| line |
true |
false |
branch |
|
75
|
8928 |
1116 |
for (i = 8; i >= 1; i--) |
|
91
|
0 |
372 |
if (n < k) return 0; |
|
107
|
0 |
93 |
if (d > r-2) d = r-2; |
|
108
|
0 |
93 |
if (i > d) i = d; |
|
109
|
0 |
93 |
if (j > (r-2-d)) j = r-2-d; |
|
144
|
13385 |
55 |
for (degpx = r-1; degpx > 0 && !px[degpx]; degpx--) ; /* */ |
|
|
12900 |
485 |
for (degpx = r-1; degpx > 0 && !px[degpx]; degpx--) ; /* */ |
|
145
|
11705 |
0 |
for (degpy = r-1; degpy > 0 && !py[degpy]; degpy--) ; /* */ |
|
|
11165 |
540 |
for (degpy = r-1; degpy > 0 && !py[degpy]; degpy--) ; /* */ |
|
147
|
540 |
0 |
j = (mod >= HALF_WORD) ? 0 : (UV_MAX / ((mod-1)*(mod-1))); |
|
149
|
225 |
315 |
if (j >= degpx || j >= degpy) { |
|
|
0 |
225 |
if (j >= degpx || j >= degpy) { |
|
151
|
17595 |
315 |
for (rindex = 0; rindex < r; rindex++) { |
|
154
|
290535 |
17595 |
for (i = 0; i <= degpx; i++) { |
|
155
|
206550 |
83985 |
if (j <= degpy) |
|
157
|
4695 |
285840 |
j = (j == 0) ? r-1 : j-1; |
|
163
|
16425 |
225 |
for (i = 0; i <= degpx; i++) { |
|
165
|
0 |
16425 |
if (pxi == 0) continue; |
|
166
|
16425 |
0 |
if (mod < HALF_WORD) { |
|
167
|
1199025 |
16425 |
for (j = 0; j <= degpy; j++) { |
|
169
|
591300 |
607725 |
rindex = i+j; if (rindex >= r) rindex -= r; |
|
173
|
0 |
0 |
for (j = 0; j <= degpy; j++) { |
|
175
|
0 |
0 |
rindex = i+j; if (rindex >= r) rindex -= r; |
|
191
|
18730 |
0 |
for (s = degree; s > 0; s--) |
|
192
|
1435 |
17295 |
if (px[s] != 0) |
|
196
|
192475 |
1435 |
for (d = 0; d <= 2*degree; d++) { |
|
198
|
95520 |
96955 |
UV s_beg = (d <= degree) ? 0 : d-degree; |
|
200
|
17295 |
175180 |
if (s_end < s_beg) continue; |
|
205
|
2920 |
172260 |
if (native_sqr) { |
|
206
|
7240 |
2920 |
while (pp1 < ppend) |
|
210
|
1360 |
1560 |
sum += (s_end*2 == d) ? c*c : 2*c*px[d-s_end]; |
|
211
|
1230 |
1690 |
rindex = (d < r) ? d : d-r; /* d % r */ |
|
218
|
2816190 |
172260 |
while (pp1 < ppend) { |
|
220
|
0 |
2816190 |
if (c128 > max) c128 %= mod; |
|
222
|
0 |
2816190 |
if (c128 > max) c128 %= mod; |
|
224
|
0 |
2816190 |
if (sum128 > max) sum128 %= mod; |
|
227
|
78300 |
93960 |
if (s_end*2 == d) { |
|
231
|
0 |
93960 |
if (c128 > max) c128 %= mod; |
|
234
|
0 |
172260 |
if (c128 > max) c128 %= mod; |
|
236
|
0 |
172260 |
if (sum128 > max) sum128 %= mod; |
|
237
|
76995 |
95265 |
rindex = (d < r) ? d : d-r; /* d % r */ |
|
263
|
0 |
55 |
Newz(0, res, r, UV); |
|
264
|
0 |
55 |
New(0, temp, r, UV); |
|
267
|
1490 |
55 |
while (power) { |
|
268
|
540 |
950 |
if (power & 1) poly_mod_mul(res, pn, temp, r, mod); |
|
270
|
1435 |
55 |
if (power) poly_mod_sqr(pn, temp, r, mod); |
|
283
|
0 |
55 |
Newz(0, pn, r, UV); |
|
284
|
0 |
55 |
if (a >= n) a %= n; |
|
291
|
3415 |
55 |
for (i = 0; i < r; i++) |
|
292
|
0 |
3415 |
if (res[i] != 0) |
|
310
|
2 |
9 |
if (n < 2) |
|
312
|
1 |
8 |
if (n == 2) |
|
315
|
0 |
8 |
if (powerof(n) > 1) |
|
318
|
8 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
8 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
8 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
8 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
8 |
0 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
|
0 |
8 |
if (n > 11 && ( !(n%2) || !(n%3) || !(n%5) || !(n%7) || !(n%11) )) return 0; |
|
388
|
0 |
8 |
double const r0 = ((log2n > 32) ? 0.010 : 0.003) * log2n * log2n; |
|
389
|
0 |
8 |
UV const rmult = (log2n > 32) ? 6 : 30; |
|
391
|
6 |
2 |
r = next_prime(r0 < 2 ? 2 : (UV)r0); /* r must be at least 3 */ |
|
392
|
39 |
14 |
while ( !is_primitive_root(n,r,1) || !bern41_acceptable(n,r,rmult*(r-1)) ) |
|
|
6 |
8 |
while ( !is_primitive_root(n,r,1) || !bern41_acceptable(n,r,rmult*(r-1)) ) |
|
398
|
71 |
8 |
while (bi < bj) { |
|
400
|
19 |
52 |
if (!bern41_acceptable(n, r, s)) bi = s+1; |
|
404
|
0 |
8 |
if (!bern41_acceptable(n, r, s)) croak("AKS: bad s selected"); |
|
411
|
0 |
8 |
MPUverbose(2, "# aks trial to %lu\n", (unsigned long)slim); |
|
412
|
2 |
6 |
if (trial_factor(n, fac, 2, slim) > 1) |
|
414
|
6 |
0 |
if (slim >= HALF_WORD || (slim*slim) >= n) |
|
|
3 |
3 |
if (slim >= HALF_WORD || (slim*slim) >= n) |
|
417
|
56 |
2 |
for (a = 2; a <= s; a++) { |
|
418
|
1 |
55 |
if (powmod(a, n-1, n) != 1) |
|
424
|
0 |
2 |
MPUverbose(1, "# aks r = %lu s = %lu\n", (unsigned long) r, (unsigned long) s); |
|
429
|
55 |
2 |
for (a = starta; a <= s; a++) { |
|
430
|
0 |
55 |
if (! test_anr(a, n, r) ) |
|
432
|
0 |
55 |
MPUverbose(2, "."); |
|
434
|
0 |
2 |
MPUverbose(2, "\n"); |