2 * Copyright (c) 2003-2009 Nokia Corporation and/or its subsidiary(-ies).
4 * This component and the accompanying materials are made available
5 * under the terms of the License "Eclipse Public License v1.0"
6 * which accompanies this distribution, and is available
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".
9 * Initial Contributors:
10 * Nokia Corporation - initial contribution.
14 * Description: Table of prime numbers.
24 #ifndef __BIGINT_PRIMES_H__
25 #define __BIGINT_PRIMES_H__
29 const TUint16 KPrimeTable[] =
31 2, 3, 5, 7, 11, 13, 17, 19,
32 23, 29, 31, 37, 41, 43, 47, 53,
33 59, 61, 67, 71, 73, 79, 83, 89,
34 97, 101, 103, 107, 109, 113, 127, 131,
35 137, 139, 149, 151, 157, 163, 167, 173,
36 179, 181, 191, 193, 197, 199, 211, 223,
37 227, 229, 233, 239, 241, 251, 257, 263,
38 269, 271, 277, 281, 283, 293, 307, 311,
39 313, 317, 331, 337, 347, 349, 353, 359,
40 367, 373, 379, 383, 389, 397, 401, 409,
41 419, 421, 431, 433, 439, 443, 449, 457,
42 461, 463, 467, 479, 487, 491, 499, 503,
43 509, 521, 523, 541, 547, 557, 563, 569,
44 571, 577, 587, 593, 599, 601, 607, 613,
45 617, 619, 631, 641, 643, 647, 653, 659,
46 661, 673, 677, 683, 691, 701, 709, 719,
47 727, 733, 739, 743, 751, 757, 761, 769,
48 773, 787, 797, 809, 811, 821, 823, 827,
49 829, 839, 853, 857, 859, 863, 877, 881,
50 883, 887, 907, 911, 919, 929, 937, 941,
51 947, 953, 967, 971, 977, 983, 991, 997,
52 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
53 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
54 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
55 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
56 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
57 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
58 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
59 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459,
60 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
61 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,
62 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
63 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
64 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
65 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
66 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
67 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,
68 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003,
69 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
70 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
71 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,
72 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
73 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311,
74 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
75 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
76 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503,
77 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,
78 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
79 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,
80 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
81 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
82 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
83 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,
84 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,
85 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
86 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167,
87 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
88 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301,
89 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,
90 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
91 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491,
92 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,
93 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,
94 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671,
95 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
96 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
97 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863,
98 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923,
99 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003,
100 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
101 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129,
102 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
103 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259,
104 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337,
105 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
106 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481,
107 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547,
108 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
109 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673,
110 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
111 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813,
112 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909,
113 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967,
114 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011,
115 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
116 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167,
117 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233,
118 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
119 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399,
120 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
121 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507,
122 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573,
123 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653,
124 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711,
125 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
126 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849,
127 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897,
128 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007,
129 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
130 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
131 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211,
132 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
133 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329,
134 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379,
135 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
136 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563,
137 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637,
138 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701,
139 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779,
140 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
141 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
142 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971,
143 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027,
144 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
145 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
146 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253,
147 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349,
148 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457,
149 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517,
150 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
151 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621,
152 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691,
153 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757,
154 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853,
155 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
156 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009,
157 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087,
158 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161,
159 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231,
160 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291,
161 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369,
162 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443,
163 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537,
164 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609,
165 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677,
166 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731,
167 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803,
168 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861,
169 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941,
170 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011,
171 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091,
172 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161,
173 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227,
174 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311,
175 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377,
176 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433,
177 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491,
178 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587,
179 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649,
180 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733,
181 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791,
182 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857,
183 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929,
184 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037,
185 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099,
186 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163,
187 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247,
188 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303,
189 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369,
190 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459,
191 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531,
192 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627,
193 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691,
194 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771,
195 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
196 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937,
197 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003,
198 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087,
199 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161,
200 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
201 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317,
202 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399,
203 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483,
204 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551,
205 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657,
206 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
207 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813,
208 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887,
209 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941,
210 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011,
211 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101,
212 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161,
213 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251,
214 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323,
215 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
216 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473,
217 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
218 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589,
219 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653,
220 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739,
221 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821,
222 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907,
223 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967,
224 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033,
225 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109,
226 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177,
227 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259,
228 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
229 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421,
230 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499,
231 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597,
232 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681,
233 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723,
234 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799,
235 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,
236 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933,
237 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033,
238 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143,
239 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
240 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323,
241 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407,
242 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461,
243 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549,
244 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627,
245 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
246 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753,
247 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821,
248 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887,
249 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957,
250 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
251 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137,
252 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217,
253 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277,
254 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331,
255 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401,
256 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473,
257 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569,
258 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643,
259 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727,
260 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773,
261 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
262 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919,
263 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007,
264 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087,
265 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183,
266 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249,
267 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349,
268 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427,
269 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493,
270 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
271 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661,
272 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
273 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843,
274 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927,
275 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993,
276 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053,
277 17077, 17093, 17099, 17107, 17117, 17123, 17137, 17159,
278 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231,
279 17239, 17257, 17291, 17293, 17299, 17317, 17321, 17327,
280 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389,
281 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467,
282 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519,
283 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
284 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683,
285 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783,
286 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863
289 const TUint KPrimeTableSize = sizeof(KPrimeTable)/sizeof(TUint16);
290 const TUint KLastSmallPrime = 17863;
291 //Next line doesn't work on arm4 as it doesn't make this calculation at compile
292 //time but leaves it for runtime. Therefore we would have uninitialised const
294 //const TUint KLastSmallPrime = KPrimeTable[KPrimeTableSize-1];
295 const TUint KLastSmallPrimeSquared = KLastSmallPrime*KLastSmallPrime;