| line |
true |
false |
branch |
|
73
|
4416 |
552 |
for (i = 8; i >= 1; i--) |
|
101
|
0 |
46 |
if (d > r-2) d = r-2; |
|
102
|
0 |
46 |
if (i > d) i = d; |
|
103
|
0 |
46 |
if (j > (r-2-d)) j = r-2-d; |
|
138
|
0 |
0 |
for (degpx = r-1; degpx > 0 && !px[degpx]; degpx--) ; /* */ |
|
|
0 |
0 |
for (degpx = r-1; degpx > 0 && !px[degpx]; degpx--) ; /* */ |
|
139
|
0 |
0 |
for (degpy = r-1; degpy > 0 && !py[degpy]; degpy--) ; /* */ |
|
|
0 |
0 |
for (degpy = r-1; degpy > 0 && !py[degpy]; degpy--) ; /* */ |
|
141
|
0 |
0 |
j = (mod >= HALF_WORD) ? 0 : (UV_MAX / ((mod-1)*(mod-1))); |
|
143
|
0 |
0 |
if (j >= degpx || j >= degpy) { |
|
|
0 |
0 |
if (j >= degpx || j >= degpy) { |
|
145
|
0 |
0 |
for (rindex = 0; rindex < r; rindex++) { |
|
148
|
0 |
0 |
for (i = 0; i <= degpx; i++) { |
|
149
|
0 |
0 |
if (j <= degpy) |
|
151
|
0 |
0 |
j = (j == 0) ? r-1 : j-1; |
|
157
|
0 |
0 |
for (i = 0; i <= degpx; i++) { |
|
159
|
0 |
0 |
if (pxi == 0) continue; |
|
160
|
0 |
0 |
if (mod < HALF_WORD) { |
|
161
|
0 |
0 |
for (j = 0; j <= degpy; j++) { |
|
163
|
0 |
0 |
rindex = i+j; if (rindex >= r) rindex -= r; |
|
167
|
0 |
0 |
for (j = 0; j <= degpy; j++) { |
|
169
|
0 |
0 |
rindex = i+j; if (rindex >= r) rindex -= r; |
|
185
|
0 |
0 |
for (s = degree; s > 0; s--) |
|
186
|
0 |
0 |
if (px[s] != 0) |
|
190
|
0 |
0 |
for (d = 0; d <= 2*degree; d++) { |
|
192
|
0 |
0 |
UV s_beg = (d <= degree) ? 0 : d-degree; |
|
194
|
0 |
0 |
if (s_end < s_beg) continue; |
|
199
|
0 |
0 |
if (native_sqr) { |
|
200
|
0 |
0 |
while (pp1 < ppend) |
|
204
|
0 |
0 |
sum += (s_end*2 == d) ? c*c : 2*c*px[d-s_end]; |
|
205
|
0 |
0 |
rindex = (d < r) ? d : d-r; /* d % r */ |
|
212
|
0 |
0 |
while (pp1 < ppend) { |
|
214
|
0 |
0 |
if (c128 > max) c128 %= mod; |
|
216
|
0 |
0 |
if (c128 > max) c128 %= mod; |
|
218
|
0 |
0 |
if (sum128 > max) sum128 %= mod; |
|
221
|
0 |
0 |
if (s_end*2 == d) { |
|
225
|
0 |
0 |
if (c128 > max) c128 %= mod; |
|
228
|
0 |
0 |
if (c128 > max) c128 %= mod; |
|
230
|
0 |
0 |
if (sum128 > max) sum128 %= mod; |
|
231
|
0 |
0 |
rindex = (d < r) ? d : d-r; /* d % r */ |
|
257
|
0 |
0 |
Newz(0, res, r, UV); |
|
258
|
0 |
0 |
New(0, temp, r, UV); |
|
261
|
0 |
0 |
while (power) { |
|
262
|
0 |
0 |
if (power & 1) poly_mod_mul(res, pn, temp, r, mod); |
|
264
|
0 |
0 |
if (power) poly_mod_sqr(pn, temp, r, mod); |
|
277
|
0 |
0 |
Newz(0, pn, r, UV); |
|
285
|
0 |
0 |
for (i = 0; i < r; i++) |
|
286
|
0 |
0 |
if (res[i] != 0) |
|
305
|
2 |
5 |
if (n < 2) |
|
307
|
1 |
4 |
if (n == 2) |
|
310
|
0 |
4 |
if (is_power(n, 0)) |
|
313
|
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; |
|
384
|
0 |
4 |
double const r0 = ((log2n > 32) ? 0.010 : 0.003) * log2n * log2n; |
|
385
|
0 |
4 |
UV const rmult = (log2n > 32) ? 6 : 30; |
|
387
|
3 |
1 |
r = next_prime(r0 < 2 ? 2 : (UV)r0); /* r must be at least 3 */ |
|
388
|
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)) ) |
|
394
|
34 |
4 |
while (bi < bj) { |
|
396
|
11 |
23 |
if (!bern41_acceptable(n, r, s)) bi = s+1; |
|
400
|
0 |
4 |
if (!bern41_acceptable(n, r, s)) croak("AKS: bad s selected"); |
|
407
|
0 |
4 |
if (verbose > 1) printf("# aks trial to %lu\n", (unsigned long)slim); |
|
408
|
2 |
2 |
if (trial_factor(n, fac, 2, slim) > 1) |
|
410
|
2 |
0 |
if (slim >= HALF_WORD || (slim*slim) >= n) |
|
|
2 |
0 |
if (slim >= HALF_WORD || (slim*slim) >= n) |
|
413
|
0 |
0 |
for (a = 2; a <= s; a++) { |
|
414
|
0 |
0 |
if (powmod(a, n-1, n) != 1) |
|
420
|
0 |
0 |
if (verbose) { printf("# aks r = %lu s = %lu\n", (unsigned long) r, (unsigned long) s); } |
|
425
|
0 |
0 |
for (a = starta; a <= s; a++) { |
|
426
|
0 |
0 |
if (! test_anr(a, n, r) ) |
|
428
|
0 |
0 |
if (verbose>1) { printf("."); fflush(stdout); } |
|
430
|
0 |
0 |
if (verbose>1) { printf("\n"); } |