| line |
true |
false |
branch |
|
46
|
35 |
84 |
if ((p % 4) == 3) { |
|
49
|
29 |
55 |
if ((p % 8) == 5) { /* Atkin's algorithm. Faster than Legendre. */ |
|
54
|
29 |
0 |
b = mulmod(alpha, mulmod(a, (beta ? beta-1 : p-1), p), p); |
|
57
|
13 |
42 |
if ((p % 16) == 9) { /* Müller's algorithm extending Atkin */ |
|
62
|
10 |
3 |
if (sqrmod(beta,p) != p-1) { |
|
63
|
10 |
10 |
do { d += 2; } while (kronecker_uu(d,p) != -1 && d < p); |
|
|
10 |
0 |
do { d += 2; } while (kronecker_uu(d,p) != -1 && d < p); |
|
67
|
13 |
0 |
b = mulmod(alpha, mulmod(a, mulmod(d,(beta ? beta-1 : p-1),p),p),p); |
|
72
|
42 |
0 |
if ((p & 1) && powmod(a,(p-1)>>1,p) != 1) return 0; |
|
|
16 |
26 |
if ((p & 1) && powmod(a,(p-1)>>1,p) != 1) return 0; |
|
80
|
60 |
26 |
while (kronecker_uu(t, p) != -1) { |
|
82
|
0 |
60 |
if (t == 201) { /* exit if p looks like a composite */ |
|
83
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
|
0 |
0 |
if ((p % 2) == 0 || powmod(2, p-1, p) != 1 || powmod(3, p-1, p) != 1) |
|
85
|
0 |
60 |
} else if (t >= 20000) { /* should never happen */ |
|
94
|
45 |
26 |
while (b != 1) { |
|
96
|
153 |
0 |
for (m = 0; m < r && t != 1; m++) |
|
|
108 |
45 |
for (m = 0; m < r && t != 1; m++) |
|
98
|
0 |
45 |
if (m >= r) break; |
|
189
|
121 |
46 |
if (e == 1) { |
|
190
|
55 |
66 |
if (a >= p) a %= p; |
|
191
|
87 |
34 |
if (p == 2 || a == 0) return a; |
|
|
3 |
84 |
if (p == 2 || a == 0) return a; |
|
193
|
38 |
46 |
if (p-r < r) r = p-r; |
|
194
|
62 |
22 |
return (sqrmod(r,p) == a) ? r : UV_MAX; |
|
200
|
1 |
45 |
if ((a % n) == 0) |
|
203
|
2 |
43 |
if ((a % pk) == 0) { |
|
206
|
1 |
1 |
if (s == UV_MAX) return UV_MAX; |
|
210
|
0 |
43 |
if ((a % p) == 0) |
|
213
|
35 |
8 |
ered = (p > 2 || e < 5) ? (e+1)>>1 : (e+3)>>1; |
|
|
32 |
3 |
ered = (p > 2 || e < 5) ? (e+1)>>1 : (e+3)>>1; |
|
215
|
4 |
39 |
if (s == UV_MAX) return UV_MAX; |
|
217
|
33 |
6 |
np = (p != 2 || (n > (UV_MAX/p))) ? n : n * p; |
|
|
33 |
0 |
np = (p != 2 || (n > (UV_MAX/p))) ? n : n * p; |
|
219
|
14 |
25 |
if (n-r < r) r = n-r; |
|
220
|
10 |
29 |
if (sqrmod(r,n) != (a % n)) return UV_MAX; |
|
229
|
0 |
40 |
if (n == 0) return UV_MAX; |
|
230
|
0 |
40 |
if (a >= n) a %= n; |
|
231
|
40 |
0 |
if (n <= 2 || a <= 1) return a; |
|
|
0 |
40 |
if (n <= 2 || a <= 1) return a; |
|
232
|
7 |
33 |
if (is_perfect_square_ret(a,&root)) return root; |
|
237
|
13 |
20 |
if (r == UV_MAX) return UV_MAX; |
|
238
|
12 |
19 |
for (i = 1; i < nf.nfactors; i++) { |
|
241
|
1 |
11 |
if (s == UV_MAX) return UV_MAX; |
|
270
|
0 |
21 |
if (n == 0) return 0; |
|
271
|
0 |
21 |
if (a >= n) a %= n; |
|
272
|
21 |
0 |
if (n > 2 && a > 1) { |
|
|
12 |
9 |
if (n > 2 && a > 1) { |
|
274
|
10 |
2 |
if (a == 0) return 0; |
|
276
|
11 |
0 |
if (s != 0) *s = a; |
|
280
|
29 |
31 |
if (p-r < r) r = p-r; |
|
281
|
14 |
46 |
if (mulmod(r, r, p) != (a % p)) return 0; |
|
282
|
46 |
0 |
if (s != 0) *s = r; |
|
286
|
0 |
20 |
if (p == 0) return 0; |
|
287
|
0 |
20 |
if (a >= p) a %= p; |
|
288
|
20 |
0 |
if (p <= NSMALL || a <= 1) return _sqrtmod_small_return(s,a,p); |
|
|
0 |
20 |
if (p <= NSMALL || a <= 1) return _sqrtmod_small_return(s,a,p); |
|
294
|
0 |
61 |
if (n == 0) return 0; |
|
295
|
0 |
61 |
if (a >= n) a %= n; |
|
296
|
46 |
15 |
if (n <= NSMALL || a <= 1) return _sqrtmod_small_return(s,a,n); |
|
|
6 |
40 |
if (n <= NSMALL || a <= 1) return _sqrtmod_small_return(s,a,n); |
|
308
|
29 |
79 |
if (k == 2 && p-r < r) r = p-r; |
|
|
2 |
27 |
if (k == 2 && p-r < r) r = p-r; |
|
309
|
38 |
70 |
if (powmod(r, k, p) != (a % p)) return 0; |
|
310
|
70 |
0 |
if (s != 0) *s = r; |
|
321
|
22 |
14 |
for (r = p-1; !(r % k); r /= k) ; |
|
328
|
19 |
14 |
for (T = 2, y = 1; y == 1; T++) { |
|
333
|
8 |
14 |
while (ke != k) { |
|
338
|
5 |
8 |
while (A != 1) { |
|
344
|
14 |
0 |
if (z) *z = t; |
|
362
|
25 |
18 |
for (e = 0, r = p-1; !(r % k); r /= k) e++; |
|
364
|
26 |
18 |
for (x = 2, m = 1; m == 1; x++) { |
|
366
|
23 |
3 |
if (y != 1) |
|
368
|
0 |
26 |
MPUassert(x < p, "bad Tonelli-Shanks input\n"); |
|
381
|
30 |
20 |
for (e = 0, r = p-1; !(r % k); r /= k) e++; |
|
384
|
19 |
1 |
A = (a == 0) ? 0 : mulmod(powmod(x, k, p), modinverse(a, p), p); |
|
386
|
0 |
20 |
if (y == 0 && A != 1) |
|
|
0 |
0 |
if (y == 0 && A != 1) |
|
389
|
9 |
14 |
while (A != 1) { |
|
390
|
11 |
3 |
for (l = 1, T = A; T != 1; l++) { |
|
391
|
6 |
5 |
if (l >= e) return 0; |
|
402
|
0 |
3 |
if (y <= 1) return 0; /* In theory this will never be hit. */ |
|
411
|
0 |
0 |
for (x = 2; m == 1; x++) { |
|
413
|
0 |
0 |
if (y == 1) continue; |
|
423
|
0 |
65 |
if (zeta) *zeta = 1; |
|
424
|
0 |
65 |
if (a >= p) a %= p; |
|
425
|
56 |
9 |
if (a == 0 || (a == 1 && !zeta)) return a; |
|
|
12 |
44 |
if (a == 0 || (a == 1 && !zeta)) return a; |
|
|
12 |
0 |
if (a == 0 || (a == 1 && !zeta)) return a; |
|
429
|
15 |
29 |
if (k == 2) { |
|
430
|
0 |
15 |
if (zeta) *zeta = p-1; |
|
439
|
17 |
12 |
if (g != 1) { |
|
442
|
30 |
5 |
for (i = 0; a != 0 && i < nf.nfactors; i++) { |
|
|
18 |
12 |
for (i = 0; a != 0 && i < nf.nfactors; i++) { |
|
444
|
0 |
18 |
if (zeta) { |
|
451
|
20 |
18 |
while (E-- > 0) |
|
455
|
17 |
12 |
if (g != k) { |
|
523
|
60 |
30 |
if (a >= pe) a %= pe; |
|
525
|
42 |
48 |
if (f == 0) { *re = r; return 1; } |
|
528
|
46 |
2 |
if (d == 0) return 0; /* We need a different base root */ |
|
553
|
34 |
13 |
for (i = 0; i < nf.nfactors; i++) { |
|
557
|
2 |
32 |
if (powmod(r, k, f) != (a%f)) return 0; |
|
559
|
16 |
16 |
if (nf.e[i] > 1) { |
|
561
|
57 |
11 |
for (e = 2; e <= nf.e[i]; e++) { |
|
564
|
26 |
31 |
if (!_hensel_lift(&r, r, a, k, fe)) { |
|
567
|
33 |
13 |
for (t = 1; t < f; t++) { |
|
568
|
13 |
20 |
if (_hensel_lift(&r, r + t*m, a, k, fe)) |
|
572
|
13 |
13 |
if (t >= f) { |
|
574
|
87 |
5 |
for (r = (a % f); r < fe; r += f) |
|
575
|
8 |
79 |
if (powmod(r, k, fe) == afe) |
|
577
|
5 |
8 |
if (r >= fe) return 0; |
|
585
|
0 |
13 |
if (chinese(&g, 0, exp, fac, nf.nfactors) != 1) return 0; |
|
724
|
0 |
0 |
if (p == 0) return 0; |
|
725
|
0 |
0 |
if (a >= p) a %= p; |
|
729
|
0 |
0 |
if (p <= 2 || a <= 1) r = a; |
|
|
0 |
0 |
if (p <= 2 || a <= 1) r = a; |
|
730
|
0 |
0 |
else if (k <= 1) r = (k == 0) ? 1 : a; |
|
|
0 |
0 |
else if (k <= 1) r = (k == 0) ? 1 : a; |
|
731
|
0 |
0 |
else if (k < BITS_PER_WORD && is_power_ret(a,k,&R)) r = R; |
|
|
0 |
0 |
else if (k < BITS_PER_WORD && is_power_ret(a,k,&R)) r = R; |
|
743
|
0 |
108 |
if (n == 0) return 0; |
|
744
|
0 |
108 |
if (a >= n) a %= n; |
|
748
|
107 |
1 |
if (n <= 2 || a <= 1) r = a; |
|
|
14 |
93 |
if (n <= 2 || a <= 1) r = a; |
|
749
|
33 |
60 |
else if (k <= 1) r = (k == 0) ? 1 : a; |
|
|
16 |
17 |
else if (k <= 1) r = (k == 0) ? 1 : a; |
|
750
|
60 |
0 |
else if (k < BITS_PER_WORD && is_power_ret(a,k,&R)) r = R; |
|
|
9 |
51 |
else if (k < BITS_PER_WORD && is_power_ret(a,k,&R)) r = R; |
|
752
|
31 |
20 |
else if (is_prime(n)) r = _rootmod_prime_splitk(a,k,n,0); |
|
778
|
0 |
39 |
if (nr > MAX_ROOTS_RETURNED) croak("Maximum returned roots exceeded"); |
|
779
|
0 |
39 |
New(0, roots, nr, UV); |
|
782
|
130 |
39 |
for (i = 0; i < nr1; i++) { |
|
784
|
238 |
130 |
for (j = 0; j < nr2; j++) { |
|
829
|
37 |
77 |
if ((a % p) == 0) { |
|
830
|
20 |
17 |
if ((a % pk) == 0) { |
|
832
|
11 |
9 |
UV high = (k & 1) ? low * p : low; |
|
833
|
0 |
20 |
if (low > MAX_ROOTS_RETURNED) croak("Maximum returned roots exceeded"); |
|
834
|
0 |
20 |
New(0, roots, low, UV); |
|
835
|
39 |
20 |
for (i = 0; i < low; i++) |
|
841
|
3 |
14 |
if ((a2 % p) != 0) |
|
845
|
5 |
9 |
if (roots2 == 0) return 0; |
|
847
|
0 |
9 |
if (*nroots > MAX_ROOTS_RETURNED) croak("Maximum returned roots exceeded"); |
|
848
|
0 |
9 |
New(0, roots, *nroots, UV); |
|
849
|
19 |
9 |
for (i = 0; i < nr2; i++) |
|
850
|
40 |
19 |
for (j = 0; j < p; j++) |
|
857
|
18 |
59 |
if (q == UV_MAX) return 0; |
|
861
|
42 |
17 |
if (p != 2) { *nroots = 2; } |
|
862
|
5 |
12 |
else if (k == 1) { *nroots = 1; } |
|
863
|
8 |
4 |
else if (k == 2) { *nroots = 2; } |
|
883
|
21 |
79 |
if (roots1 == 0) return 0; |
|
884
|
48 |
31 |
if (nf.nfactors == 1) { |
|
893
|
39 |
31 |
for (i = 0; i < rf.nfactors; i++) { |
|
900
|
4 |
27 |
if (roots2 == 0) { Safefree(roots1); return 0; } |
|
911
|
0 |
34 |
if (n == 0) return 0; |
|
912
|
0 |
34 |
if (a >= n) a %= n; |
|
916
|
2 |
32 |
if (n <= 2) return _one_root(nroots, a); |
|
919
|
25 |
7 |
if (numr > 0) sort_uv_array(roots, numr); |
|
936
|
23 |
26 |
if (a >= p) a %= p; |
|
941
|
45 |
4 |
if (p == 2 || a == 0) return _one_root(nroots, a); |
|
|
1 |
44 |
if (p == 2 || a == 0) return _one_root(nroots, a); |
|
945
|
28 |
16 |
if (g == 1) { |
|
953
|
2 |
14 |
if (powmod(a, (p-1)/g, p) != 1) |
|
957
|
0 |
14 |
if (p == 3) return (k == 2 && a == 1) ? _two_roots(nroots, 1, 2) : 0; |
|
|
0 |
0 |
if (p == 3) return (k == 2 && a == 1) ? _two_roots(nroots, 1, 2) : 0; |
|
|
0 |
0 |
if (p == 3) return (k == 2 && a == 1) ? _two_roots(nroots, 1, 2) : 0; |
|
961
|
14 |
0 |
if (powmod(r,k,p) != a || z == 0) croak("allrootmod: failed to find root"); |
|
|
0 |
14 |
if (powmod(r,k,p) != a || z == 0) croak("allrootmod: failed to find root"); |
|
963
|
0 |
14 |
New(0, roots, k, UV); |
|
965
|
30 |
14 |
for (r2 = mulmod(r, z, p); r2 != r && numr < k; r2 = mulmod(r2, z, p) ) |
|
|
30 |
0 |
for (r2 = mulmod(r, z, p); r2 != r && numr < k; r2 = mulmod(r2, z, p) ) |
|
967
|
0 |
14 |
if (r2 != r) croak("allrootmod: excess roots found"); |
|
985
|
49 |
38 |
if (e == 1) return _allrootmod_prime(nroots, a, k, p); |
|
991
|
2 |
36 |
if ((a % n) == 0) { |
|
996
|
0 |
2 |
New(0, roots, numr, UV); |
|
997
|
8 |
2 |
for (i = 0; i < numr; i++) |
|
1000
|
5 |
31 |
} else if ((a % pk) == 0) { |
|
1007
|
0 |
5 |
New(0, roots, numr, UV); |
|
1008
|
4 |
5 |
for (i = 0; i < nr2; i++) |
|
1009
|
40 |
4 |
for (j = 0; j < pe1; j++) |
|
1013
|
16 |
15 |
} else if ((a % p) != 0) { |
|
1015
|
16 |
0 |
UV np = (n > (UV_MAX/p)) ? n : n*p; |
|
1016
|
2 |
14 |
UV ered = (p > 2 || e < 5) ? (e+1)>>1 : (e+3)>>1; |
|
|
2 |
0 |
UV ered = (p > 2 || e < 5) ? (e+1)>>1 : (e+3)>>1; |
|
1019
|
2 |
14 |
if (k != p) { |
|
1021
|
2 |
2 |
for (j = 0; j < nr2; j++) { |
|
1033
|
30 |
14 |
for (j = 0; j < nr2; j++) { |
|
1037
|
17 |
13 |
if (powmod(r, k, n) == (a % n)) |
|
1043
|
12 |
2 |
if (nr2 > 0) { |
|
1045
|
0 |
12 |
New(0, roots, numr, UV); |
|
1046
|
17 |
12 |
for (j = 0; j < nr2; j++) { |
|
1048
|
59 |
17 |
for (i = 0; i < k; i++) |
|
1055
|
0 |
14 |
if (numr == 2 && roots[0] == roots[1]) |
|
|
0 |
0 |
if (numr == 2 && roots[0] == roots[1]) |
|
1057
|
12 |
2 |
if (numr > 2) { |
|
1059
|
47 |
12 |
for (j = 0, i = 1; i < numr; i++) |
|
1060
|
32 |
15 |
if (roots[j] != roots[i]) |
|
1075
|
37 |
53 |
if (k == 2) return _allsqrtmodfact(nroots, a, nf); |
|
1080
|
18 |
35 |
if (numr == 0) { Safefree(roots); return 0; } |
|
1081
|
13 |
34 |
for (i = 1; i < nf.nfactors; i++) { |
|
1084
|
1 |
12 |
if (nr2 == 0) { Safefree(roots); Safefree(roots2); return 0; } |
|
1089
|
0 |
34 |
MPUassert(N == nf.n, "allrootmod: Incorrect factoring"); |
|
1104
|
0 |
47 |
if (n == 0) return 0; |
|
1105
|
0 |
47 |
if (a >= n) a %= n; |
|
1107
|
46 |
1 |
if (n <= 2 || k == 1) |
|
|
0 |
46 |
if (n <= 2 || k == 1) |
|
1110
|
2 |
44 |
if (k == 0) { |
|
1111
|
1 |
1 |
if (a != 1) return 0; |
|
1112
|
0 |
1 |
if (n > MAX_ROOTS_RETURNED) croak("Maximum returned roots exceeded"); |
|
1113
|
0 |
1 |
New(0, roots, n, UV); |
|
1114
|
13 |
1 |
for (i = 0; i < n; i++) |
|
1123
|
31 |
13 |
if (is_prime(k)) { |
|
1132
|
19 |
5 |
for (i = 1; numr > 0 && i < kfactors; i++) { /* for each prime k */ |
|
|
11 |
8 |
for (i = 1; numr > 0 && i < kfactors; i++) { /* for each prime k */ |
|
1135
|
0 |
11 |
New(0, roots3, allocr, UV); |
|
1136
|
46 |
11 |
for (j = 0; j < numr; j++) { /* get a list from each root */ |
|
1138
|
23 |
23 |
if (nr2 == 0) continue; |
|
1140
|
0 |
23 |
if (nr3 + nr2 > MAX_ROOTS_RETURNED) croak("Maximum returned roots exceeded"); |
|
1141
|
11 |
12 |
if (nr3 + nr2 >= allocr) Renew(roots3, allocr += nr2, UV); |
|
|
0 |
11 |
if (nr3 + nr2 >= allocr) Renew(roots3, allocr += nr2, UV); |
|
1142
|
66 |
23 |
for (t = 0; t < nr2; t++) |
|
1153
|
30 |
14 |
if (numr > 1) |