Branch Coverage

primality.c
Criterion Covered Total %
branch 661 1002 65.9


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;