| line |
true |
false |
branch |
|
24
|
12710 |
0 |
if (m <= 0 || (m%2) == 0) return 0; |
|
|
0 |
12710 |
if (m <= 0 || (m%2) == 0) return 0; |
|
25
|
44 |
12666 |
if (in < 0 && (m%4) == 3) j = -j; |
|
|
28 |
16 |
if (in < 0 && (m%4) == 3) j = -j; |
|
26
|
29883 |
12710 |
while (n != 0) { |
|
27
|
25600 |
29883 |
while ((n % 2) == 0) { |
|
29
|
19331 |
6269 |
if ( (m % 8) == 3 || (m % 8) == 5 ) j = -j; |
|
|
10132 |
9199 |
if ( (m % 8) == 3 || (m % 8) == 5 ) j = -j; |
|
32
|
13257 |
16626 |
if ( (n % 4) == 3 && (m % 4) == 3 ) j = -j; |
|
|
2511 |
10746 |
if ( (n % 4) == 3 && (m % 4) == 3 ) j = -j; |
|
35
|
12690 |
20 |
return (m == 1) ? j : 0; |
|
44
|
18 |
12584 |
if (j == 0) { UV g = gcd_ui(D,n); if (g != 1 && g != n) return 0; } |
|
|
18 |
0 |
if (j == 0) { UV g = gcd_ui(D,n); if (g != 1 && g != n) return 0; } |
|
|
17 |
1 |
if (j == 0) { UV g = gcd_ui(D,n); if (g != 1 && g != n) return 0; } |
|
45
|
5597 |
6988 |
if (j == -1) break; |
|
46
|
13 |
6975 |
if (P == (3+20*increment) && is_perfect_square(n)) return 0; |
|
|
0 |
13 |
if (P == (3+20*increment) && is_perfect_square(n)) return 0; |
|
48
|
0 |
6988 |
if (P > 65535) |
|
51
|
0 |
5597 |
if (P >= n) P %= n; /* Never happens with increment < 4 */ |
|
58
|
0 |
105 |
if (n < 3) return (n == 2); |
|
59
|
2 |
103 |
if (!(n&1) && !(a&1)) return 0; |
|
|
0 |
2 |
if (!(n&1) && !(a&1)) return 0; |
|
60
|
0 |
105 |
if (a < 2) croak("Base %"UVuf" is invalid", a); |
|
61
|
0 |
105 |
if (a >= n) { |
|
63
|
0 |
0 |
if (a <= 1) return (a == 1); |
|
64
|
0 |
0 |
if (a == n-1) return !(a & 1); |
|
68
|
103 |
2 |
if (n & 1) { /* The Montgomery code only works for odd n */ |
|
70
|
52 |
51 |
const uint64_t monta = (a == 2) ? mont_get2(n) : mont_geta(a, n); |
|
80
|
0 |
109 |
if (n < 3) return (n == 2); |
|
81
|
0 |
109 |
if (!(n&1)) return 0; |
|
82
|
0 |
109 |
if (a < 2) croak("Base %"UVuf" is invalid", a); |
|
83
|
73 |
36 |
if (a > 2) { |
|
84
|
1 |
72 |
if (a >= n) { |
|
86
|
0 |
1 |
if (a <= 1) return (a == 1); |
|
87
|
1 |
0 |
if (a == n-1) return !(a & 1); |
|
89
|
0 |
72 |
if ((n % a) == 0) return 0; |
|
96
|
23 |
85 |
if (ap != mont1 && ap != n-mont1) return 0; |
|
|
0 |
23 |
if (ap != mont1 && ap != n-mont1) return 0; |
|
97
|
36 |
72 |
if (a == 2) { |
|
99
|
8 |
28 |
return (nmod8 == 1 || nmod8 == 7) ? (ap == mont1) : (ap == n-mont1); |
|
|
3 |
5 |
return (nmod8 == 1 || nmod8 == 7) ? (ap == mont1) : (ap == n-mont1); |
|
101
|
54 |
18 |
return (kronecker_uu(a,n) >= 0) ? (ap == mont1) : (ap == n-mont1); |
|
124
|
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); |
|
125
|
0 |
1195 |
if (!(n&1)) return 0; |
|
130
|
314 |
881 |
ap = mont_powmod(mont2, (n-1) >> (1 + (nmod8 == 1)), n); |
|
131
|
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); |
|
132
|
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); |
|
146
|
0 |
301508 |
if (n < 3) return (n == 2); |
|
147
|
1 |
301507 |
if (!(n&1)) return 0; |
|
148
|
2 |
301505 |
if (a < 2) croak("Base %"UVuf" is invalid", a); |
|
149
|
6496 |
295009 |
if (a >= n) a %= n; |
|
150
|
301461 |
44 |
if (a <= 1 || a == n-1) return 1; |
|
|
11 |
301450 |
if (a <= 1 || a == n-1) return 1; |
|
152
|
611735 |
301450 |
while (!(d&1)) { s++; d >>= 1; } |
|
164
|
0 |
301450 |
if (!ma) return 1; |
|
166
|
245403 |
56047 |
if (mx != mont1 && mx != n-mont1) { |
|
|
191821 |
53582 |
if (mx != mont1 && mx != n-mont1) { |
|
167
|
253467 |
135335 |
for (r = 1; r < s; r++) { |
|
168
|
0 |
253467 |
mx = mont_sqrmod(mx, n); |
|
169
|
56379 |
197088 |
if (mx == n-mont1) break; |
|
170
|
107 |
196981 |
if (mx == mont1 ) return 0; |
|
172
|
135335 |
56379 |
if (r >= s) return 0; |
|
200
|
0 |
0 |
for (i = 0; i < nbases; i++) |
|
201
|
0 |
0 |
if (!is_strong_pseudoprime(n, bases[i])) |
|
209
|
0 |
7918 |
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); |
|
210
|
7918 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
7918 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
224
|
16169 |
7918 |
while (!(u&1)) { t++; u >>= 1; } |
|
226
|
6615 |
1303 |
if (md != mont1 && md != n-mont1) { |
|
|
5334 |
1281 |
if (md != mont1 && md != n-mont1) { |
|
227
|
6216 |
3547 |
for (i=1; i
|
|
228
|
67 |
6149 |
md = mont_sqrmod(md, n); |
|
229
|
10 |
6206 |
if (md == mont1) return 0; |
|
230
|
1777 |
4429 |
if (md == n-mont1) break; |
|
232
|
3547 |
1777 |
if (i == t) |
|
237
|
0 |
4361 |
if (P == 0) return 0; |
|
241
|
8910 |
4361 |
while ( (d & 1) == 0 ) { s++; d >>= 1; } |
|
246
|
64 |
4297 |
W = submod( mont_mulmod( montP, montP, n), mont2, n); |
|
248
|
206526 |
4361 |
{ UV v = d; b = 1; while (v >>= 1) b++; } |
|
249
|
206526 |
4361 |
while (b-- > 1) { |
|
250
|
3906 |
202620 |
UV T = submod( mont_mulmod(V, W, n), montP, n); |
|
251
|
110493 |
96033 |
if ( (d >> (b-1)) & UVCONST(1) ) { |
|
253
|
2043 |
108450 |
W = submod( mont_mulmod(W, W, n), mont2, n); |
|
256
|
1863 |
94170 |
V = submod( mont_mulmod(V, V, n), mont2, n); |
|
261
|
3953 |
408 |
if (V == mont2 || V == (n-mont2)) |
|
|
2008 |
1945 |
if (V == mont2 || V == (n-mont2)) |
|
263
|
4277 |
21 |
while (s-- > 1) { |
|
264
|
1924 |
2353 |
if (V == 0) |
|
266
|
33 |
2320 |
V = submod( mont_mulmod(V, V, n), mont2, n); |
|
267
|
0 |
2353 |
if (V == mont2) |
|
294
|
4 |
166 |
if (n < 5) return (n == 2 || n == 3); |
|
|
2 |
2 |
if (n < 5) return (n == 2 || n == 3); |
|
|
1 |
1 |
if (n < 5) return (n == 2 || n == 3); |
|
295
|
113 |
53 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
113 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
297
|
43 |
70 |
if (strength < 3) { |
|
304
|
44 |
64 |
if (j != 1 && Du != n) break; |
|
|
43 |
1 |
if (j != 1 && Du != n) break; |
|
305
|
0 |
65 |
if (Du == 21 && is_perfect_square(n)) return 0; |
|
|
0 |
0 |
if (Du == 21 && is_perfect_square(n)) return 0; |
|
309
|
1 |
42 |
if (j != -1) return 0; |
|
312
|
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* */ |
|
314
|
22 |
20 |
Qk = (Q >= 0) ? Q % n : n-(((UV)(-Q)) % n); |
|
315
|
0 |
42 |
if (gcd_ui(Qk,n) != 1) return 0; |
|
318
|
17 |
53 |
if (P == 0) return 0; |
|
322
|
0 |
95 |
MPUassert( D == (P*P - 4*Q) , "is_lucas_pseudoprime: incorrect DPQ"); |
|
333
|
72 |
23 |
if (strength > 0) |
|
334
|
147 |
72 |
while ( (d & 1) == 0 ) { s++; d >>= 1; } |
|
341
|
53 |
42 |
: (P >= 0) ? mont_geta(P, n) |
|
342
|
53 |
0 |
: n - mont_geta(-P, n); |
|
344
|
42 |
53 |
: (Q >= 0) ? mont_geta(Q, n) |
|
345
|
22 |
20 |
: n - mont_geta(-Q, n); |
|
347
|
73 |
22 |
: n - mont_geta(-D, n); |
|
349
|
1039 |
95 |
{ UV v = d; b = 0; while (v >>= 1) b++; } |
|
355
|
42 |
53 |
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 */ |
|
357
|
674 |
69 |
while (b--) { |
|
358
|
0 |
674 |
U = mont_mulmod(U, V, n); |
|
359
|
572 |
102 |
if (sign == 1) V = submod( mont_sqrmod(V,n), mont2, n); |
|
|
0 |
572 |
if (sign == 1) V = submod( mont_sqrmod(V,n), mont2, n); |
|
360
|
0 |
102 |
else V = addmod( mont_sqrmod(V,n), mont2, n); |
|
362
|
295 |
379 |
if ( (d >> b) & UVCONST(1) ) { |
|
363
|
0 |
295 |
UV t2 = mont_mulmod(U, montD, n); |
|
364
|
92 |
203 |
if (P == 1) { |
|
368
|
0 |
203 |
U = addmod( mont_mulmod(U, montP, n), V, n); |
|
369
|
0 |
203 |
V = addmod( mont_mulmod(V, montP, n), t2, n); |
|
371
|
125 |
170 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
372
|
149 |
146 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
376
|
6 |
63 |
Qk = (sign == 1) ? mont1 : n-mont1; |
|
379
|
365 |
26 |
while (b--) { |
|
380
|
0 |
365 |
U = mont_mulmod(U, V, n); |
|
381
|
0 |
365 |
V = submod( mont_sqrmod(V,n), addmod(Qk,Qk,n), n); |
|
382
|
0 |
365 |
Qk = mont_sqrmod(Qk,n); |
|
383
|
186 |
179 |
if ( (d >> b) & UVCONST(1) ) { |
|
384
|
0 |
186 |
UV t2 = mont_mulmod(U, montD, n); |
|
385
|
0 |
186 |
U = addmod( mont_mulmod(U, montP, n), V, n); |
|
386
|
84 |
102 |
if (U & 1) { U = (n>>1) + (U>>1) + 1; } else { U >>= 1; } |
|
387
|
0 |
186 |
V = addmod( mont_mulmod(V, montP, n), t2, n); |
|
388
|
102 |
84 |
if (V & 1) { V = (n>>1) + (V>>1) + 1; } else { V >>= 1; } |
|
389
|
0 |
186 |
Qk = mont_mulmod(Qk, montQ, n); |
|
394
|
23 |
72 |
if (strength == 0) { |
|
395
|
20 |
3 |
if (U == 0) |
|
397
|
19 |
53 |
} else if (strength == 1) { |
|
398
|
8 |
11 |
if (U == 0) |
|
400
|
23 |
0 |
while (s--) { |
|
401
|
11 |
12 |
if (V == 0) |
|
403
|
12 |
0 |
if (s) { |
|
404
|
0 |
12 |
V = submod( mont_sqrmod(V,n), addmod(Qk,Qk,n), n); |
|
405
|
0 |
12 |
Qk = mont_sqrmod(Qk,n); |
|
408
|
0 |
53 |
} else if (strength == 2) { |
|
411
|
0 |
0 |
if (U == 0) |
|
413
|
0 |
0 |
while (s--) { |
|
414
|
0 |
0 |
if (V == 0) |
|
417
|
0 |
0 |
V = submod( mont_sqrmod(V,n), addmod(Qk,Qk,n), n); |
|
418
|
0 |
0 |
Qk = mont_sqrmod(Qk,n); |
|
420
|
0 |
0 |
if (!is_slpsp) return 0; /* slpsp */ |
|
421
|
0 |
0 |
if (V != addmod(montQ,montQ,n)) return 0; /* V_{n+1} != 2Q mod n */ |
|
423
|
0 |
0 |
Qj = (qjacobi == 0) ? 0 : (qjacobi == 1) ? montQ : n-montQ; |
|
|
0 |
0 |
Qj = (qjacobi == 0) ? 0 : (qjacobi == 1) ? montQ : n-montQ; |
|
424
|
0 |
0 |
if (Ql != Qj) return 0; /* n is epsp base Q */ |
|
427
|
26 |
27 |
if ( U == 0 && (V == mont2 || V == (n-mont2)) ) |
|
|
20 |
6 |
if ( U == 0 && (V == mont2 || V == (n-mont2)) ) |
|
|
20 |
0 |
if ( U == 0 && (V == mont2 || V == (n-mont2)) ) |
|
430
|
50 |
8 |
while (s--) { |
|
431
|
19 |
31 |
if (V == 0) |
|
433
|
27 |
4 |
if (s) |
|
434
|
0 |
27 |
V = submod( mont_sqrmod(V,n), mont2, n); |
|
513
|
0 |
1183 |
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); |
|
514
|
1183 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
1183 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
515
|
1183 |
0 |
if (increment < 1 || increment > 256) |
|
|
0 |
1183 |
if (increment < 1 || increment > 256) |
|
519
|
0 |
1183 |
if ( (increment >= 16 && n <= 331) || (increment > 148 && n <= 631) ) |
|
|
0 |
0 |
if ( (increment >= 16 && n <= 331) || (increment > 148 && n <= 631) ) |
|
|
0 |
1183 |
if ( (increment >= 16 && n <= 331) || (increment > 148 && n <= 631) ) |
|
|
0 |
0 |
if ( (increment >= 16 && n <= 331) || (increment > 148 && n <= 631) ) |
|
523
|
0 |
1183 |
if (P == 0) return 0; |
|
527
|
2350 |
1183 |
while ( (d & 1) == 0 ) { s++; d >>= 1; } |
|
528
|
18192 |
1183 |
{ UV v = d; b = 0; while (v >>= 1) b++; } |
|
535
|
0 |
1183 |
W = submod( mont_mulmod( montP, montP, n), mont2, n); |
|
537
|
18192 |
1183 |
while (b--) { |
|
538
|
0 |
18192 |
UV T = submod( mont_mulmod(V, W, n), montP, n); |
|
539
|
9362 |
8830 |
if ( (d >> b) & UVCONST(1) ) { |
|
541
|
0 |
9362 |
W = submod( mont_mulmod(W, W, n), mont2, n); |
|
544
|
0 |
8830 |
V = submod( mont_mulmod(V, V, n), mont2, n); |
|
548
|
1052 |
131 |
if (V == mont2 || V == (n-mont2)) |
|
|
552 |
500 |
if (V == mont2 || V == (n-mont2)) |
|
551
|
1077 |
0 |
while (s--) { |
|
552
|
500 |
577 |
if (V == 0) |
|
554
|
577 |
0 |
if (s) |
|
555
|
0 |
577 |
V = submod( mont_mulmod(V, V, n), mont2, n); |
|
627
|
0 |
20 |
if (n <= 1) return; |
|
630
|
18 |
2 |
if ( (n&1) ) { |
|
639
|
551 |
20 |
{ UV v = n; b = 1; while (v >>= 1) b++; } |
|
641
|
551 |
20 |
while (b-- > 1) { |
|
644
|
504 |
47 |
if (n&1) { |
|
645
|
0 |
504 |
T[0] = submod(submod(mont_sqrmod(S[0],n), S[5],n), S[5],n); |
|
646
|
0 |
504 |
T[1] = submod(submod(mont_sqrmod(S[1],n), S[4],n), S[4],n); |
|
647
|
0 |
504 |
T[2] = submod(submod(mont_sqrmod(S[2],n), S[3],n), S[3],n); |
|
648
|
0 |
504 |
T[3] = submod(submod(mont_sqrmod(S[3],n), S[2],n), S[2],n); |
|
649
|
0 |
504 |
T[4] = submod(submod(mont_sqrmod(S[4],n), S[1],n), S[1],n); |
|
650
|
0 |
504 |
T[5] = submod(submod(mont_sqrmod(S[5],n), S[0],n), S[0],n); |
|
665
|
245 |
306 |
if ( (n >> (b-1)) & 1U ) { |
|
674
|
18 |
2 |
if (n&1) { /* Recover result from Montgomery form */ |
|
675
|
108 |
18 |
for (i = 0; i < 6; i++) |
|
676
|
0 |
108 |
S[i] = mont_recover(S[i],n); |
|
686
|
0 |
20 |
if (n < 3) return (n >= 2); |
|
687
|
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 */ |
|
692
|
2 |
18 |
if (!(n32&1) && !(( 22 >> (n32% 7)) & 1)) return 0; |
|
|
0 |
2 |
if (!(n32&1) && !(( 22 >> (n32% 7)) & 1)) return 0; |
|
693
|
0 |
20 |
if (!(n32%3) && !(( 523 >> (n32%13)) & 1)) return 0; |
|
|
0 |
0 |
if (!(n32%3) && !(( 523 >> (n32%13)) & 1)) return 0; |
|
694
|
2 |
18 |
if (!(n32%5) && !((65890 >> (n32%24)) & 1)) return 0; |
|
|
0 |
2 |
if (!(n32%5) && !((65890 >> (n32%24)) & 1)) return 0; |
|
695
|
0 |
20 |
if (!(n32%4) && !(( 514 >> (n32%14)) & 1)) return 0; |
|
|
0 |
0 |
if (!(n32%4) && !(( 514 >> (n32%14)) & 1)) return 0; |
|
697
|
300 |
20 |
for (i = 4; i < NPERRINDIV; i++) { |
|
698
|
12 |
288 |
if ((n % _perrindata[i].div) == 0) { |
|
701
|
0 |
12 |
if (!((mask[mod/32] >> (mod%32)) & 1)) |
|
709
|
0 |
20 |
if (S[4] != 0) return 0; /* P(n) = 0 mod n */ |
|
710
|
15 |
5 |
if (restricted == 0) return 1; |
|
712
|
1 |
4 |
if (S[1] != n-1) return 0; /* P(-n) = -1 mod n */ |
|
713
|
1 |
3 |
if (restricted == 1) return 1; |
|
729
|
1 |
2 |
if (jacobi == -1) { /* Q-type */ |
|
734
|
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 && |
|
735
|
0 |
0 |
B != 3 && submod(mulmod(B2,B,n),B,n) == 1) { |
|
736
|
0 |
0 |
MPUverbose(2, "%"UVuf" Q-Type %"UVuf" -1 %"UVuf" %"UVuf" 0 %"UVuf"\n", n, A, B, B, C); |
|
742
|
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) { |
|
743
|
0 |
1 |
MPUverbose(2, "%"UVuf" Jacobi %d\n",n,jacobi); |
|
747
|
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) { |
|
748
|
0 |
1 |
MPUverbose(2, "%"UVuf" S-Type 1 -1 3 3 0 2\n",n); |
|
750
|
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] && |
|
|
0 |
0 |
} else if (S[0] == 0 && S[5] == n-1 && S[2] != S[3] && |
|
751
|
0 |
0 |
addmod(S[2],S[3],n) == n-3 && sqrmod(submod(S[2],S[3],n),n) == n-(23%n)) { |
|
|
0 |
0 |
addmod(S[2],S[3],n) == n-3 && sqrmod(submod(S[2],S[3],n),n) == n-(23%n)) { |
|
752
|
0 |
0 |
MPUverbose(2, "%"UVuf" I-Type 0 -1 %"UVuf" %"UVuf" 0 -1\n",n, S[2], S[3]); |
|
757
|
0 |
1 |
MPUverbose(2, "%"UVuf" ? %2d ? %"UVuf" -1 %"UVuf" %"UVuf" 0 %"UVuf"\n", n, jacobi, S[0],S[2],S[3],S[5]); |
|
768
|
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); |
|
769
|
28 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
28 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
771
|
0 |
28 |
if (P == 0 && Q == 0) { |
|
|
0 |
0 |
if (P == 0 && Q == 0) { |
|
773
|
0 |
0 |
if (n == 7) P = 1; /* So we don't test kronecker(-7,7) */ |
|
776
|
0 |
0 |
if (P == 3) P = 5; /* P=3,Q=2 -> D=9-8=1 => k=1, so skip */ |
|
780
|
0 |
0 |
if (P == 10001 && is_perfect_square(n)) return 0; |
|
|
0 |
0 |
if (P == 10001 && is_perfect_square(n)) return 0; |
|
781
|
0 |
0 |
} while (k == 1); |
|
782
|
0 |
0 |
if (k == 0) return 0; |
|
784
|
0 |
0 |
MPUverbose(1, "%"UVuf" Frobenius (%"IVdf",%"IVdf") : x^2 - %"IVdf"x + %"IVdf"\n", n, P, Q, P, Q); |
|
789
|
11 |
17 |
if (D != 5 && is_perfect_square(Du)) |
|
|
0 |
11 |
if (D != 5 && is_perfect_square(Du)) |
|
796
|
0 |
28 |
if (t != 1) { |
|
797
|
0 |
0 |
if (t == n) return is_prob_prime(n); |
|
800
|
28 |
0 |
if (k == 0) { |
|
802
|
0 |
28 |
if (k == 0) return 0; |
|
803
|
4 |
24 |
Vcomp = (k == 1) ? 2 : addmod(Qu,Qu,n); |
|
808
|
28 |
0 |
if (U == 0 && V == Vcomp) return 1; |
|
|
28 |
0 |
if (U == 0 && V == Vcomp) return 1; |
|
831
|
48 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
48 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
48 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
48 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
832
|
0 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
833
|
0 |
0 |
if (is_perfect_square(n)) return 0; |
|
835
|
0 |
0 |
if (n % 4 == 3) c = d; |
|
836
|
0 |
0 |
else if (n % 8 == 5) c = 2; |
|
840
|
0 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
0 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
0 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
0 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
0 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
0 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
|
0 |
0 |
if (c==9 || (c>=15 && (!(c%3) || !(c%5) || !(c%7) || !(c%11) || !(c%13)))) |
|
843
|
0 |
0 |
} while (k == 1); |
|
844
|
0 |
0 |
if (k == 0 || (k == 2 && n % 3 == 0)) return 0; |
|
|
0 |
0 |
if (k == 0 || (k == 2 && n % 3 == 0)) return 0; |
|
|
0 |
0 |
if (k == 0 || (k == 2 && n % 3 == 0)) return 0; |
|
851
|
0 |
0 |
ra = a = ea = (k == 2) ? mont_get2(n) : mont1; |
|
853
|
0 |
0 |
while (d) { |
|
854
|
0 |
0 |
if (d & 1) { |
|
856
|
0 |
0 |
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 |
0 |
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 ); |
|
857
|
0 |
0 |
rb = addmod( mont_mulmod(tb,a,n), mont_mulmod(ta,b,n), n); |
|
|
0 |
0 |
rb = addmod( mont_mulmod(tb,a,n), mont_mulmod(ta,b,n), n); |
|
860
|
0 |
0 |
if (d) { |
|
861
|
0 |
0 |
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 |
0 |
UV t = mont_mulmod(mont_mulmod(b,b,n),montc,n); |
|
862
|
0 |
0 |
b = mont_mulmod(b,a,n); |
|
864
|
0 |
0 |
a = addmod(mont_mulmod(a,a,n),t,n); |
|
867
|
0 |
0 |
return (ra == ea && rb == n-mont1); |
|
|
0 |
0 |
return (ra == ea && rb == n-mont1); |
|
908
|
48 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
48 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
48 |
0 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
|
0 |
48 |
if (n < 7) return (n == 2 || n == 3 || n == 5); |
|
909
|
0 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
|
0 |
0 |
if ((n % 2) == 0 || n == UV_MAX) return 0; |
|
911
|
0 |
0 |
for (x = 0; x < 1000000; x++) { |
|
912
|
0 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
0 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
0 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
0 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
0 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
0 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
0 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
|
0 |
0 |
if (x==2 || x==4 || x==7 || x==8 || x==10 || x==14 || x==16 || x==18) |
|
916
|
0 |
0 |
if (j == -1) break; |
|
917
|
0 |
0 |
if (j == 0 || (x == 20 && is_perfect_square(n))) |
|
|
0 |
0 |
if (j == 0 || (x == 20 && is_perfect_square(n))) |
|
|
0 |
0 |
if (j == 0 || (x == 20 && is_perfect_square(n))) |
|
920
|
0 |
0 |
if (x >= 1000000) croak("FU test failure, unable to find suitable a"); |
|
922
|
0 |
0 |
if (t1 != 1 && t1 != n) |
|
|
0 |
0 |
if (t1 != 1 && t1 != n) |
|
925
|
0 |
0 |
{ UV v = np1; len = 1; while (v >>= 1) len++; } |
|
937
|
0 |
0 |
if (x == 0) { |
|
939
|
0 |
0 |
for (bit = len-2; bit >= 0; bit--) { |
|
941
|
0 |
0 |
b = mont_mulmod(submod(b, a, n), addmod(b, a, n), n); |
|
942
|
0 |
0 |
a = mont_mulmod(a, t1, n); |
|
943
|
0 |
0 |
if ( (np1 >> bit) & UVCONST(1) ) { |
|
952
|
0 |
0 |
for (bit = len-2; bit >= 0; bit--) { |
|
953
|
0 |
0 |
t1 = addmod( mont_mulmod(a, x, n), addmod(b, b, n), n); |
|
954
|
0 |
0 |
b = mont_mulmod(submod(b, a, n), addmod(b, a, n), n); |
|
955
|
0 |
0 |
a = mont_mulmod(a, t1, n); |
|
956
|
0 |
0 |
if ( (np1 >> bit) & UVCONST(1) ) { |
|
959
|
0 |
0 |
a = addmod( mont_mulmod(a, multiplier, n), t1, n); |
|
963
|
0 |
0 |
return (a == 0 && b == result); |
|
|
0 |
0 |
return (a == 0 && b == result); |
|
1014
|
118238 |
2270 |
for (i = 0; i < NUM_KNOWN_MERSENNE_PRIMES; i++) |
|
1015
|
26 |
118212 |
if (p == _mersenne_primes[i]) |
|
1017
|
2270 |
0 |
return (p < LAST_CHECKED_MERSENNE) ? 0 : -1; |
|
1023
|
0 |
0 |
if (p == 2) return 1; |
|
1024
|
0 |
0 |
if (!is_prob_prime(p)) return 0; |
|
1025
|
0 |
0 |
if (p > BITS_PER_WORD) croak("lucas_lehmer with p > BITS_PER_WORD"); |
|
1028
|
0 |
0 |
for (k = 3; k <= p; k++) { |
|
1063
|
5 |
12793 |
if (n < 11) return 0xAC >> n & 1; /* equal to 2, 3, 5 or 7 */ |
|
1064
|
12793 |
0 |
if (is_divis_2_3_5(n)) return 0; /* divis by 2, 3, or 5 */ |
|
|
12793 |
0 |
if (is_divis_2_3_5(n)) return 0; /* divis by 2, 3, or 5 */ |
|
|
0 |
12793 |
if (is_divis_2_3_5(n)) return 0; /* divis by 2, 3, or 5 */ |
|
1096
|
3714 |
543432 |
if (n > UVCONST(4294967295)) { /* input is >= 2^32, UV is 64-bit*/ |
|
1097
|
3686 |
28 |
if (is_divis_2_3_5_7(n)) return 0; |
|
|
2371 |
1315 |
if (is_divis_2_3_5_7(n)) return 0; |
|
|
1918 |
453 |
if (is_divis_2_3_5_7(n)) return 0; |
|
|
225 |
1693 |
if (is_divis_2_3_5_7(n)) return 0; |
|
1098
|
1542 |
151 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
|
1433 |
109 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
|
1349 |
84 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
|
1279 |
70 |
if (!(n%11) || !(n%13) || !(n%17) || !(n%19) || |
|
1099
|
1219 |
60 |
!(n%23) || !(n%29) || !(n%31) || !(n%37) || |
|
|
1186 |
33 |
!(n%23) || !(n%29) || !(n%31) || !(n%37) || |
|
|
1148 |
38 |
!(n%23) || !(n%29) || !(n%31) || !(n%37) || |
|
|
1104 |
44 |
!(n%23) || !(n%29) || !(n%31) || !(n%37) || |
|
1100
|
1078 |
26 |
!(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; |
|
|
1056 |
22 |
!(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; |
|
|
1039 |
17 |
!(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; |
|
|
18 |
1021 |
!(n%41) || !(n%43) || !(n%47) || !(n%53)) return 0; |
|
1101
|
1004 |
17 |
if (!(n%59) || !(n%61) || !(n%67) || !(n%71)) return 0; |
|
|
987 |
17 |
if (!(n%59) || !(n%61) || !(n%67) || !(n%71)) return 0; |
|
|
970 |
17 |
if (!(n%59) || !(n%61) || !(n%67) || !(n%71)) return 0; |
|
|
12 |
958 |
if (!(n%59) || !(n%61) || !(n%67) || !(n%71)) return 0; |
|
1102
|
947 |
11 |
if (!(n%73) || !(n%79) || !(n%83) || !(n%89)) return 0; |
|
|
936 |
11 |
if (!(n%73) || !(n%79) || !(n%83) || !(n%89)) return 0; |
|
|
926 |
10 |
if (!(n%73) || !(n%79) || !(n%83) || !(n%89)) return 0; |
|
|
7 |
919 |
if (!(n%73) || !(n%79) || !(n%83) || !(n%89)) return 0; |
|
1111
|
4381 |
539051 |
if (x < 11) return 0xAC >> x & 1; /* Bits 2, 3, 5 and 7 */ |
|
1113
|
521669 |
17382 |
if (is_divis_2_3_5_7(x)) return 0; |
|
|
505208 |
16461 |
if (is_divis_2_3_5_7(x)) return 0; |
|
|
497686 |
7522 |
if (is_divis_2_3_5_7(x)) return 0; |
|
|
5547 |
492139 |
if (is_divis_2_3_5_7(x)) return 0; |
|
1114
|
2095 |
490044 |
if (x < 121) /* 11*11 */ return 1; |
|
1116
|
445254 |
44790 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
|
411203 |
34051 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
|
386326 |
24877 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
|
365158 |
21168 |
if (!(x%11) || !(x%13) || !(x%17) || !(x%19) || |
|
1117
|
349385 |
15773 |
!(x%23) || !(x%29) || !(x%31) || !(x%37) || |
|
|
337480 |
11905 |
!(x%23) || !(x%29) || !(x%31) || !(x%37) || |
|
|
326965 |
10515 |
!(x%23) || !(x%29) || !(x%31) || !(x%37) || |
|
|
318298 |
8667 |
!(x%23) || !(x%29) || !(x%31) || !(x%37) || |
|
1118
|
310692 |
7606 |
!(x%41) || !(x%43) || !(x%47) || !(x%53)) return 0; |
|
|
303658 |
7034 |
!(x%41) || !(x%43) || !(x%47) || !(x%53)) return 0; |
|
|
297624 |
6034 |
!(x%41) || !(x%43) || !(x%47) || !(x%53)) return 0; |
|
|
5303 |
292321 |
!(x%41) || !(x%43) || !(x%47) || !(x%53)) return 0; |
|
1119
|
11993 |
280328 |
if (x < 3481) /* 59*59 */ return 1; |