| line |
true |
false |
branch |
|
75
|
4416 |
552 |
for (i = 8; i >= 1; i--) |
|
106
|
0 |
46 |
if (d > r-2) d = r-2; |
|
107
|
0 |
46 |
if (i > d) i = d; |
|
108
|
0 |
46 |
if (j > (r-2-d)) j = r-2-d; |
|
143
|
0 |
0 |
for (degpx = r-1; degpx > 0 && !px[degpx]; degpx--) ; /* */ |
|
|
0 |
0 |
for (degpx = r-1; degpx > 0 && !px[degpx]; degpx--) ; /* */ |
|
144
|
0 |
0 |
for (degpy = r-1; degpy > 0 && !py[degpy]; degpy--) ; /* */ |
|
|
0 |
0 |
for (degpy = r-1; degpy > 0 && !py[degpy]; degpy--) ; /* */ |
|
146
|
0 |
0 |
j = (mod >= HALF_WORD) ? 0 : (UV_MAX / ((mod-1)*(mod-1))); |
|
148
|
0 |
0 |
if (j >= degpx || j >= degpy) { |
|
|
0 |
0 |
if (j >= degpx || j >= degpy) { |
|
150
|
0 |
0 |
for (rindex = 0; rindex < r; rindex++) { |
|
153
|
0 |
0 |
for (i = 0; i <= degpx; i++) { |
|
154
|
0 |
0 |
if (j <= degpy) |
|
156
|
0 |
0 |
j = (j == 0) ? r-1 : j-1; |
|
162
|
0 |
0 |
for (i = 0; i <= degpx; i++) { |
|
164
|
0 |
0 |
if (pxi == 0) continue; |
|
165
|
0 |
0 |
if (mod < HALF_WORD) { |
|
166
|
0 |
0 |
for (j = 0; j <= degpy; j++) { |
|
168
|
0 |
0 |
rindex = i+j; if (rindex >= r) rindex -= r; |
|
172
|
0 |
0 |
for (j = 0; j <= degpy; j++) { |
|
174
|
0 |
0 |
rindex = i+j; if (rindex >= r) rindex -= r; |
|
190
|
0 |
0 |
for (s = degree; s > 0; s--) |
|
191
|
0 |
0 |
if (px[s] != 0) |
|
195
|
0 |
0 |
for (d = 0; d <= 2*degree; d++) { |
|
197
|
0 |
0 |
UV s_beg = (d <= degree) ? 0 : d-degree; |
|
199
|
0 |
0 |
if (s_end < s_beg) continue; |
|
204
|
0 |
0 |
if (native_sqr) { |
|
205
|
0 |
0 |
while (pp1 < ppend) |
|
209
|
0 |
0 |
sum += (s_end*2 == d) ? c*c : 2*c*px[d-s_end]; |
|
210
|
0 |
0 |
rindex = (d < r) ? d : d-r; /* d % r */ |
|
217
|
0 |
0 |
while (pp1 < ppend) { |
|
219
|
0 |
0 |
if (c128 > max) c128 %= mod; |
|
221
|
0 |
0 |
if (c128 > max) c128 %= mod; |
|
223
|
0 |
0 |
if (sum128 > max) sum128 %= mod; |
|
226
|
0 |
0 |
if (s_end*2 == d) { |
|
230
|
0 |
0 |
if (c128 > max) c128 %= mod; |
|
233
|
0 |
0 |
if (c128 > max) c128 %= mod; |
|
235
|
0 |
0 |
if (sum128 > max) sum128 %= mod; |
|
236
|
0 |
0 |
rindex = (d < r) ? d : d-r; /* d % r */ |
|
262
|
0 |
0 |
Newz(0, res, r, UV); |
|
263
|
0 |
0 |
New(0, temp, r, UV); |
|
266
|
0 |
0 |
while (power) { |
|
267
|
0 |
0 |
if (power & 1) poly_mod_mul(res, pn, temp, r, mod); |
|
269
|
0 |
0 |
if (power) poly_mod_sqr(pn, temp, r, mod); |
|
282
|
0 |
0 |
Newz(0, pn, r, UV); |
|
290
|
0 |
0 |
for (i = 0; i < r; i++) |
|
291
|
0 |
0 |
if (res[i] != 0) |
|
309
|
2 |
5 |
if (n < 2) |
|
311
|
1 |
4 |
if (n == 2) |
|
314
|
0 |
4 |
if (is_power(n, 0)) |
|
317
|
4 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
4 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
4 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
4 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
4 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
0 |
4 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
387
|
0 |
4 |
double const r0 = ((log2n > 32) ? 0.010 : 0.003) * log2n * log2n; |
|
388
|
0 |
4 |
UV const rmult = (log2n > 32) ? 6 : 30; |
|
390
|
3 |
1 |
r = next_prime(r0 < 2 ? 2 : (UV)r0); /* r must be at least 3 */ |
|
391
|
12 |
8 |
while ( !is_primitive_root(n,r,1) || !bern41_acceptable(n,r,rmult*(r-1)) ) |
|
|
4 |
4 |
while ( !is_primitive_root(n,r,1) || !bern41_acceptable(n,r,rmult*(r-1)) ) |
|
397
|
34 |
4 |
while (bi < bj) { |
|
399
|
11 |
23 |
if (!bern41_acceptable(n, r, s)) bi = s+1; |
|
403
|
0 |
4 |
if (!bern41_acceptable(n, r, s)) croak("AKS: bad s selected"); |
|
410
|
0 |
4 |
MPUverbose(2, "# aks trial to %lu\n", (unsigned long)slim); |
|
411
|
2 |
2 |
if (trial_factor(n, fac, 2, slim) > 1) |
|
413
|
2 |
0 |
if (slim >= HALF_WORD || (slim*slim) >= n) |
|
|
2 |
0 |
if (slim >= HALF_WORD || (slim*slim) >= n) |
|
416
|
0 |
0 |
for (a = 2; a <= s; a++) { |
|
417
|
0 |
0 |
if (powmod(a, n-1, n) != 1) |
|
423
|
0 |
0 |
MPUverbose(1, "# aks r = %lu s = %lu\n", (unsigned long) r, (unsigned long) s); |
|
428
|
0 |
0 |
for (a = starta; a <= s; a++) { |
|
429
|
0 |
0 |
if (! test_anr(a, n, r) ) |
|
431
|
0 |
0 |
MPUverbose(2, "."); |
|
433
|
0 |
0 |
MPUverbose(2, "\n"); |