| line |
true |
false |
branch |
|
61
|
34001 |
151 |
if (n > 1) { |
|
62
|
14603 |
34001 |
while ( (n & 1) == 0 ) { factors[nfactors++] = 2; n /= 2; } |
|
63
|
10405 |
34001 |
while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
64
|
5936 |
34001 |
while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
67
|
27135 |
7017 |
if (f*f <= n) { |
|
71
|
26909 |
226 |
if (n <= 4294967295U) { |
|
73
|
240583 |
222 |
while (sp < lastsp) { |
|
74
|
13320 |
240583 |
while ( (un%f) == 0 ) { |
|
79
|
26687 |
213896 |
if (f*f > un) break; |
|
83
|
17138 |
214 |
while (sp < lastsp) { |
|
84
|
250 |
17138 |
while ( (n%f) == 0 ) { |
|
89
|
12 |
17126 |
if (f*f > n) break; |
|
93
|
26761 |
374 |
if (n < 2011*2011 && f*f <= n) { /* Trial division from 431 to 2003 */ |
|
|
62 |
26699 |
if (n < 2011*2011 && f*f <= n) { /* Trial division from 431 to 2003 */ |
|
95
|
5698 |
0 |
while (sp < NPRIMES_SMALL) { |
|
96
|
21 |
5698 |
while ( (un%f) == 0 ) { |
|
101
|
62 |
5636 |
if (f*f > un) break; |
|
106
|
33778 |
374 |
if (f*f > n) { |
|
107
|
29851 |
3927 |
if (n != 1) factors[nfactors++] = n; |
|
112
|
112 |
262 |
if (n < 100000000 && n < f*f*f) { |
|
|
108 |
4 |
if (n < 100000000 && n < f*f*f) { |
|
113
|
54 |
54 |
if (MR32(n)) factors[nfactors++] = n; |
|
124
|
5 |
261 |
if (k > 1) { |
|
127
|
12 |
5 |
for (i = nfactors; i >= 0; i--) |
|
128
|
26 |
12 |
for (j = 0; j < k; j++) |
|
141
|
480 |
249 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
130 |
350 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
40 |
90 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
194 |
156 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
144
|
234 |
0 |
UV const nbits = BITS_PER_WORD - clz(n); |
|
146
|
99 |
135 |
UV const br_rounds = 8000 + (9000 * ((nbits <= 45) ? 0 : (nbits-45))); |
|
160
|
234 |
0 |
if (!split_success && nbits <= 30) { /* This should always succeed */ |
|
|
37 |
197 |
if (!split_success && nbits <= 30) { /* This should always succeed */ |
|
162
|
0 |
37 |
if (verbose) printf("holf %d\n", split_success); |
|
166
|
197 |
37 |
if (!split_success && br_rounds > 0) { |
|
|
197 |
0 |
if (!split_success && br_rounds > 0) { |
|
168
|
0 |
197 |
if (verbose) printf("pbrent %d\n", split_success); |
|
171
|
0 |
234 |
if (!split_success) { |
|
173
|
0 |
0 |
if (verbose) printf("second pbrent %d\n", split_success); |
|
183
|
0 |
234 |
if (!split_success && nbits <= 62) { |
|
|
0 |
0 |
if (!split_success && nbits <= 62) { |
|
185
|
0 |
0 |
if (verbose) printf("squfof %d\n", split_success); |
|
188
|
0 |
234 |
if (!split_success) { |
|
190
|
0 |
0 |
if (verbose) printf("pminus1 %d\n", split_success); |
|
192
|
0 |
0 |
if (!split_success) { |
|
194
|
0 |
0 |
if (verbose) printf("long prho %d\n", split_success); |
|
195
|
0 |
0 |
if (!split_success) { |
|
197
|
0 |
0 |
if (verbose) printf("long pbrent %d\n", split_success); |
|
202
|
234 |
0 |
if (split_success) { |
|
203
|
0 |
234 |
MPUassert( split_success == 1, "split factor returned more than 2 factors"); |
|
205
|
234 |
0 |
if ((tofac_stack[ntofac] == n) || (tofac_stack[ntofac] == 1)) |
|
|
0 |
234 |
if ((tofac_stack[ntofac] == n) || (tofac_stack[ntofac] == 1)) |
|
212
|
0 |
0 |
if (verbose) printf("doing trial on %"UVuf"\n", n); |
|
213
|
0 |
0 |
while (f <= limit) { |
|
214
|
0 |
0 |
if ( (n%f) == 0 ) { |
|
218
|
0 |
0 |
} while ( (n%f) == 0 ); |
|
228
|
495 |
0 |
if (n != 1) factors[nfactors++] = n; |
|
230
|
234 |
261 |
if (ntofac > 0) n = tofac_stack[ntofac-1]; |
|
231
|
234 |
261 |
} while (ntofac-- > 0); |
|
234
|
234 |
261 |
for (i = nsmallfactors+1; i < nfactors; i++) { |
|
236
|
462 |
56 |
for (j = i; j > 0 && factors[j-1] > fi; j--) |
|
|
284 |
178 |
for (j = i; j > 0 && factors[j-1] > fi; j--) |
|
249
|
12 |
12695 |
if (n == 1) return 0; |
|
252
|
39 |
12656 |
if (exponents == 0) { |
|
253
|
92 |
39 |
for (; i < nfactors; i++) |
|
254
|
62 |
30 |
if (factors[i] != factors[i-1]) |
|
258
|
16583 |
12656 |
for (; i < nfactors; i++) { |
|
259
|
13080 |
3503 |
if (factors[i] != factors[i-1]) { |
|
275
|
0 |
1619 |
if (f < 2) f = 2; |
|
276
|
1616 |
3 |
if (last == 0 || last*last > n) last = UV_MAX; |
|
|
1010 |
606 |
if (last == 0 || last*last > n) last = UV_MAX; |
|
278
|
1611 |
8 |
if (n < 4 || last < f) { |
|
|
0 |
1611 |
if (n < 4 || last < f) { |
|
285
|
1611 |
0 |
if (f < primes_small[NPRIMES_SMALL-1]) { |
|
286
|
1621 |
1611 |
while ( (n & 1) == 0 ) { factors[nfactors++] = 2; n >>= 1; } |
|
287
|
1608 |
3 |
if (3<=last) while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
|
804 |
1608 |
if (3<=last) while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
288
|
1508 |
103 |
if (5<=last) while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
|
372 |
1508 |
if (5<=last) while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
289
|
5598 |
3 |
for (sp = 4; sp < (int)NPRIMES_SMALL; sp++) { |
|
291
|
4560 |
1038 |
if (f*f > n || f > last) break; |
|
|
3990 |
570 |
if (f*f > n || f > last) break; |
|
292
|
384 |
3990 |
while ( (n%f) == 0 ) { |
|
299
|
573 |
1038 |
if (f*f <= n && f <= last) { |
|
|
3 |
570 |
if (f*f <= n && f <= last) { |
|
301
|
2 |
1 |
if (limit > last) limit = last; |
|
303
|
7903 |
3 |
while (f <= limit) { |
|
304
|
2 |
7901 |
if ( (n%f) == 0 ) { |
|
308
|
0 |
2 |
} while ( (n%f) == 0 ); |
|
310
|
2 |
0 |
if (newlimit < limit) limit = newlimit; |
|
317
|
1485 |
126 |
if (n != 1) |
|
327
|
9080 |
3862 |
for (s = 0; s < nfactors; s++) { |
|
329
|
12195 |
9080 |
for (j = 0; j < e; j++) { |
|
331
|
28960 |
12195 |
for (i = 0; i < scount; i++) |
|
338
|
53930 |
5021 |
{ const UV *x = a, *y = b; return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; } |
|
|
53930 |
0 |
{ const UV *x = a, *y = b; return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; } |
|
347
|
4 |
3862 |
if (n <= 1) { |
|
349
|
1 |
3 |
if (n == 0) { divs[0] = 0; divs[1] = 1; *num_divisors = 2; } |
|
350
|
3 |
1 |
if (n == 1) { divs[0] = 1; *num_divisors = 1; } |
|
357
|
5218 |
3862 |
for (i = 1; i < nfactors; i++) |
|
359
|
0 |
3862 |
New(0, divs, ndivisors, UV); |
|
388
|
1505 |
0 |
if (k > 11 || (k > 0 && n >= sigma_overflow[k-1])) return 0; |
|
|
250 |
1255 |
if (k > 11 || (k > 0 && n >= sigma_overflow[k-1])) return 0; |
|
|
0 |
250 |
if (k > 11 || (k > 0 && n >= sigma_overflow[k-1])) return 0; |
|
389
|
287 |
1218 |
if (n <= 1) /* n=0 divisors are [0,1] */ |
|
390
|
3 |
284 |
return (n == 1) ? 1 : (k == 0) ? 2 : 1; /* n=1 divisors are [1] */ |
|
|
2 |
1 |
return (n == 1) ? 1 : (k == 0) ? 2 : 1; /* n=1 divisors are [1] */ |
|
392
|
974 |
244 |
if (k == 0) { |
|
393
|
1365 |
974 |
for (i = 0; i < nfac; i++) { |
|
395
|
832 |
974 |
while (i+1 < nfac && f == factors[i+1]) { e++; i++; } |
|
|
441 |
391 |
while (i+1 < nfac && f == factors[i+1]) { e++; i++; } |
|
398
|
157 |
87 |
} else if (k == 1) { |
|
399
|
270 |
157 |
for (i = 0; i < nfac; i++) { |
|
402
|
215 |
157 |
while (i+1 < nfac && f == factors[i+1]) { |
|
|
102 |
113 |
while (i+1 < nfac && f == factors[i+1]) { |
|
410
|
135 |
87 |
for (i = 0; i < nfac; i++) { |
|
413
|
193 |
135 |
for (j = 1; j < (int)k; j++) pk *= f; |
|
416
|
101 |
87 |
while (i+1 < nfac && f == factors[i+1]) { |
|
|
53 |
48 |
while (i+1 < nfac && f == factors[i+1]) { |
|
434
|
303 |
0 |
if (f == 1 || f2 == 1) { |
|
|
0 |
303 |
if (f == 1 || f2 == 1) { |
|
440
|
0 |
303 |
MPUassert( factors[0] * factors[1] == n , "incorrect factoring"); |
|
450
|
2 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in fermat_factor"); |
|
|
0 |
2 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in fermat_factor"); |
|
456
|
8 |
2 |
while (r != 0) { |
|
457
|
0 |
8 |
if (rounds-- == 0) { factors[0] = n; return 1; } |
|
463
|
18 |
8 |
} while (r > 0); |
|
474
|
2 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in holf_factor"); |
|
|
0 |
2 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in holf_factor"); |
|
478
|
0 |
2 |
if (is_perfect_square(n)) |
|
481
|
2 |
0 |
if (n <= (UV_MAX >> 6)) { /* Try with premultiplier first */ |
|
482
|
0 |
2 |
UV npre = n * ( (n <= (UV_MAX >> 13)) ? 720 : |
|
|
0 |
0 |
UV npre = n * ( (n <= (UV_MAX >> 13)) ? 720 : |
|
|
0 |
0 |
UV npre = n * ( (n <= (UV_MAX >> 13)) ? 720 : |
|
|
0 |
0 |
UV npre = n * ( (n <= (UV_MAX >> 13)) ? 720 : |
|
500
|
3 |
0 |
while (rounds--) { |
|
504
|
2 |
1 |
if (!((f*0x8bc40d7d) & (f*0xa1e2f5d1) & 0x14020a)) { |
|
506
|
2 |
0 |
if (m == f*f) { |
|
508
|
2 |
0 |
if (f > 1 && f < n) |
|
|
2 |
0 |
if (f > 1 && f < n) |
|
512
|
0 |
1 |
if (ni >= (ni+npre)) break; |
|
518
|
0 |
0 |
for (i = 1; i <= rounds; i++) { |
|
524
|
0 |
0 |
if (is_perfect_square(m)) { |
|
526
|
0 |
0 |
f = gcd_ui( (s>f) ? s-f : f-s, n); |
|
538
|
0 |
91 |
if (n < 3) { factors[0] = n; return 1; } |
|
539
|
0 |
91 |
if (!(n&1)) { factors[0] = 2; factors[1] = n/2; return 2; } |
|
540
|
1 |
90 |
if (is_perfect_square(n)) { factors[0] = factors[1] = isqrt(n); return 2; } |
|
543
|
2729 |
0 |
while (rounds--) { |
|
547
|
2101 |
628 |
if (!((f*0x8bc40d7d) & (f*0xa1e2f5d1) & 0x14020a)) { |
|
549
|
90 |
2011 |
if (m == f*f) { |
|
551
|
90 |
0 |
if (f > 1 && f < n) |
|
|
90 |
0 |
if (f > 1 && f < n) |
|
555
|
0 |
2639 |
if (ni >= (ni+npre)) break; /* We've overflowed */ |
|
568
|
201 |
0 |
UV const nbits = BITS_PER_WORD - clz(n); |
|
569
|
196 |
5 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
185 |
11 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
166 |
19 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
106 |
60 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
574
|
201 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pbrent_factor"); |
|
|
0 |
201 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pbrent_factor"); |
|
579
|
1516 |
0 |
while (rounds > 0) { |
|
583
|
2385 |
1315 |
while (rleft > 0) { |
|
588
|
2031 |
354 |
if (n < (1ULL << 63)) { |
|
590
|
1021 |
1010 |
m = ABSDIFF(Xi,Xm); |
|
591
|
227523 |
2031 |
while (--irounds > 0) { |
|
593
|
100959 |
126564 |
f = ABSDIFF(Xi,Xm); |
|
596
|
354 |
0 |
} else if (a == mont1) { |
|
598
|
201 |
153 |
m = ABSDIFF(Xi,Xm); |
|
599
|
103835 |
354 |
while (--irounds > 0) { |
|
601
|
59454 |
44381 |
f = ABSDIFF(Xi,Xm); |
|
606
|
0 |
0 |
m = ABSDIFF(Xi,Xm); |
|
607
|
0 |
0 |
while (--irounds > 0) { |
|
609
|
0 |
0 |
f = ABSDIFF(Xi,Xm); |
|
614
|
201 |
2184 |
if (f != 1) |
|
618
|
1315 |
201 |
if (f == 1) { |
|
622
|
0 |
201 |
if (f == n) { /* back up, with safety */ |
|
625
|
0 |
0 |
if (n < (1ULL << 63) || a == mont1) |
|
|
0 |
0 |
if (n < (1ULL << 63) || a == mont1) |
|
626
|
0 |
0 |
Xi = mont_mulmod(Xi,Xi+a,n); |
|
628
|
0 |
0 |
Xi = addmod(mont_mulmod(Xi,Xi,n),a,n); |
|
629
|
0 |
0 |
m = ABSDIFF(Xi,Xm); |
|
631
|
0 |
0 |
} while (f == 1 && r-- != 0); |
|
|
0 |
0 |
} while (f == 1 && r-- != 0); |
|
633
|
201 |
0 |
if (f == 0 || f == n) { |
|
|
0 |
201 |
if (f == 0 || f == n) { |
|
634
|
0 |
0 |
if (fails-- <= 0) break; |
|
711
|
2 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in prho_factor"); |
|
|
0 |
2 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in prho_factor"); |
|
724
|
2 |
0 |
while (rounds-- > 0) { |
|
726
|
128 |
2 |
for (i = 0; i < inner; i++) { |
|
730
|
59 |
69 |
f = (U > V) ? U-V : V-U; |
|
734
|
0 |
2 |
if (f == 1) |
|
736
|
2 |
0 |
if (f == n) { /* back up to find a factor*/ |
|
743
|
3 |
3 |
f = gcd_ui( (U > V) ? U-V : V-U, n); |
|
744
|
4 |
2 |
} while (f == 1 && i-- != 0); |
|
|
4 |
0 |
} while (f == 1 && i-- != 0); |
|
746
|
2 |
0 |
if (f == 0 || f == n) { |
|
|
0 |
2 |
if (f == 0 || f == n) { |
|
747
|
0 |
0 |
if (fails-- <= 0) break; |
|
776
|
2 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pminus1_factor"); |
|
|
0 |
2 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pminus1_factor"); |
|
778
|
0 |
2 |
if (B1 <= primes_small[NPRIMES_SMALL-2]) { |
|
780
|
0 |
0 |
for (i = 1; primes_small[i] <= B1; i++) { |
|
782
|
0 |
0 |
if (q <= sqrtB1) { |
|
784
|
0 |
0 |
while (k <= kmin) k *= q; |
|
787
|
0 |
0 |
if ( (j++ % 32) == 0) { |
|
788
|
0 |
0 |
PMINUS1_RECOVER_A; |
|
789
|
0 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
|
0 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
794
|
0 |
0 |
PMINUS1_RECOVER_A; |
|
796
|
2 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
6 |
58 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
4 |
2 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
2 |
2 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
8 |
50 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
8 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
8 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
8 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
58 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
64 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
798
|
64 |
0 |
if (q <= sqrtB1) { |
|
800
|
136 |
64 |
while (k <= kmin) k *= q; |
|
803
|
2 |
62 |
if ( (j++ % 32) == 0) { |
|
804
|
0 |
2 |
PMINUS1_RECOVER_A; |
|
805
|
2 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
|
0 |
2 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
810
|
0 |
2 |
PMINUS1_RECOVER_A; |
|
812
|
0 |
2 |
if (a == 0) { factors[0] = n; return 1; } |
|
816
|
2 |
0 |
if (f == n) { |
|
818
|
2 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
4 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
2 |
2 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
2 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
4 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
820
|
58 |
4 |
while (k <= kmin) k *= p; |
|
824
|
2 |
2 |
if (f != 1) |
|
839
|
0 |
2 |
if (f == 1 && B2 > B1) { |
|
|
0 |
0 |
if (f == 1 && B2 > B1) { |
|
848
|
0 |
0 |
for (j = 1; j < 20; j++) { |
|
856
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
862
|
0 |
0 |
if (qdiff >= 111) { |
|
866
|
0 |
0 |
if (bmdiff == 0) { |
|
867
|
0 |
0 |
if (precomp_bm[qdiff-1] != 0) |
|
875
|
0 |
0 |
if (a == 0) break; |
|
877
|
0 |
0 |
if ( (j++ % 64) == 0 ) { |
|
879
|
0 |
0 |
if (f != 1) |
|
894
|
6 |
0 |
UV bit = UVCONST(1) << (clz(exp)-1); |
|
895
|
339 |
6 |
while (bit) { |
|
897
|
15 |
324 |
if ( exp & bit ) { |
|
912
|
2 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pplus1_factor"); |
|
|
0 |
2 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pplus1_factor"); |
|
917
|
2 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
4 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
2 |
2 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
1 |
1 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
4 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
919
|
4 |
0 |
if (p < sqrtB1) { |
|
921
|
17 |
4 |
while (k <= kmin) |
|
925
|
4 |
0 |
if (X1 != 2) { |
|
927
|
2 |
2 |
if (f != 1 && f != n) break; |
|
|
2 |
0 |
if (f != 1 && f != n) break; |
|
930
|
0 |
2 |
if (X2 != 2) { |
|
932
|
0 |
0 |
if (f != 1 && f != n) break; |
|
|
0 |
0 |
if (f != 1 && f != n) break; |
|
987
|
0 |
3 |
if (i & 0x1) { |
|
993
|
0 |
4 |
if (i >= imax) { |
|
1007
|
3 |
1 |
if (!((t2*0x8bc40d7d) & (t2*0xa1e2f5d1) & 0x14020a)) { |
|
1009
|
3 |
0 |
if (Qn == t1*t1) |
|
1036
|
2 |
1 |
SYMMETRY_POINT_ITERATION; |
|
1037
|
1 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1038
|
0 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1039
|
0 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1040
|
0 |
0 |
if (j++ > 2000000) { |
|
1047
|
3 |
0 |
if (t1 > 1) |
|
1074
|
2 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in squfof_factor"); |
|
|
0 |
2 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in squfof_factor"); |
|
1077
|
0 |
2 |
if (n > SQUFOF_MAX) { |
|
1081
|
76 |
2 |
for (i = 0; i < NSQUFOF_MULT; i++) { |
|
1087
|
2 |
0 |
while (mults_racing > 0 && rounds_done < rounds) { |
|
|
2 |
0 |
while (mults_racing > 0 && rounds_done < rounds) { |
|
1088
|
3 |
0 |
for (i = 0; i < NSQUFOF_MULT && rounds_done < rounds; i++) { |
|
|
3 |
0 |
for (i = 0; i < NSQUFOF_MULT && rounds_done < rounds; i++) { |
|
1089
|
0 |
3 |
if (mult_save[i].valid == 0) continue; |
|
1092
|
3 |
0 |
if (mult_save[i].valid == -1) { |
|
1093
|
0 |
3 |
if ((SQUFOF_MAX / mult) < n) { |
|
1104
|
0 |
3 |
if (mult_save[i].Qn == 0) |
|
1110
|
3 |
0 |
if (mult_save[i].imax < 20) mult_save[i].imax = 20; |
|
1111
|
0 |
3 |
if (mult_save[i].imax > rounds) mult_save[i].imax = rounds; |
|
1113
|
0 |
3 |
if (mults_racing == 1) /* Do all rounds if only one multiplier left */ |
|
1116
|
3 |
0 |
if (f64 > 1) { |
|
1118
|
2 |
1 |
if (f64red > 1) { |
|
1127
|
1 |
0 |
if (mult_save[i].valid == 0) |
|
1143
|
0 |
0 |
for (i = 0; i < SQR_TAB_SIZE; i++) |
|
1151
|
0 |
0 |
const double Tune = ((n >> 31) >> 5) ? 3.5 : 5.0; |
|
1156
|
0 |
0 |
if (!(n&1)) return found_factor(n, 2, factors); |
|
1160
|
0 |
0 |
if (do_trial) { |
|
1162
|
0 |
0 |
if (FirstCut < 84) FirstCut = 84; |
|
1163
|
0 |
0 |
if (FirstCut > 65535) FirstCut = 65535; |
|
1164
|
0 |
0 |
for (ip = 2; ip < NPRIMES_SMALL; ip++) { |
|
1166
|
0 |
0 |
if (p >= FirstCut) |
|
1168
|
0 |
0 |
if (n % p == 0) |
|
1173
|
0 |
0 |
if (n >= UVCONST(8796393022207)) { factors[0] = n; return 1; } |
|
1178
|
0 |
0 |
if (!sqr_tab_init) make_sqr_tab(); |
|
1181
|
0 |
0 |
for (k = 1; k <= Bred; k++) { |
|
1182
|
0 |
0 |
if (k&1) { inc = 4; r = (k+n) % 4; } |
|
1185
|
0 |
0 |
if (kN >= UVCONST(1152921504606846976)) { factors[0] = n; return 1; } |
|
1188
|
0 |
0 |
x = (k < SQR_TAB_SIZE) ? sqrtn * sqr_tab[k] : sqrt((double)kN); |
|
1190
|
0 |
0 |
if ((UV)a * (UV)a == kN) |
|
1198
|
0 |
0 |
for (a = b; a <= U; c += inc*(a+a+inc), a += inc) { |
|
1201
|
0 |
0 |
if (!((b*0x8bc40d7d) & (b*0xa1e2f5d1) & 0x14020a)) { |
|
1203
|
0 |
0 |
if (c == b*b) { |
|
1210
|
0 |
0 |
if (do_trial) { |
|
1211
|
0 |
0 |
if (B > 65535) B = 65535; |
|
1217
|
0 |
0 |
if (ip >= NPRIMES_SMALL) ip = NPRIMES_SMALL-1; |
|
1226
|
0 |
23 |
if (maxrounds > p) maxrounds = p; |
|
1229
|
18 |
5 |
if (p&1) { |
|
1233
|
13930 |
0 |
for (t = g, k = 1; k < maxrounds; k++) { |
|
1234
|
18 |
13912 |
if (t == a) |
|
1236
|
0 |
13912 |
t = mont_mulmod(t, g, p); |
|
1237
|
0 |
13912 |
if (t == g) break; /* Stop at cycle */ |
|
1242
|
9 |
0 |
for (t = g, k = 1; k < maxrounds; k++) { |
|
1243
|
4 |
5 |
if (t == a) |
|
1246
|
1 |
4 |
if (t == g) break; /* Stop at cycle */ |
|
1289
|
0 |
4 |
if (s->failed) return 0; |
|
1290
|
0 |
4 |
if (s->round + rounds > n) rounds = n - s->round; |
|
1292
|
26785 |
2 |
for (i = 1; i <= rounds; i++) { |
|
1296
|
0 |
26785 |
if (verbose > 3) printf( "%3"UVuf" %4"UVuf" %3"UVuf" %3"UVuf" %4"UVuf" %3"UVuf" %3"UVuf"\n", i, u, v, w, U, V, W ); |
|
1297
|
2 |
26783 |
if (u == U) { |
|
1300
|
0 |
2 |
if (r1 == 0) { |
|
1301
|
0 |
0 |
if (verbose) printf("DLP Rho failure, r=0\n"); |
|
1311
|
0 |
2 |
if (G > 1) { |
|
1312
|
0 |
0 |
if (powmod(g,k,p) == a) { |
|
1313
|
0 |
0 |
if (verbose > 2) printf(" common GCD %"UVuf"\n", G2); |
|
1316
|
0 |
0 |
for (m = 0; m < G; m++) { |
|
1318
|
0 |
0 |
if (powmod(g,k,p) == a) break; |
|
1320
|
0 |
0 |
if (m 2) printf(" GCD %"UVuf", found with m=%"UVuf"\n", G, m); |
|
|
0 |
0 |
if (m 2) printf(" GCD %"UVuf", found with m=%"UVuf"\n", G, m); |
|
1324
|
0 |
2 |
if (powmod(g,k,p) != a) { |
|
1325
|
0 |
0 |
if (verbose > 2) printf("r1 = %"UVuf" r2 = %"UVuf" k = %"UVuf"\n", r1, r2, k); |
|
1326
|
0 |
0 |
if (verbose) printf("Incorrect DLP Rho solution: %"UVuf"\n", k); |
|
1334
|
0 |
4 |
if (verbose && k) printf("DLP Rho solution found after %"UVuf" steps\n", s->round + 1); |
|
|
0 |
0 |
if (verbose && k) printf("DLP Rho solution found after %"UVuf" steps\n", s->round + 1); |
|
1379
|
4137 |
2 |
if (top->nused == 0 || top->nused >= BSGS_ENTRIES_PER_PAGE) { |
|
|
0 |
4137 |
if (top->nused == 0 || top->nused >= BSGS_ENTRIES_PER_PAGE) { |
|
1391
|
2 |
2 |
while (head != 0) { |
|
1405
|
0 |
2 |
while (entry && entry->V != v) |
|
|
0 |
0 |
while (entry && entry->V != v) |
|
1408
|
2 |
0 |
if (!entry) { |
|
1419
|
0 |
0 |
while (entry && entry->V != v) |
|
|
0 |
0 |
while (entry && entry->V != v) |
|
1421
|
0 |
0 |
return (entry) ? entry->M : 0; |
|
1429
|
123 |
4137 |
while (entry && entry->V != v) |
|
|
123 |
0 |
while (entry && entry->V != v) |
|
1432
|
0 |
4137 |
if (entry) |
|
1455
|
0 |
3 |
if (n <= 2) return 0; /* Shouldn't be here with gorder this low */ |
|
1457
|
3 |
0 |
if (race_rho) { |
|
1459
|
1 |
2 |
if (result) { |
|
1460
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step 0\n"); |
|
1465
|
0 |
2 |
if (a == 0) return 0; /* We don't handle this case */ |
|
1470
|
0 |
2 |
hashmap_count = (m < 65537) ? 65537 : |
|
1471
|
0 |
0 |
(m > 40000000) ? 40000003 : |
|
1479
|
0 |
2 |
Newz(0, PAGES.table, hashmap_count, bsgs_hash_t*); |
|
1491
|
2069 |
0 |
for (i = 1; i <= m; i++) { |
|
1493
|
0 |
2069 |
if (gs_i) { bs_i = i; break; } |
|
1495
|
1 |
2068 |
if (S == aa) { /* We discovered the solution! */ |
|
1496
|
0 |
1 |
if (verbose) printf(" dlp bsgs: solution at BS step %"UVuf"\n", i+1); |
|
1501
|
0 |
2068 |
if (bs_i) { gs_i = i; break; } |
|
1503
|
2068 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
|
1 |
2067 |
if (race_rho && (i % 2048) == 0) { |
|
1505
|
1 |
0 |
if (result) { |
|
1506
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step %"UVuf"\n", i); |
|
1512
|
0 |
2 |
if (!result) { |
|
1514
|
0 |
0 |
if (!(gs_i || bs_i)) { |
|
|
0 |
0 |
if (!(gs_i || bs_i)) { |
|
1516
|
0 |
0 |
if (m < maxm && b > 8*m) b = 8*m; |
|
|
0 |
0 |
if (m < maxm && b > 8*m) b = 8*m; |
|
1517
|
0 |
0 |
for (i = m+1; i < b; i++) { |
|
1519
|
0 |
0 |
if (bs_i) { gs_i = i; break; } |
|
1521
|
0 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
|
0 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
1523
|
0 |
0 |
if (result) { |
|
1524
|
0 |
0 |
if (verbose) printf("rho found solution in BSGS step %"UVuf"\n", i); |
|
1531
|
0 |
0 |
if (gs_i || bs_i) { |
|
|
0 |
0 |
if (gs_i || bs_i) { |
|
1535
|
0 |
2 |
if (verbose) printf(" dlp bsgs using %d pages (%.1fMB+%.1fMB) for hash\n", PAGES.npages, ((double)PAGES.npages * sizeof(bsgs_page_t)) / (1024*1024), ((double)hashmap_count * sizeof(bsgs_hash_t*)) / (1024*1024)); |
|
1539
|
2 |
0 |
if (result != 0 && powmod(g,result,p) != a) { |
|
|
0 |
2 |
if (result != 0 && powmod(g,result,p) != a) { |
|
1540
|
0 |
0 |
if (verbose) printf("Incorrect DLP BSGS solution: %"UVuf"\n", result); |
|
1543
|
2 |
0 |
if (race_rho && result == 0) { |
|
|
0 |
2 |
if (race_rho && result == 0) { |
|
1555
|
0 |
16 |
if (a >= p) a %= p; |
|
1556
|
0 |
16 |
if (g >= p) g %= p; |
|
1558
|
15 |
1 |
if (a == 1 || g == 0 || p <= 2) |
|
|
15 |
0 |
if (a == 1 || g == 0 || p <= 2) |
|
|
0 |
15 |
if (a == 1 || g == 0 || p <= 2) |
|
1561
|
0 |
15 |
if (verbose > 1 && n != p-1) printf(" g=%"UVuf" p=%"UVuf", order %"UVuf"\n", g, p, n); |
|
|
0 |
0 |
if (verbose > 1 && n != p-1) printf(" g=%"UVuf" p=%"UVuf", order %"UVuf"\n", g, p, n); |
|
1565
|
15 |
0 |
if (n == 0 || n <= DLP_TRIAL_NUM) { |
|
|
12 |
3 |
if (n == 0 || n <= DLP_TRIAL_NUM) { |
|
1567
|
0 |
12 |
if (verbose) printf(" dlp trial 10k %s\n", (k!=0 || p <= DLP_TRIAL_NUM) ? "success" : "failure"); |
|
|
0 |
0 |
if (verbose) printf(" dlp trial 10k %s\n", (k!=0 || p <= DLP_TRIAL_NUM) ? "success" : "failure"); |
|
|
0 |
0 |
if (verbose) printf(" dlp trial 10k %s\n", (k!=0 || p <= DLP_TRIAL_NUM) ? "success" : "failure"); |
|
1568
|
0 |
12 |
if (k != 0 || (n > 0 && n <= DLP_TRIAL_NUM)) return k; |
|
|
0 |
0 |
if (k != 0 || (n > 0 && n <= DLP_TRIAL_NUM)) return k; |
|
|
0 |
0 |
if (k != 0 || (n > 0 && n <= DLP_TRIAL_NUM)) return k; |
|
1573
|
3 |
0 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
|
0 |
3 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
1575
|
0 |
3 |
if (aorder == 0 && gorder != 0) return 0; |
|
|
0 |
0 |
if (aorder == 0 && gorder != 0) return 0; |
|
1576
|
3 |
0 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
|
0 |
3 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
1579
|
3 |
0 |
sqrtn = (n == 0) ? 0 : isqrt(n); |
|
1580
|
0 |
3 |
if (n == 0) n = p-1; |
|
1583
|
3 |
0 |
UV maxent = (sqrtn > 0) ? sqrtn+1 : 100000; |
|
1585
|
0 |
3 |
if (verbose) printf(" dlp bsgs %"UVuf"k %s\n", maxent/1000, k!=0 ? "success" : "failure"); |
|
|
0 |
0 |
if (verbose) printf(" dlp bsgs %"UVuf"k %s\n", maxent/1000, k!=0 ? "success" : "failure"); |
|
1586
|
3 |
0 |
if (k != 0) return k; |
|
1587
|
0 |
0 |
if (sqrtn > 0 && sqrtn < maxent) return 0; |
|
|
0 |
0 |
if (sqrtn > 0 && sqrtn < maxent) return 0; |
|
1590
|
0 |
0 |
if (verbose) printf(" dlp doing exhaustive trial\n"); |
|
1602
|
0 |
5 |
if (p1 == 0) return 0; /* TODO: Should we plow on with p1=p-1? */ |
|
1604
|
0 |
5 |
if (nfactors == 1) |
|
1606
|
16 |
5 |
for (i = 0; i < nfactors; i++) { |
|
1608
|
1 |
16 |
pi = fac[i]; for (j = 1; j < exp[i]; j++) pi *= fac[i]; |
|
1616
|
5 |
0 |
if (i == 1 && powmod(g, x, p) == a) |
|
|
5 |
0 |
if (i == 1 && powmod(g, x, p) == a) |
|
1626
|
0 |
20 |
if (a >= p) a %= p; |
|
1627
|
0 |
20 |
if (g >= p) g %= p; |
|
1629
|
18 |
2 |
if (a == 1 || g == 0 || p <= 2) |
|
|
18 |
0 |
if (a == 1 || g == 0 || p <= 2) |
|
|
0 |
18 |
if (a == 1 || g == 0 || p <= 2) |
|
1636
|
15 |
3 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
|
2 |
13 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
1638
|
3 |
13 |
if (aorder == 0 && gorder != 0) return 0; |
|
|
0 |
3 |
if (aorder == 0 && gorder != 0) return 0; |
|
1639
|
13 |
3 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
|
0 |
13 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
1642
|
15 |
1 |
if (a == 0 || p < DLP_TRIAL_NUM || (gorder > 0 && gorder < DLP_TRIAL_NUM)) { |
|
|
5 |
10 |
if (a == 0 || p < DLP_TRIAL_NUM || (gorder > 0 && gorder < DLP_TRIAL_NUM)) { |
|
|
5 |
0 |
if (a == 0 || p < DLP_TRIAL_NUM || (gorder > 0 && gorder < DLP_TRIAL_NUM)) { |
|
|
0 |
5 |
if (a == 0 || p < DLP_TRIAL_NUM || (gorder > 0 && gorder < DLP_TRIAL_NUM)) { |
|
1643
|
0 |
11 |
if (verbose > 1) printf(" dlp trial znlog(%"UVuf",%"UVuf",%"UVuf")\n",a,g,p); |
|
1648
|
5 |
0 |
if (!is_prob_prime(gorder)) { |
|
1650
|
0 |
5 |
if (verbose) printf(" dlp PH %s\n", k!=0 ? "success" : "failure"); |
|
|
0 |
0 |
if (verbose) printf(" dlp PH %s\n", k!=0 ? "success" : "failure"); |
|
1651
|
5 |
0 |
if (k != 0) return k; |