| line |
true |
false |
branch |
|
26
|
13462 |
0 |
if (m <= 0 || (m%2) == 0) return 0; |
|
|
0 |
13462 |
if (m <= 0 || (m%2) == 0) return 0; |
|
27
|
199 |
13263 |
if (in < 0 && (m%4) == 3) j = -j; |
|
|
77 |
122 |
if (in < 0 && (m%4) == 3) j = -j; |
|
28
|
31420 |
13462 |
while (n != 0) { |
|
29
|
27049 |
31420 |
while ((n % 2) == 0) { |
|
31
|
20264 |
6785 |
if ( (m % 8) == 3 || (m % 8) == 5 ) j = -j; |
|
|
10860 |
9404 |
if ( (m % 8) == 3 || (m % 8) == 5 ) j = -j; |
|
34
|
14099 |
17321 |
if ( (n % 4) == 3 && (m % 4) == 3 ) j = -j; |
|
|
2685 |
11414 |
if ( (n % 4) == 3 && (m % 4) == 3 ) j = -j; |
|
37
|
13439 |
23 |
return (m == 1) ? j : 0; |
|
46
|
0 |
13174 |
if (j == 0) return 0; |
|
47
|
5942 |
7232 |
if (j == -1) break; |
|
48
|
17 |
7215 |
if (P == (3+20*increment) && is_perfect_square(n)) return 0; |
|
|
0 |
17 |
if (P == (3+20*increment) && is_perfect_square(n)) return 0; |
|
50
|
0 |
7232 |
if (P > 65535) |
|
53
|
0 |
5942 |
if (P >= n) P %= n; /* Never happens with increment < 4 */ |
|
60
|
0 |
86 |
if (n < 4) return (n == 2 || n == 3); |
|
|
0 |
0 |
if (n < 4) return (n == 2 || n == 3); |
|
|
0 |
0 |
if (n < 4) return (n == 2 || n == 3); |
|
61
|
2 |
84 |
if (!(n&1) && !(a&1)) return 0; |
|
|
0 |
2 |
if (!(n&1) && !(a&1)) return 0; |
|
62
|
0 |
86 |
if (a < 2) croak("Base %"UVuf" is invalid", a); |
|
63
|
0 |
86 |
if (a >= n) { |
|
65
|
0 |
0 |
if (a <= 1) return (a == 1); |
|
66
|
0 |
0 |
if (a == n-1) return !(a & 1); |
|
70
|
84 |
2 |
if (n & 1) { /* The Montgomery code only works for odd n */ |
|
72
|
41 |
43 |
const uint64_t monta = (a == 2) ? mont_get2(n) : mont_geta(a, n); |
|
82
|
0 |
109 |
if (n < 5) return (n == 2 || n == 3); |
|
|
0 |
0 |
if (n < 5) return (n == 2 || n == 3); |
|
|
0 |
0 |
if (n < 5) return (n == 2 || n == 3); |
|
83
|
0 |
109 |
if (!(n&1)) return 0; |
|
84
|
0 |
109 |
if (a < 2) croak("Base %"UVuf" is invalid", a); |
|
85
|
73 |
36 |
if (a > 2) { |
|
86
|
1 |
72 |
if (a >= n) { |
|
88
|
0 |
1 |
if (a <= 1) return (a == 1); |
|
89
|
1 |
0 |
if (a == n-1) return !(a & 1); |
|
91
|
0 |
72 |
if ((n % a) == 0) return 0; |
|
98
|
23 |
85 |
if (ap != mont1 && ap != n-mont1) return 0; |
|
|
0 |
23 |
if (ap != mont1 && ap != n-mont1) return 0; |
|
99
|
36 |
72 |
if (a == 2) { |
|
101
|
8 |
28 |
return (nmod8 == 1 || nmod8 == 7) ? (ap == mont1) : (ap == n-mont1); |
|
|
3 |
5 |
return (nmod8 == 1 || nmod8 == 7) ? (ap == mont1) : (ap == n-mont1); |
|
103
|
54 |
18 |
return (kronecker_uu(a,n) >= 0) ? (ap == mont1) : (ap == n-mont1); |
|
126
|
0 |
1195 |
if (n < 5) return (n == 2 || n == 3); |
|
|
0 |
0 |
if (n < 5) return (n == 2 || n == 3); |
|
|
0 |
0 |
if (n < 5) return (n == 2 || n == 3); |
|
127
|
0 |
1195 |
if (!(n&1)) return 0; |
|
132
|
314 |
881 |
ap = mont_powmod(mont2, (n-1) >> (1 + (nmod8 == 1)), n); |
|
133
|
425 |
770 |
if (ap == mont1) return (nmod8 == 1 || nmod8 == 7); |
|
|
273 |
152 |
if (ap == mont1) return (nmod8 == 1 || nmod8 == 7); |
|
|
273 |
0 |
if (ap == mont1) return (nmod8 == 1 || nmod8 == 7); |
|
134
|
761 |
9 |
if (ap == n-mont1) return (nmod8 == 1 || nmod8 == 3 || nmod8 == 5); |
|
|
602 |
159 |
if (ap == n-mont1) return (nmod8 == 1 || nmod8 == 3 || nmod8 == 5); |
|
|
301 |
301 |
if (ap == n-mont1) return (nmod8 == 1 || nmod8 == 3 || nmod8 == 5); |
|
|
301 |
0 |
if (ap == n-mont1) return (nmod8 == 1 || nmod8 == 3 || nmod8 == 5); |
|
151
|
0 |
89229 |
MPUassert(n > 3, "MR called with n <= 3"); |
|
152
|
1 |
89228 |
if ((n & 1) == 0) return 0; |
|
158
|
176034 |
89228 |
while (!(u&1)) { t++; u >>= 1; } |
|
159
|
93119 |
30761 |
for (j = 0; j < nbases; j++) { |
|
161
|
2 |
93117 |
if (a < 2) croak("Base %"UVuf" is invalid", (UV)a); |
|
162
|
91 |
93026 |
if (a >= n) { |
|
164
|
85 |
6 |
if (a == 0 || (a == n-1 && a&1)) return 0; |
|
|
2 |
83 |
if (a == 0 || (a == n-1 && a&1)) return 0; |
|
|
0 |
2 |
if (a == 0 || (a == n-1 && a&1)) return 0; |
|
167
|
93108 |
3 |
if (a == 1 || a == n-1 || !ma) continue; |
|
|
93099 |
9 |
if (a == 1 || a == n-1 || !ma) continue; |
|
|
0 |
93099 |
if (a == 1 || a == n-1 || !ma) continue; |
|
169
|
75891 |
17208 |
if (md != mont1 && md != n-mont1) { |
|
|
68525 |
7366 |
if (md != mont1 && md != n-mont1) { |
|
170
|
80516 |
58429 |
for (i=1; i
|
|
171
|
0 |
80516 |
md = mont_sqrmod(md, n); |
|
172
|
30 |
80486 |
if (md == mont1) return 0; |
|
173
|
10066 |
70420 |
if (md == n-mont1) break; |
|
175
|
58429 |
10066 |
if (i == t) |
|
215
|
0 |
8295 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
216
|
8295 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
8295 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
230
|
16674 |
8295 |
while (!(u&1)) { t++; u >>= 1; } |
|
232
|
6916 |
1379 |
if (md != mont1 && md != n-mont1) { |
|
|
5394 |
1522 |
if (md != mont1 && md != n-mont1) { |
|
233
|
6453 |
3559 |
for (i=1; i
|
|
234
|
105 |
6348 |
md = mont_sqrmod(md, n); |
|
235
|
0 |
6453 |
if (md == mont1) return 0; |
|
236
|
1835 |
4618 |
if (md == n-mont1) break; |
|
238
|
3559 |
1835 |
if (i == t) |
|
243
|
0 |
4736 |
if (P == 0) return 0; |
|
247
|
9738 |
4736 |
while ( (d & 1) == 0 ) { s++; d >>= 1; } |
|
252
|
72 |
4664 |
W = submod( mont_mulmod( montP, montP, n), mont2, n); |
|
254
|
222739 |
4736 |
{ UV v = d; b = 1; while (v >>= 1) b++; } |
|
255
|
222739 |
4736 |
while (b-- > 1) { |
|
256
|
4385 |
218354 |
UV T = submod( mont_mulmod(V, W, n), montP, n); |
|
257
|
118554 |
104185 |
if ( (d >> (b-1)) & UVCONST(1) ) { |
|
259
|
2307 |
116247 |
W = submod( mont_mulmod(W, W, n), mont2, n); |
|
262
|
2078 |
102107 |
V = submod( mont_mulmod(V, V, n), mont2, n); |
|
267
|
4324 |
412 |
if (V == mont2 || V == (n-mont2)) |
|
|
2197 |
2127 |
if (V == mont2 || V == (n-mont2)) |
|
269
|
4612 |
101 |
while (s-- > 1) { |
|
270
|
2026 |
2586 |
if (V == 0) |
|
272
|
45 |
2541 |
V = submod( mont_mulmod(V, V, n), mont2, n); |
|
273
|
0 |
2586 |
if (V == mont2) |
|
290
|
0 |
1 |
{ UV v = k; while (!(v & 1)) { v >>= 1; s++; } } |
|
291
|
23 |
1 |
{ UV v = k; while (v >>= 1) m++; } |
|
293
|
1 |
0 |
if (Pmod == 1 && Qmod == (n-1)) { |
|
|
1 |
0 |
if (Pmod == 1 && Qmod == (n-1)) { |
|
295
|
23 |
1 |
for (j = m; j > s; j--) { |
|
297
|
8 |
15 |
Ql = (Sl==1) ? 1 : n-1; |
|
298
|
8 |
15 |
if ( (k >> j) & UVCONST(1) ) { |
|
302
|
6 |
2 |
Vh = submod(sqrmod(Vh, n), (Sh==1) ? 2 : n-2, n); |
|
307
|
6 |
9 |
Vl = submod(sqrmod(Vl, n), (Sl==1) ? 2 : n-2, n); |
|
311
|
0 |
1 |
Ql = (Sl==1) ? 1 : n-1; |
|
314
|
0 |
1 |
for (j = 0; j < s; j++) { |
|
316
|
0 |
0 |
Vl = submod(sqrmod(Vl, n), (j>0) ? 2 : n-2, n); |
|
320
|
1 |
0 |
*Qkret = (s>0)?1:n-1; |
|
324
|
0 |
0 |
for (j = m; j > s; j--) { |
|
326
|
0 |
0 |
if ( (k >> j) & UVCONST(1) ) { |
|
343
|
0 |
0 |
for (j = 0; j < s; j++) { |
|
358
|
0 |
26319 |
MPUassert(n > 1, "lucas_sequence: modulus n must be > 1"); |
|
359
|
25 |
26294 |
if (k == 0) { |
|
366
|
26139 |
155 |
Qmod = (Q < 0) ? (UV) (Q + (IV)(((-Q/n)+1)*n)) : (UV)Q % n; |
|
367
|
0 |
26294 |
Pmod = (P < 0) ? (UV) (P + (IV)(((-P/n)+1)*n)) : (UV)P % n; |
|
369
|
13 |
26281 |
if (Dmod == 0) { |
|
376
|
1 |
26280 |
if ((n % 2) == 0) { |
|
383
|
365056 |
26280 |
{ UV v = k; b = 0; while (v >>= 1) b++; } |
|
385
|
53 |
26227 |
if (Q == 1) { |
|
386
|
133 |
53 |
while (b--) { |
|
389
|
51 |
82 |
if ( (k >> b) & UVCONST(1) ) { |
|
392
|
2 |
49 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
394
|
4 |
47 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
397
|
25973 |
254 |
} else if (P == 1 && Q == -1) { |
|
|
25944 |
29 |
} else if (P == 1 && Q == -1) { |
|
401
|
363747 |
25944 |
while (b--) { |
|
403
|
169766 |
193981 |
if (sign == 1) V = mulsubmod(V, V, 2, n); |
|
406
|
168054 |
195693 |
if ( (k >> b) & UVCONST(1) ) { |
|
409
|
62316 |
105738 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
411
|
63745 |
104309 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
415
|
25927 |
17 |
if (sign == 1) Qk = 1; |
|
417
|
1176 |
283 |
while (b--) { |
|
421
|
536 |
640 |
if ( (k >> b) & UVCONST(1) ) { |
|
424
|
124 |
412 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
426
|
167 |
369 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
442
|
0 |
199 |
if (U == 0) return 0; |
|
443
|
14 |
185 |
if (k == 0) { *U = 0; return 1; } |
|
447
|
147 |
185 |
{ UV v = k; while (!(v & 1)) { v >>= 1; s++; } } |
|
448
|
403 |
185 |
{ UV v = k; while (v >>= 1) n++; } |
|
450
|
256 |
185 |
for (j = n; j > s; j--) { |
|
451
|
256 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
256 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
256 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
256 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
256 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
453
|
175 |
81 |
if ( (k >> j) & UVCONST(1) ) { |
|
465
|
185 |
0 |
if (OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
185 |
if (OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
468
|
185 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
185 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
185 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
185 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
185 |
if (OVERHALF(Uh) || OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
472
|
147 |
185 |
for (j = 0; j < s; j++) { |
|
473
|
147 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vl) || OVERHALF(Ql)) return 0; |
|
|
147 |
0 |
if (OVERHALF(Uh) || OVERHALF(Vl) || OVERHALF(Ql)) return 0; |
|
|
0 |
147 |
if (OVERHALF(Uh) || OVERHALF(Vl) || OVERHALF(Ql)) return 0; |
|
486
|
0 |
152 |
if (V == 0) return 0; |
|
487
|
11 |
141 |
if (k == 0) { *V = 2; return 1; } |
|
491
|
110 |
141 |
{ UV v = k; while (!(v & 1)) { v >>= 1; s++; } } |
|
492
|
304 |
141 |
{ UV v = k; while (v >>= 1) n++; } |
|
494
|
194 |
141 |
for (j = n; j > s; j--) { |
|
495
|
194 |
0 |
if (OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
194 |
0 |
if (OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
194 |
0 |
if (OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
194 |
if (OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
497
|
130 |
64 |
if ( (k >> j) & UVCONST(1) ) { |
|
507
|
141 |
0 |
if (OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
141 |
if (OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
510
|
141 |
0 |
if (OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
141 |
0 |
if (OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
141 |
0 |
if (OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
|
0 |
141 |
if (OVERHALF(Vh) || OVERHALF(Vl) || OVERHALF(Ql) || OVERHALF(Qh)) return 0; |
|
513
|
110 |
141 |
for (j = 0; j < s; j++) { |
|
514
|
110 |
0 |
if (OVERHALF(Vl) || OVERHALF(Ql)) return 0; |
|
|
0 |
110 |
if (OVERHALF(Vl) || OVERHALF(Ql)) return 0; |
|
536
|
1 |
70 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
1 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
537
|
65 |
5 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
65 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
539
|
43 |
22 |
if (strength < 3) { |
|
546
|
44 |
64 |
if (j != 1 && Du != n) break; |
|
|
43 |
1 |
if (j != 1 && Du != n) break; |
|
547
|
0 |
65 |
if (Du == 21 && is_perfect_square(n)) return 0; |
|
|
0 |
0 |
if (Du == 21 && is_perfect_square(n)) return 0; |
|
551
|
1 |
42 |
if (j != -1) return 0; |
|
554
|
0 |
42 |
if (strength == 2 && Q == -1) P=Q=D=5; /* Method A* */ |
|
|
0 |
0 |
if (strength == 2 && Q == -1) P=Q=D=5; /* Method A* */ |
|
556
|
22 |
20 |
Qk = (Q >= 0) ? Q % n : n-(((UV)(-Q)) % n); |
|
557
|
0 |
42 |
if (gcd_ui(Qk,n) != 1) return 0; |
|
560
|
0 |
22 |
if (P == 0) return 0; |
|
564
|
0 |
64 |
MPUassert( D == (P*P - 4*Q) , "is_lucas_pseudoprime: incorrect DPQ"); |
|
575
|
44 |
20 |
if (strength > 0) |
|
576
|
98 |
44 |
while ( (d & 1) == 0 ) { s++; d >>= 1; } |
|
583
|
22 |
42 |
: (P >= 0) ? mont_geta(P, n) |
|
584
|
22 |
0 |
: n - mont_geta(-P, n); |
|
586
|
42 |
22 |
: (Q >= 0) ? mont_geta(Q, n) |
|
587
|
22 |
20 |
: n - mont_geta(-Q, n); |
|
589
|
42 |
22 |
: n - mont_geta(-D, n); |
|
591
|
935 |
64 |
{ UV v = d; b = 0; while (v >>= 1) b++; } |
|
597
|
42 |
22 |
if (Q == 1 || Q == -1) { /* Faster code for |Q|=1, also opt for P=1 */ |
|
|
16 |
26 |
if (Q == 1 || Q == -1) { /* Faster code for |Q|=1, also opt for P=1 */ |
|
599
|
572 |
38 |
while (b--) { |
|
600
|
0 |
572 |
U = mont_mulmod(U, V, n); |
|
601
|
471 |
101 |
if (sign == 1) V = submod( mont_sqrmod(V,n), mont2, n); |
|
|
0 |
471 |
if (sign == 1) V = submod( mont_sqrmod(V,n), mont2, n); |
|
602
|
0 |
101 |
else V = addmod( mont_sqrmod(V,n), mont2, n); |
|
604
|
238 |
334 |
if ( (d >> b) & UVCONST(1) ) { |
|
605
|
0 |
238 |
UV t2 = mont_mulmod(U, montD, n); |
|
606
|
92 |
146 |
if (P == 1) { |
|
610
|
0 |
146 |
U = addmod( mont_mulmod(U, montP, n), V, n); |
|
611
|
0 |
146 |
V = addmod( mont_mulmod(V, montP, n), t2, n); |
|
613
|
105 |
133 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
614
|
126 |
112 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
618
|
7 |
31 |
Qk = (sign == 1) ? mont1 : n-mont1; |
|
621
|
363 |
26 |
while (b--) { |
|
622
|
0 |
363 |
U = mont_mulmod(U, V, n); |
|
623
|
0 |
363 |
V = submod( mont_sqrmod(V,n), addmod(Qk,Qk,n), n); |
|
624
|
0 |
363 |
Qk = mont_sqrmod(Qk,n); |
|
625
|
186 |
177 |
if ( (d >> b) & UVCONST(1) ) { |
|
626
|
0 |
186 |
UV t2 = mont_mulmod(U, montD, n); |
|
627
|
0 |
186 |
U = addmod( mont_mulmod(U, montP, n), V, n); |
|
628
|
84 |
102 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
629
|
0 |
186 |
V = addmod( mont_mulmod(V, montP, n), t2, n); |
|
630
|
102 |
84 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
631
|
0 |
186 |
Qk = mont_mulmod(Qk, montQ, n); |
|
636
|
20 |
44 |
if (strength == 0) { |
|
637
|
20 |
0 |
if (U == 0) |
|
639
|
22 |
22 |
} else if (strength == 1) { |
|
640
|
8 |
14 |
if (U == 0) |
|
642
|
36 |
3 |
while (s--) { |
|
643
|
11 |
25 |
if (V == 0) |
|
645
|
22 |
3 |
if (s) { |
|
646
|
0 |
22 |
V = submod( mont_sqrmod(V,n), addmod(Qk,Qk,n), n); |
|
647
|
0 |
22 |
Qk = mont_sqrmod(Qk,n); |
|
650
|
0 |
22 |
} else if (strength == 2) { |
|
653
|
0 |
0 |
if (U == 0) |
|
655
|
0 |
0 |
while (s--) { |
|
656
|
0 |
0 |
if (V == 0) |
|
659
|
0 |
0 |
V = submod( mont_sqrmod(V,n), addmod(Qk,Qk,n), n); |
|
660
|
0 |
0 |
Qk = mont_sqrmod(Qk,n); |
|
662
|
0 |
0 |
if (!is_slpsp) return 0; /* slpsp */ |
|
663
|
0 |
0 |
if (V != addmod(montQ,montQ,n)) return 0; /* V_{n+1} != 2Q mod n */ |
|
665
|
0 |
0 |
Qj = (qjacobi == 0) ? 0 : (qjacobi == 1) ? montQ : n-montQ; |
|
|
0 |
0 |
Qj = (qjacobi == 0) ? 0 : (qjacobi == 1) ? montQ : n-montQ; |
|
666
|
0 |
0 |
if (Ql != Qj) return 0; /* n is epsp base Q */ |
|
669
|
14 |
8 |
if ( U == 0 && (V == mont2 || V == (n-mont2)) ) |
|
|
11 |
3 |
if ( U == 0 && (V == mont2 || V == (n-mont2)) ) |
|
|
11 |
0 |
if ( U == 0 && (V == mont2 || V == (n-mont2)) ) |
|
672
|
20 |
0 |
while (s--) { |
|
673
|
8 |
12 |
if (V == 0) |
|
675
|
12 |
0 |
if (s) |
|
676
|
0 |
12 |
V = submod( mont_sqrmod(V,n), mont2, n); |
|
752
|
0 |
1184 |
if (n < 13) return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11); |
|
|
0 |
0 |
if (n < 13) return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11); |
|
|
0 |
0 |
if (n < 13) return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11); |
|
|
0 |
0 |
if (n < 13) return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11); |
|
|
0 |
0 |
if (n < 13) return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11); |
|
|
0 |
0 |
if (n < 13) return (n == 2 || n == 3 || n == 5 || n == 7 || n == 11); |
|
753
|
1184 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
1184 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
754
|
1184 |
0 |
if (increment < 1 || increment > 256) |
|
|
0 |
1184 |
if (increment < 1 || increment > 256) |
|
758
|
0 |
1184 |
if ( (increment >= 16 && n <= 331) || (increment > 148 && n <= 631) ) |
|
|
0 |
0 |
if ( (increment >= 16 && n <= 331) || (increment > 148 && n <= 631) ) |
|
|
0 |
1184 |
if ( (increment >= 16 && n <= 331) || (increment > 148 && n <= 631) ) |
|
|
0 |
0 |
if ( (increment >= 16 && n <= 331) || (increment > 148 && n <= 631) ) |
|
762
|
0 |
1184 |
if (P == 0) return 0; |
|
766
|
2351 |
1184 |
while ( (d & 1) == 0 ) { s++; d >>= 1; } |
|
767
|
18226 |
1184 |
{ UV v = d; b = 0; while (v >>= 1) b++; } |
|
774
|
0 |
1184 |
W = submod( mont_mulmod( montP, montP, n), mont2, n); |
|
776
|
18226 |
1184 |
while (b--) { |
|
777
|
0 |
18226 |
UV T = submod( mont_mulmod(V, W, n), montP, n); |
|
778
|
9373 |
8853 |
if ( (d >> b) & UVCONST(1) ) { |
|
780
|
0 |
9373 |
W = submod( mont_mulmod(W, W, n), mont2, n); |
|
783
|
0 |
8853 |
V = submod( mont_mulmod(V, V, n), mont2, n); |
|
787
|
1052 |
132 |
if (V == mont2 || V == (n-mont2)) |
|
|
552 |
500 |
if (V == mont2 || V == (n-mont2)) |
|
790
|
1077 |
0 |
while (s--) { |
|
791
|
500 |
577 |
if (V == 0) |
|
793
|
577 |
0 |
if (s) |
|
794
|
0 |
577 |
V = submod( mont_mulmod(V, V, n), mont2, n); |
|
866
|
0 |
20 |
if (n <= 1) return; |
|
869
|
18 |
2 |
if ( (n&1) ) { |
|
878
|
605 |
20 |
{ UV v = n; b = 1; while (v >>= 1) b++; } |
|
880
|
605 |
20 |
while (b-- > 1) { |
|
883
|
558 |
47 |
if (n&1) { |
|
884
|
0 |
558 |
T[0] = submod(submod(mont_sqrmod(S[0],n), S[5],n), S[5],n); |
|
885
|
0 |
558 |
T[1] = submod(submod(mont_sqrmod(S[1],n), S[4],n), S[4],n); |
|
886
|
0 |
558 |
T[2] = submod(submod(mont_sqrmod(S[2],n), S[3],n), S[3],n); |
|
887
|
0 |
558 |
T[3] = submod(submod(mont_sqrmod(S[3],n), S[2],n), S[2],n); |
|
888
|
0 |
558 |
T[4] = submod(submod(mont_sqrmod(S[4],n), S[1],n), S[1],n); |
|
889
|
0 |
558 |
T[5] = submod(submod(mont_sqrmod(S[5],n), S[0],n), S[0],n); |
|
904
|
281 |
324 |
if ( (n >> (b-1)) & 1U ) { |
|
913
|
18 |
2 |
if (n&1) { /* Recover result from Montgomery form */ |
|
914
|
108 |
18 |
for (i = 0; i < 6; i++) |
|
915
|
0 |
108 |
S[i] = mont_recover(S[i],n); |
|
925
|
0 |
20 |
if (n < 3) return (n >= 2); |
|
926
|
2 |
18 |
if (!(n&1) && restricted > 2) return 0; /* Odds only for restrict > 2 */ |
|
|
0 |
2 |
if (!(n&1) && restricted > 2) return 0; /* Odds only for restrict > 2 */ |
|
931
|
2 |
18 |
if (!(n32&1) && !(( 22 >> (n32% 7)) & 1)) return 0; |
|
|
0 |
2 |
if (!(n32&1) && !(( 22 >> (n32% 7)) & 1)) return 0; |
|
932
|
0 |
20 |
if (!(n32%3) && !(( 523 >> (n32%13)) & 1)) return 0; |
|
|
0 |
0 |
if (!(n32%3) && !(( 523 >> (n32%13)) & 1)) return 0; |
|
933
|
2 |
18 |
if (!(n32%5) && !((65890 >> (n32%24)) & 1)) return 0; |
|
|
0 |
2 |
if (!(n32%5) && !((65890 >> (n32%24)) & 1)) return 0; |
|
934
|
0 |
20 |
if (!(n32%4) && !(( 514 >> (n32%14)) & 1)) return 0; |
|
|
0 |
0 |
if (!(n32%4) && !(( 514 >> (n32%14)) & 1)) return 0; |
|
936
|
300 |
20 |
for (i = 4; i < NPERRINDIV; i++) { |
|
937
|
12 |
288 |
if ((n % _perrindata[i].div) == 0) { |
|
940
|
0 |
12 |
if (!((mask[mod/32] >> (mod%32)) & 1)) |
|
948
|
0 |
20 |
if (S[4] != 0) return 0; /* P(n) = 0 mod n */ |
|
949
|
15 |
5 |
if (restricted == 0) return 1; |
|
951
|
1 |
4 |
if (S[1] != n-1) return 0; /* P(-n) = -1 mod n */ |
|
952
|
1 |
3 |
if (restricted == 1) return 1; |
|
968
|
1 |
2 |
if (jacobi == -1) { /* Q-type */ |
|
973
|
1 |
0 |
if (S[0] == A && S[2] == B && S[3] == B && S[5] == C && |
|
|
1 |
0 |
if (S[0] == A && S[2] == B && S[3] == B && S[5] == C && |
|
|
1 |
0 |
if (S[0] == A && S[2] == B && S[3] == B && S[5] == C && |
|
|
0 |
1 |
if (S[0] == A && S[2] == B && S[3] == B && S[5] == C && |
|
|
0 |
0 |
if (S[0] == A && S[2] == B && S[3] == B && S[5] == C && |
|
974
|
0 |
0 |
B != 3 && submod(mulmod(B2,B,n),B,n) == 1) { |
|
975
|
0 |
0 |
if (_XS_get_verbose()>1) printf("%"UVuf" Q-Type %"UVuf" -1 %"UVuf" %"UVuf" 0 %"UVuf"\n", n, A, B, B, C); |
|
981
|
2 |
0 |
if (jacobi == 0 && n != 23 && restricted > 2) { |
|
|
2 |
0 |
if (jacobi == 0 && n != 23 && restricted > 2) { |
|
|
1 |
1 |
if (jacobi == 0 && n != 23 && restricted > 2) { |
|
982
|
0 |
1 |
if (_XS_get_verbose()>1) printf("%"UVuf" Jacobi %d\n",n,jacobi); |
|
986
|
1 |
0 |
if (S[0] == 1 && S[2] == 3 && S[3] == 3 && S[5] == 2) { |
|
|
1 |
0 |
if (S[0] == 1 && S[2] == 3 && S[3] == 3 && S[5] == 2) { |
|
|
1 |
0 |
if (S[0] == 1 && S[2] == 3 && S[3] == 3 && S[5] == 2) { |
|
|
1 |
0 |
if (S[0] == 1 && S[2] == 3 && S[3] == 3 && S[5] == 2) { |
|
987
|
0 |
1 |
if (_XS_get_verbose()>1) printf("%"UVuf" S-Type 1 -1 3 3 0 2\n",n); |
|
989
|
0 |
0 |
} else if (S[0] == 0 && S[5] == n-1 && S[2] != S[3] && |
|
|
0 |
0 |
} else if (S[0] == 0 && S[5] == n-1 && S[2] != S[3] && |
|
990
|
0 |
0 |
addmod(S[2],S[3],n) == n-3 && sqrmod(submod(S[2],S[3],n),n) == n-(23%n)) { |
|
991
|
0 |
0 |
if (_XS_get_verbose()>1) printf("%"UVuf" I-Type 0 -1 %"UVuf" %"UVuf" 0 -1\n",n, S[2], S[3]); |
|
996
|
0 |
1 |
if (_XS_get_verbose()>1) printf("%"UVuf" ? %2d ? %"UVuf" -1 %"UVuf" %"UVuf" 0 %"UVuf"\n", n, jacobi, S[0],S[2],S[3],S[5]); |
|
1007
|
0 |
28 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
1008
|
28 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
28 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
1010
|
0 |
28 |
if (P == 0 && Q == 0) { |
|
|
0 |
0 |
if (P == 0 && Q == 0) { |
|
1012
|
0 |
0 |
if (n == 7) P = 1; /* So we don't test kronecker(-7,7) */ |
|
1015
|
0 |
0 |
if (P == 3) P = 5; /* P=3,Q=2 -> D=9-8=1 => k=1, so skip */ |
|
1019
|
0 |
0 |
if (P == 10001 && is_perfect_square(n)) return 0; |
|
|
0 |
0 |
if (P == 10001 && is_perfect_square(n)) return 0; |
|
1020
|
0 |
0 |
} while (k == 1); |
|
1021
|
0 |
0 |
if (k == 0) return 0; |
|
1023
|
0 |
0 |
if (_XS_get_verbose()) printf("%"UVuf" Frobenius (%"IVdf",%"IVdf") : x^2 - %"IVdf"x + %"IVdf"\n", n, P, Q, P, Q); |
|
1028
|
11 |
17 |
if (D != 5 && is_perfect_square(Du)) |
|
|
0 |
11 |
if (D != 5 && is_perfect_square(Du)) |
|
1035
|
0 |
28 |
if (Qk != 1) { |
|
1036
|
0 |
0 |
if (Qk == n) return !!is_prob_prime(n); |
|
1039
|
28 |
0 |
if (k == 0) { |
|
1041
|
0 |
28 |
if (k == 0) return 0; |
|
1042
|
24 |
4 |
if (k == 1) { |
|
1046
|
4 |
0 |
Vcomp = (Q >= 0) ? Qu : n-Qu; |
|
1052
|
28 |
0 |
if (U == 0 && V == Vcomp) return 1; |
|
|
28 |
0 |
if (U == 0 && V == Vcomp) return 1; |
|
1072
|
0 |
102 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
1073
|
102 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
102 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
1074
|
0 |
102 |
if (is_perfect_square(n)) return 0; |
|
1079
|
172 |
10 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
8 |
164 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
5 |
3 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
5 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
5 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
5 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
0 |
5 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
1082
|
80 |
102 |
} while (k == 1); |
|
1083
|
40 |
62 |
if (k == 0) return 0; |
|
1091
|
1889 |
62 |
while (d) { |
|
1092
|
926 |
963 |
if (d & 1) { |
|
1094
|
0 |
926 |
ra = addmod( mont_mulmod(ta,a,n), mont_mulmod(mont_mulmod(tb,b,n),montc,n), n ); |
|
|
0 |
0 |
ra = addmod( mont_mulmod(ta,a,n), mont_mulmod(mont_mulmod(tb,b,n),montc,n), n ); |
|
|
0 |
926 |
ra = addmod( mont_mulmod(ta,a,n), mont_mulmod(mont_mulmod(tb,b,n),montc,n), n ); |
|
|
0 |
926 |
ra = addmod( mont_mulmod(ta,a,n), mont_mulmod(mont_mulmod(tb,b,n),montc,n), n ); |
|
1095
|
0 |
926 |
rb = addmod( mont_mulmod(tb,a,n), mont_mulmod(ta,b,n), n); |
|
|
0 |
926 |
rb = addmod( mont_mulmod(tb,a,n), mont_mulmod(ta,b,n), n); |
|
1098
|
1827 |
62 |
if (d) { |
|
1099
|
0 |
1827 |
UV t = mont_mulmod(mont_mulmod(b,b,n),montc,n); |
|
|
0 |
0 |
UV t = mont_mulmod(mont_mulmod(b,b,n),montc,n); |
|
|
0 |
1827 |
UV t = mont_mulmod(mont_mulmod(b,b,n),montc,n); |
|
1100
|
0 |
1827 |
b = mont_mulmod(b,a,n); |
|
1102
|
0 |
1827 |
a = addmod(mont_mulmod(a,a,n),t,n); |
|
1105
|
8 |
54 |
return (ra == mont1 && rb == n-mont1); |
|
|
8 |
0 |
return (ra == mont1 && rb == n-mont1); |
|
1145
|
0 |
102 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
1146
|
102 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
102 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
1148
|
204 |
0 |
for (x = 0; x < 1000000; x++) { |
|
1149
|
187 |
17 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
180 |
7 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
180 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
180 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
180 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
180 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
180 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
0 |
180 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
1153
|
81 |
99 |
if (j == -1) break; |
|
1154
|
78 |
21 |
if (j == 0 || (x == 20 && is_perfect_square(n))) |
|
|
0 |
78 |
if (j == 0 || (x == 20 && is_perfect_square(n))) |
|
|
0 |
0 |
if (j == 0 || (x == 20 && is_perfect_square(n))) |
|
1157
|
0 |
81 |
if (x >= 1000000) croak("FU test failure, unable to find suitable a"); |
|
1159
|
15 |
66 |
if (t1 != 1 && t1 != n) |
|
|
15 |
0 |
if (t1 != 1 && t1 != n) |
|
1162
|
1956 |
66 |
{ UV v = np1; len = 1; while (v >>= 1) len++; } |
|
1174
|
41 |
25 |
if (x == 0) { |
|
1176
|
1213 |
41 |
for (bit = len-2; bit >= 0; bit--) { |
|
1178
|
0 |
1213 |
b = mont_mulmod(submod(b, a, n), addmod(b, a, n), n); |
|
1179
|
0 |
1213 |
a = mont_mulmod(a, t1, n); |
|
1180
|
582 |
631 |
if ( (np1 >> bit) & UVCONST(1) ) { |
|
1189
|
743 |
25 |
for (bit = len-2; bit >= 0; bit--) { |
|
1190
|
0 |
743 |
t1 = addmod( mont_mulmod(a, x, n), addmod(b, b, n), n); |
|
1191
|
0 |
743 |
b = mont_mulmod(submod(b, a, n), addmod(b, a, n), n); |
|
1192
|
0 |
743 |
a = mont_mulmod(a, t1, n); |
|
1193
|
375 |
368 |
if ( (np1 >> bit) & UVCONST(1) ) { |
|
1196
|
0 |
375 |
a = addmod( mont_mulmod(a, multiplier, n), t1, n); |
|
1200
|
9 |
57 |
return (a == 0 && b == result); |
|
|
9 |
0 |
return (a == 0 && b == result); |
|
1251
|
111138 |
2265 |
for (i = 0; i < NUM_KNOWN_MERSENNE_PRIMES; i++) |
|
1252
|
17 |
111121 |
if (p == _mersenne_primes[i]) |
|
1254
|
2265 |
0 |
return (p < LAST_CHECKED_MERSENNE) ? 0 : -1; |
|
1260
|
0 |
0 |
if (p == 2) return 1; |
|
1261
|
0 |
0 |
if (!is_prob_prime(p)) return 0; |
|
1262
|
0 |
0 |
if (p > BITS_PER_WORD) croak("lucas_lehmer with p > BITS_PER_WORD"); |
|
1265
|
0 |
0 |
for (k = 3; k <= p; k++) { |
|
1282
|
0 |
61637 |
if (x < 7) return (x == 2 || x == 3 || x == 5); |
|
|
0 |
0 |
if (x < 7) return (x == 2 || x == 3 || x == 5); |
|
|
0 |
0 |
if (x < 7) return (x == 2 || x == 3 || x == 5); |
|
|
0 |
0 |
if (x < 7) return (x == 2 || x == 3 || x == 5); |
|
1283
|
0 |
61637 |
if (!(x&1)) return 0; |
|
1295
|
6358 |
172222 |
if (n < 11) { |
|
1296
|
6358 |
0 |
if (n == 2 || n == 3 || n == 5 || n == 7) return 2; |
|
|
3424 |
2934 |
if (n == 2 || n == 3 || n == 5 || n == 7) return 2; |
|
|
1511 |
1913 |
if (n == 2 || n == 3 || n == 5 || n == 7) return 2; |
|
|
1306 |
205 |
if (n == 2 || n == 3 || n == 5 || n == 7) return 2; |
|
1301
|
3356 |
168866 |
if (n > UVCONST(4294967295)) { /* input is >= 2^32, UV is 64-bit*/ |
|
1302
|
3356 |
0 |
if (!(n%2) || !(n%3) || !(n%5) || !(n%7)) return 0; |
|
|
2463 |
893 |
if (!(n%2) || !(n%3) || !(n%5) || !(n%7)) return 0; |
|
|
2085 |
378 |
if (!(n%2) || !(n%3) || !(n%5) || !(n%7)) return 0; |
|
|
272 |
1813 |
if (!(n%2) || !(n%3) || !(n%5) || !(n%7)) return 0; |
|
1303
|
1665 |
148 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
|
1544 |
121 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
|
1463 |
81 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
|
1401 |
62 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
|
1345 |
56 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
1304
|
1303 |
42 |
!(n%23) || !(n%29) || !(n%31) || !(n%37) || |
|
|
1265 |
38 |
!(n%23) || !(n%29) || !(n%31) || !(n%37) || |
|
|
1239 |
26 |
!(n%23) || !(n%29) || !(n%31) || !(n%37) || |
|
|
1220 |
19 |
!(n%23) || !(n%29) || !(n%31) || !(n%37) || |
|
1305
|
1202 |
18 |
!(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; |
|
|
1184 |
18 |
!(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; |
|
|
18 |
1166 |
!(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; |
|
1306
|
1146 |
20 |
if (!(n%59) || !(n%61) || !(n%67) || !(n%71)) return 0; |
|
|
1133 |
13 |
if (!(n%59) || !(n%61) || !(n%67) || !(n%71)) return 0; |
|
|
1121 |
12 |
if (!(n%59) || !(n%61) || !(n%67) || !(n%71)) return 0; |
|
|
12 |
1109 |
if (!(n%59) || !(n%61) || !(n%67) || !(n%71)) return 0; |
|
1307
|
1100 |
9 |
if (!(n%73) || !(n%79) || !(n%83) || !(n%89)) return 0; |
|
|
1089 |
11 |
if (!(n%73) || !(n%79) || !(n%83) || !(n%89)) return 0; |
|
|
1076 |
13 |
if (!(n%73) || !(n%79) || !(n%83) || !(n%89)) return 0; |
|
|
5 |
1071 |
if (!(n%73) || !(n%79) || !(n%83) || !(n%89)) return 0; |
|
1316
|
168835 |
31 |
if (!(x%2) || !(x%3) || !(x%5) || !(x%7)) return 0; |
|
|
127730 |
41105 |
if (!(x%2) || !(x%3) || !(x%5) || !(x%7)) return 0; |
|
|
111167 |
16563 |
if (!(x%2) || !(x%3) || !(x%5) || !(x%7)) return 0; |
|
|
11466 |
99701 |
if (!(x%2) || !(x%3) || !(x%5) || !(x%7)) return 0; |
|
1317
|
2529 |
97172 |
if (x < 121) /* 11*11 */ return 2; |
|
1318
|
91714 |
5458 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
|
86326 |
5388 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
|
81962 |
4364 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
|
77646 |
4316 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
|
74710 |
2936 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
1319
|
73597 |
1113 |
!(x%23) || !(x%29) || !(x%31) || !(x%37) || |
|
|
70698 |
2899 |
!(x%23) || !(x%29) || !(x%31) || !(x%37) || |
|
|
69075 |
1623 |
!(x%23) || !(x%29) || !(x%31) || !(x%37) || |
|
|
67599 |
1476 |
!(x%23) || !(x%29) || !(x%31) || !(x%37) || |
|
1320
|
64877 |
2722 |
!(x%41) || !(x%43) || !(x%47) || !(x%53)) return 0; |
|
|
64357 |
520 |
!(x%41) || !(x%43) || !(x%47) || !(x%53)) return 0; |
|
|
1968 |
62389 |
!(x%41) || !(x%43) || !(x%47) || !(x%53)) return 0; |
|
1321
|
1011 |
61378 |
if (x < 3481) /* 59*59 */ return 2; |