| line |
true |
false |
branch |
|
59
|
33855 |
149 |
if (n > 1) { |
|
60
|
14882 |
33855 |
while ( (n & 1) == 0 ) { factors[nfactors++] = 2; n /= 2; } |
|
61
|
10524 |
33855 |
while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
62
|
5930 |
33855 |
while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
65
|
26728 |
7276 |
if (f*f <= n) { |
|
69
|
26561 |
167 |
if (n <= 4294967295U) { |
|
71
|
238730 |
219 |
while (sp < lastsp) { |
|
72
|
12438 |
238730 |
while ( (un%f) == 0 ) { |
|
77
|
26342 |
212388 |
if (f*f > un) break; |
|
81
|
12477 |
155 |
while (sp < lastsp) { |
|
82
|
220 |
12477 |
while ( (n%f) == 0 ) { |
|
87
|
12 |
12465 |
if (f*f > n) break; |
|
91
|
26419 |
309 |
if (n < 2011*2011 && f*f <= n) { /* Trial division from 431 to 2003 */ |
|
|
65 |
26354 |
if (n < 2011*2011 && f*f <= n) { /* Trial division from 431 to 2003 */ |
|
93
|
5934 |
0 |
while (sp < NPRIMES_SMALL) { |
|
94
|
21 |
5934 |
while ( (un%f) == 0 ) { |
|
99
|
65 |
5869 |
if (f*f > un) break; |
|
104
|
33695 |
309 |
if (f*f > n && n != 1) { |
|
|
30179 |
3516 |
if (f*f > n && n != 1) { |
|
108
|
34004 |
0 |
if (newn) *newn = n; |
|
109
|
34004 |
0 |
if (lastf) *lastf = f; |
|
116
|
5 |
200 |
if (k > 1) { |
|
119
|
12 |
5 |
for (i = nfactors; i >= 0; i--) |
|
120
|
26 |
12 |
for (j = 0; j < k; j++) |
|
132
|
0 |
190 |
if (n < 4) { |
|
137
|
0 |
190 |
if (trial) { |
|
139
|
0 |
0 |
if (!(n&1)) { factors[0] = 2; factors[1] = n >> 1; return 2; } |
|
140
|
0 |
0 |
if (!(n%3)) { factors[0] = 3; factors[1] = n / 3; return 2; } |
|
141
|
0 |
0 |
if (!(n%5)) { factors[0] = 5; factors[1] = n / 5; return 2; } |
|
142
|
0 |
0 |
for (sp = 4; (f = primes_small[sp]) < 2011; sp++) { |
|
143
|
0 |
0 |
if ( (n % f) == 0 ) |
|
146
|
0 |
0 |
if (n < f*f) { factors[0] = n; return 1; } |
|
148
|
0 |
190 |
if (primality && is_prime(n)) { |
|
|
0 |
0 |
if (primality && is_prime(n)) { |
|
159
|
190 |
0 |
UV const nbits = BITS_PER_WORD - clz(n); |
|
161
|
68 |
122 |
UV const br_rounds = 8000 + (9000 * ((nbits <= 45) ? 0 : (nbits-45))); |
|
175
|
35 |
155 |
if (nbits <= 30) { /* This should always succeed */ |
|
177
|
35 |
0 |
if (nfactors > 1) return nfactors; |
|
181
|
155 |
0 |
if (br_rounds > 0) { |
|
183
|
155 |
0 |
if (nfactors > 1) return nfactors; |
|
187
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
196
|
0 |
0 |
if (nbits <= 62) { |
|
198
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
202
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
205
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
207
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
209
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
227
|
33695 |
309 |
if (n == 1) return nfactors; |
|
231
|
107 |
202 |
if (n < 100000000 && n < f*f*f) { |
|
|
104 |
3 |
if (n < 100000000 && n < f*f*f) { |
|
232
|
52 |
52 |
if (MR32(n)) factors[nfactors++] = n; |
|
242
|
5 |
200 |
if (npowerfactors > 1) return nsmallfactors + npowerfactors; |
|
246
|
353 |
177 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
124 |
229 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
37 |
87 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
128 |
101 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
248
|
165 |
0 |
if (split_success != 1 || tofac_stack[ntofac] == 1 || tofac_stack[ntofac] == n) |
|
|
165 |
0 |
if (split_success != 1 || tofac_stack[ntofac] == 1 || tofac_stack[ntofac] == n) |
|
|
0 |
165 |
if (split_success != 1 || tofac_stack[ntofac] == 1 || tofac_stack[ntofac] == n) |
|
254
|
365 |
0 |
if (n != 1) factors[nfactors++] = n; |
|
256
|
165 |
200 |
if (ntofac > 0) n = tofac_stack[ntofac-1]; |
|
257
|
165 |
200 |
} while (ntofac-- > 0); |
|
260
|
165 |
200 |
for (i = nsmallfactors+1; i < nfactors; i++) { |
|
262
|
316 |
42 |
for (j = i; j > 0 && factors[j-1] > fi; j--) |
|
|
193 |
123 |
for (j = i; j > 0 && factors[j-1] > fi; j--) |
|
274
|
11 |
12664 |
if (n == 1) return 0; |
|
277
|
53 |
12611 |
if (exponents == 0) { |
|
278
|
165 |
53 |
for (; i < nfactors; i++) |
|
279
|
111 |
54 |
if (factors[i] != factors[i-1]) |
|
283
|
16463 |
12611 |
for (; i < nfactors; i++) { |
|
284
|
12924 |
3539 |
if (factors[i] != factors[i-1]) { |
|
299
|
0 |
1619 |
if (f < 2) f = 2; |
|
300
|
1616 |
3 |
if (last == 0 || last*last > n) last = UV_MAX; |
|
|
1010 |
606 |
if (last == 0 || last*last > n) last = UV_MAX; |
|
302
|
1611 |
8 |
if (n < 4 || last < f) { |
|
|
0 |
1611 |
if (n < 4 || last < f) { |
|
309
|
1611 |
0 |
if (f < primes_small[NPRIMES_SMALL-1]) { |
|
310
|
1621 |
1611 |
while ( (n & 1) == 0 ) { factors[nfactors++] = 2; n >>= 1; } |
|
311
|
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; } |
|
312
|
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; } |
|
313
|
5598 |
3 |
for (sp = 4; sp < (int)NPRIMES_SMALL; sp++) { |
|
315
|
4560 |
1038 |
if (f*f > n || f > last) break; |
|
|
3990 |
570 |
if (f*f > n || f > last) break; |
|
316
|
384 |
3990 |
while ( (n%f) == 0 ) { |
|
323
|
573 |
1038 |
if (f*f <= n && f <= last) { |
|
|
3 |
570 |
if (f*f <= n && f <= last) { |
|
325
|
2 |
1 |
if (limit > last) limit = last; |
|
327
|
7903 |
3 |
while (f <= limit) { |
|
328
|
2 |
7901 |
if ( (n%f) == 0 ) { |
|
332
|
0 |
2 |
} while ( (n%f) == 0 ); |
|
334
|
2 |
0 |
if (newlimit < limit) limit = newlimit; |
|
341
|
1485 |
126 |
if (n != 1) |
|
351
|
8945 |
3834 |
for (s = 0; s < nfactors; s++) { |
|
353
|
12120 |
8945 |
for (j = 0; j < e; j++) { |
|
355
|
28417 |
12120 |
for (i = 0; i < scount; i++) |
|
368
|
4 |
3834 |
if (n <= 1) { |
|
370
|
1 |
3 |
if (n == 0) { divs[0] = 0; divs[1] = 1; *num_divisors = 2; } |
|
371
|
3 |
1 |
if (n == 1) { divs[0] = 1; *num_divisors = 1; } |
|
378
|
5111 |
3834 |
for (i = 1; i < nfactors; i++) |
|
380
|
0 |
3834 |
New(0, divs, ndivisors, UV); |
|
409
|
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; |
|
410
|
287 |
1218 |
if (n <= 1) /* n=0 divisors are [0,1] */ |
|
411
|
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] */ |
|
413
|
974 |
244 |
if (k == 0) { |
|
414
|
1365 |
974 |
for (i = 0; i < nfac; i++) { |
|
416
|
832 |
974 |
while (i+1 < nfac && f == factors[i+1]) { e++; i++; } |
|
|
441 |
391 |
while (i+1 < nfac && f == factors[i+1]) { e++; i++; } |
|
419
|
157 |
87 |
} else if (k == 1) { |
|
420
|
270 |
157 |
for (i = 0; i < nfac; i++) { |
|
423
|
215 |
157 |
while (i+1 < nfac && f == factors[i+1]) { |
|
|
102 |
113 |
while (i+1 < nfac && f == factors[i+1]) { |
|
431
|
135 |
87 |
for (i = 0; i < nfac; i++) { |
|
434
|
193 |
135 |
for (j = 1; j < (int)k; j++) pk *= f; |
|
437
|
101 |
87 |
while (i+1 < nfac && f == factors[i+1]) { |
|
|
53 |
48 |
while (i+1 < nfac && f == factors[i+1]) { |
|
455
|
255 |
0 |
if (f == 1 || f2 == 1) { |
|
|
0 |
255 |
if (f == 1 || f2 == 1) { |
|
461
|
0 |
255 |
MPUassert( factors[0] * factors[1] == n , "incorrect factoring"); |
|
471
|
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"); |
|
477
|
8 |
2 |
while (r != 0) { |
|
478
|
0 |
8 |
if (rounds-- == 0) { factors[0] = n; return 1; } |
|
484
|
18 |
8 |
} while (r > 0); |
|
495
|
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"); |
|
499
|
0 |
2 |
if (is_perfect_square(n)) |
|
502
|
2 |
0 |
if (n <= (UV_MAX >> 6)) { /* Try with premultiplier first */ |
|
503
|
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 : |
|
521
|
3 |
0 |
while (rounds--) { |
|
525
|
2 |
1 |
if (!((f*0x8bc40d7d) & (f*0xa1e2f5d1) & 0x14020a)) { |
|
527
|
2 |
0 |
if (m == f*f) { |
|
529
|
2 |
0 |
if (f > 1 && f < n) |
|
|
2 |
0 |
if (f > 1 && f < n) |
|
533
|
0 |
1 |
if (ni >= (ni+npre)) break; |
|
539
|
0 |
0 |
for (i = 1; i <= rounds; i++) { |
|
545
|
0 |
0 |
if (is_perfect_square(m)) { |
|
547
|
0 |
0 |
f = gcd_ui( (s>f) ? s-f : f-s, n); |
|
559
|
0 |
87 |
if (n < 3) { factors[0] = n; return 1; } |
|
560
|
0 |
87 |
if (!(n&1)) { factors[0] = 2; factors[1] = n/2; return 2; } |
|
561
|
1 |
86 |
if (is_perfect_square(n)) { factors[0] = factors[1] = isqrt(n); return 2; } |
|
564
|
2649 |
0 |
while (rounds--) { |
|
568
|
2059 |
590 |
if (!((f*0x8bc40d7d) & (f*0xa1e2f5d1) & 0x14020a)) { |
|
570
|
86 |
1973 |
if (m == f*f) { |
|
572
|
86 |
0 |
if (f > 1 && f < n) |
|
|
86 |
0 |
if (f > 1 && f < n) |
|
576
|
0 |
2563 |
if (ni >= (ni+npre)) break; /* We've overflowed */ |
|
589
|
157 |
0 |
UV const nbits = BITS_PER_WORD - clz(n); |
|
590
|
152 |
5 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
144 |
8 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
104 |
40 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
62 |
42 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
595
|
157 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pbrent_factor"); |
|
|
0 |
157 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pbrent_factor"); |
|
600
|
1219 |
0 |
while (rounds > 0) { |
|
604
|
2095 |
1062 |
while (rleft > 0) { |
|
609
|
1741 |
354 |
if (n < (1ULL << 63)) { |
|
611
|
858 |
883 |
m = ABSDIFF(Xi,Xm); |
|
612
|
221249 |
1741 |
while (--irounds > 0) { |
|
614
|
96995 |
124254 |
f = ABSDIFF(Xi,Xm); |
|
617
|
354 |
0 |
} else if (a == mont1) { |
|
619
|
201 |
153 |
m = ABSDIFF(Xi,Xm); |
|
620
|
103835 |
354 |
while (--irounds > 0) { |
|
622
|
59454 |
44381 |
f = ABSDIFF(Xi,Xm); |
|
627
|
0 |
0 |
m = ABSDIFF(Xi,Xm); |
|
628
|
0 |
0 |
while (--irounds > 0) { |
|
630
|
0 |
0 |
f = ABSDIFF(Xi,Xm); |
|
635
|
157 |
1938 |
if (f != 1) |
|
639
|
1062 |
157 |
if (f == 1) { |
|
643
|
0 |
157 |
if (f == n) { /* back up, with safety */ |
|
646
|
0 |
0 |
if (n < (1ULL << 63) || a == mont1) |
|
|
0 |
0 |
if (n < (1ULL << 63) || a == mont1) |
|
647
|
0 |
0 |
Xi = mont_mulmod(Xi,Xi+a,n); |
|
649
|
0 |
0 |
Xi = addmod(mont_mulmod(Xi,Xi,n),a,n); |
|
650
|
0 |
0 |
m = ABSDIFF(Xi,Xm); |
|
652
|
0 |
0 |
} while (f == 1 && r-- != 0); |
|
|
0 |
0 |
} while (f == 1 && r-- != 0); |
|
654
|
157 |
0 |
if (f == 0 || f == n) { |
|
|
0 |
157 |
if (f == 0 || f == n) { |
|
655
|
0 |
0 |
if (fails-- <= 0) break; |
|
732
|
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"); |
|
745
|
2 |
0 |
while (rounds-- > 0) { |
|
747
|
128 |
2 |
for (i = 0; i < inner; i++) { |
|
751
|
59 |
69 |
f = (U > V) ? U-V : V-U; |
|
755
|
0 |
2 |
if (f == 1) |
|
757
|
2 |
0 |
if (f == n) { /* back up to find a factor*/ |
|
764
|
3 |
3 |
f = gcd_ui( (U > V) ? U-V : V-U, n); |
|
765
|
4 |
2 |
} while (f == 1 && i-- != 0); |
|
|
4 |
0 |
} while (f == 1 && i-- != 0); |
|
767
|
2 |
0 |
if (f == 0 || f == n) { |
|
|
0 |
2 |
if (f == 0 || f == n) { |
|
768
|
0 |
0 |
if (fails-- <= 0) break; |
|
797
|
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"); |
|
799
|
0 |
2 |
if (B1 <= primes_small[NPRIMES_SMALL-2]) { |
|
801
|
0 |
0 |
for (i = 1; primes_small[i] <= B1; i++) { |
|
803
|
0 |
0 |
if (q <= sqrtB1) { |
|
805
|
0 |
0 |
while (k <= kmin) k *= q; |
|
808
|
0 |
0 |
if ( (j++ % 32) == 0) { |
|
809
|
0 |
0 |
PMINUS1_RECOVER_A; |
|
810
|
0 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
|
0 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
815
|
0 |
0 |
PMINUS1_RECOVER_A; |
|
817
|
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) { |
|
819
|
64 |
0 |
if (q <= sqrtB1) { |
|
821
|
136 |
64 |
while (k <= kmin) k *= q; |
|
824
|
2 |
62 |
if ( (j++ % 32) == 0) { |
|
825
|
0 |
2 |
PMINUS1_RECOVER_A; |
|
826
|
2 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
|
0 |
2 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
831
|
0 |
2 |
PMINUS1_RECOVER_A; |
|
833
|
0 |
2 |
if (a == 0) { factors[0] = n; return 1; } |
|
837
|
2 |
0 |
if (f == n) { |
|
839
|
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) { |
|
841
|
58 |
4 |
while (k <= kmin) k *= p; |
|
845
|
2 |
2 |
if (f != 1) |
|
860
|
0 |
2 |
if (f == 1 && B2 > B1) { |
|
|
0 |
0 |
if (f == 1 && B2 > B1) { |
|
869
|
0 |
0 |
for (j = 1; j < 20; j++) { |
|
877
|
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 ) { |
|
883
|
0 |
0 |
if (qdiff >= 111) { |
|
887
|
0 |
0 |
if (bmdiff == 0) { |
|
888
|
0 |
0 |
if (precomp_bm[qdiff-1] != 0) |
|
896
|
0 |
0 |
if (a == 0) break; |
|
898
|
0 |
0 |
if ( (j++ % 64) == 0 ) { |
|
900
|
0 |
0 |
if (f != 1) |
|
915
|
6 |
0 |
UV bit = UVCONST(1) << (clz(exp)-1); |
|
916
|
339 |
6 |
while (bit) { |
|
918
|
15 |
324 |
if ( exp & bit ) { |
|
933
|
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"); |
|
938
|
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) { |
|
940
|
4 |
0 |
if (p < sqrtB1) { |
|
942
|
17 |
4 |
while (k <= kmin) |
|
946
|
4 |
0 |
if (X1 != 2) { |
|
948
|
2 |
2 |
if (f != 1 && f != n) break; |
|
|
2 |
0 |
if (f != 1 && f != n) break; |
|
951
|
0 |
2 |
if (X2 != 2) { |
|
953
|
0 |
0 |
if (f != 1 && f != n) break; |
|
|
0 |
0 |
if (f != 1 && f != n) break; |
|
1008
|
0 |
3 |
if (i & 0x1) { |
|
1014
|
0 |
4 |
if (i >= imax) { |
|
1028
|
3 |
1 |
if (!((t2*0x8bc40d7d) & (t2*0xa1e2f5d1) & 0x14020a)) { |
|
1030
|
3 |
0 |
if (Qn == t1*t1) |
|
1057
|
2 |
1 |
SYMMETRY_POINT_ITERATION; |
|
1058
|
1 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1059
|
0 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1060
|
0 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1061
|
0 |
0 |
if (j++ > 2000000) { |
|
1068
|
3 |
0 |
if (t1 > 1) |
|
1095
|
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"); |
|
1098
|
0 |
2 |
if (n > SQUFOF_MAX) { |
|
1102
|
76 |
2 |
for (i = 0; i < NSQUFOF_MULT; i++) { |
|
1108
|
2 |
0 |
while (mults_racing > 0 && rounds_done < rounds) { |
|
|
2 |
0 |
while (mults_racing > 0 && rounds_done < rounds) { |
|
1109
|
3 |
0 |
for (i = 0; i < NSQUFOF_MULT && rounds_done < rounds; i++) { |
|
|
3 |
0 |
for (i = 0; i < NSQUFOF_MULT && rounds_done < rounds; i++) { |
|
1110
|
0 |
3 |
if (mult_save[i].valid == 0) continue; |
|
1113
|
3 |
0 |
if (mult_save[i].valid == -1) { |
|
1114
|
0 |
3 |
if ((SQUFOF_MAX / mult) < n) { |
|
1125
|
0 |
3 |
if (mult_save[i].Qn == 0) |
|
1131
|
3 |
0 |
if (mult_save[i].imax < 20) mult_save[i].imax = 20; |
|
1132
|
0 |
3 |
if (mult_save[i].imax > rounds) mult_save[i].imax = rounds; |
|
1134
|
0 |
3 |
if (mults_racing == 1) /* Do all rounds if only one multiplier left */ |
|
1137
|
3 |
0 |
if (f64 > 1) { |
|
1139
|
2 |
1 |
if (f64red > 1) { |
|
1148
|
1 |
0 |
if (mult_save[i].valid == 0) |
|
1164
|
0 |
0 |
for (i = 0; i < SQR_TAB_SIZE; i++) |
|
1172
|
0 |
0 |
const double Tune = ((n >> 31) >> 5) ? 3.5 : 5.0; |
|
1177
|
0 |
0 |
if (!(n&1)) return found_factor(n, 2, factors); |
|
1181
|
0 |
0 |
if (do_trial) { |
|
1183
|
0 |
0 |
if (FirstCut < 84) FirstCut = 84; |
|
1184
|
0 |
0 |
if (FirstCut > 65535) FirstCut = 65535; |
|
1185
|
0 |
0 |
for (ip = 2; ip < NPRIMES_SMALL; ip++) { |
|
1187
|
0 |
0 |
if (p >= FirstCut) |
|
1189
|
0 |
0 |
if (n % p == 0) |
|
1194
|
0 |
0 |
if (n >= UVCONST(8796393022207)) { factors[0] = n; return 1; } |
|
1199
|
0 |
0 |
if (!sqr_tab_init) make_sqr_tab(); |
|
1202
|
0 |
0 |
for (k = 1; k <= Bred; k++) { |
|
1203
|
0 |
0 |
if (k&1) { inc = 4; r = (k+n) % 4; } |
|
1206
|
0 |
0 |
if (kN >= UVCONST(1152921504606846976)) { factors[0] = n; return 1; } |
|
1209
|
0 |
0 |
x = (k < SQR_TAB_SIZE) ? sqrtn * sqr_tab[k] : sqrt((double)kN); |
|
1211
|
0 |
0 |
if ((UV)a * (UV)a == kN) |
|
1219
|
0 |
0 |
for (a = b; a <= U; c += inc*(a+a+inc), a += inc) { |
|
1222
|
0 |
0 |
if (!((b*0x8bc40d7d) & (b*0xa1e2f5d1) & 0x14020a)) { |
|
1224
|
0 |
0 |
if (c == b*b) { |
|
1231
|
0 |
0 |
if (do_trial) { |
|
1232
|
0 |
0 |
if (B > 65535) B = 65535; |
|
1238
|
0 |
0 |
if (ip >= NPRIMES_SMALL) ip = NPRIMES_SMALL-1; |
|
1253
|
0 |
1 |
New(0, N, hi-lo+1, UV); |
|
1254
|
998 |
1 |
for (j = 0; j < n; j++) { |
|
1258
|
0 |
1 |
sievelim = (sqrthi < _fr_sieve_crossover) ? sqrthi : icbrt(hi); |
|
1259
|
1 |
0 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
3 |
9 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
2 |
1 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
1 |
1 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
1 |
8 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
0 |
1 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
0 |
1 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
0 |
1 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
0 |
9 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
1 |
11 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
1261
|
0 |
11 |
if (square_free == 0) { |
|
1263
|
0 |
0 |
for (q = p; q <= kmin; q *= p) { |
|
1265
|
0 |
0 |
if (A < lo) A += q; |
|
1266
|
0 |
0 |
for (j = A-lo; j < n; j += q) { |
|
1273
|
11 |
0 |
if (A < lo) A += q; |
|
1274
|
440 |
11 |
for (j = A-lo; j < n; j += q) { |
|
1279
|
10 |
1 |
if (A < lo) A += q; |
|
1280
|
1558 |
11 |
for (j = A-lo; j < n; j += q) { |
|
1281
|
824 |
734 |
if (N[j] > 0) { |
|
1289
|
1 |
0 |
if (sievelim == sqrthi) { |
|
1291
|
998 |
1 |
for (j = 0; j < n; j++) { |
|
1292
|
157 |
841 |
if (N[j] == 1) |
|
1294
|
450 |
391 |
else if (N[j] > 0 && N[j] != j+lo) |
|
|
298 |
152 |
else if (N[j] > 0 && N[j] != j+lo) |
|
1299
|
0 |
0 |
for (j = 0; j < n; j++) { |
|
1301
|
0 |
0 |
if (N[j] > 0 && N[j] != rem) { |
|
|
0 |
0 |
if (N[j] > 0 && N[j] != rem) { |
|
1302
|
0 |
0 |
if (N[j] != 1) |
|
1304
|
0 |
0 |
if (square_free && is_perfect_square(rem)) { |
|
|
0 |
0 |
if (square_free && is_perfect_square(rem)) { |
|
1322
|
1 |
4 |
if (hi-lo+1 > 100) { /* Sieve in chunks */ |
|
1323
|
1 |
0 |
if (square_free) ctx._noffset = (hi <= 42949672965UL) ? 10 : 15; |
|
|
1 |
0 |
if (square_free) ctx._noffset = (hi <= 42949672965UL) ? 10 : 15; |
|
1324
|
0 |
0 |
else ctx._noffset = BITS_PER_WORD - clz(hi); |
|
1326
|
0 |
1 |
New(0, ctx._nfactors, _fr_chunk, UV); |
|
1327
|
0 |
1 |
New(0, ctx._farray, _fr_chunk * ctx._noffset, UV); |
|
1330
|
0 |
1 |
if (t >= _fr_sieve_crossover) t = icbrt(hi); |
|
1334
|
1 |
3 |
New(0, ctx.factors, square_free ? 15 : 63, UV); |
|
1345
|
0 |
1207 |
if (ctx->n >= ctx->hi) |
|
1348
|
998 |
209 |
if (ctx->_nfactors) { |
|
1349
|
1 |
997 |
if (ctx->_coffset >= _fr_chunk) { |
|
1352
|
1 |
0 |
if (chi > ctx->hi) chi = ctx->hi; |
|
1360
|
99 |
110 |
if (ctx->is_square_free && n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49))) |
|
|
52 |
47 |
if (ctx->is_square_free && n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49))) |
|
|
39 |
13 |
if (ctx->is_square_free && n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49))) |
|
|
34 |
5 |
if (ctx->is_square_free && n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49))) |
|
|
32 |
2 |
if (ctx->is_square_free && n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49))) |
|
|
2 |
30 |
if (ctx->is_square_free && n >= 49 && (!(n% 4) || !(n% 9) || !(n%25) || !(n%49))) |
|
1363
|
77 |
110 |
if (ctx->is_square_free) { |
|
1364
|
58 |
60 |
for (j = 1; j < nfactors; j++) |
|
1365
|
17 |
41 |
if (ctx->factors[j] == ctx->factors[j-1]) |
|
1367
|
17 |
60 |
if (j < nfactors) return 0; |
|
1374
|
0 |
0 |
if (ctx->_farray != 0) Safefree(ctx->_farray); |
|
1375
|
0 |
0 |
if (ctx->_nfactors != 0) Safefree(ctx->_nfactors); |
|
1386
|
0 |
23 |
if (maxrounds > p) maxrounds = p; |
|
1389
|
18 |
5 |
if (p&1) { |
|
1393
|
13930 |
0 |
for (t = g, k = 1; k < maxrounds; k++) { |
|
1394
|
18 |
13912 |
if (t == a) |
|
1396
|
0 |
13912 |
t = mont_mulmod(t, g, p); |
|
1397
|
0 |
13912 |
if (t == g) break; /* Stop at cycle */ |
|
1402
|
9 |
0 |
for (t = g, k = 1; k < maxrounds; k++) { |
|
1403
|
4 |
5 |
if (t == a) |
|
1406
|
1 |
4 |
if (t == g) break; /* Stop at cycle */ |
|
1449
|
0 |
4 |
if (s->failed) return 0; |
|
1450
|
0 |
4 |
if (s->round + rounds > n) rounds = n - s->round; |
|
1452
|
26785 |
2 |
for (i = 1; i <= rounds; i++) { |
|
1456
|
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 ); |
|
1457
|
2 |
26783 |
if (u == U) { |
|
1460
|
0 |
2 |
if (r1 == 0) { |
|
1461
|
0 |
0 |
if (verbose) printf("DLP Rho failure, r=0\n"); |
|
1471
|
0 |
2 |
if (G > 1) { |
|
1472
|
0 |
0 |
if (powmod(g,k,p) == a) { |
|
1473
|
0 |
0 |
if (verbose > 2) printf(" common GCD %"UVuf"\n", G2); |
|
1476
|
0 |
0 |
for (m = 0; m < G; m++) { |
|
1478
|
0 |
0 |
if (powmod(g,k,p) == a) break; |
|
1480
|
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); |
|
1484
|
0 |
2 |
if (powmod(g,k,p) != a) { |
|
1485
|
0 |
0 |
if (verbose > 2) printf("r1 = %"UVuf" r2 = %"UVuf" k = %"UVuf"\n", r1, r2, k); |
|
1486
|
0 |
0 |
if (verbose) printf("Incorrect DLP Rho solution: %"UVuf"\n", k); |
|
1494
|
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); |
|
1539
|
4137 |
2 |
if (top->nused == 0 || top->nused >= BSGS_ENTRIES_PER_PAGE) { |
|
|
0 |
4137 |
if (top->nused == 0 || top->nused >= BSGS_ENTRIES_PER_PAGE) { |
|
1551
|
2 |
2 |
while (head != 0) { |
|
1565
|
0 |
2 |
while (entry && entry->V != v) |
|
|
0 |
0 |
while (entry && entry->V != v) |
|
1568
|
2 |
0 |
if (!entry) { |
|
1579
|
0 |
0 |
while (entry && entry->V != v) |
|
|
0 |
0 |
while (entry && entry->V != v) |
|
1581
|
0 |
0 |
return (entry) ? entry->M : 0; |
|
1589
|
123 |
4137 |
while (entry && entry->V != v) |
|
|
123 |
0 |
while (entry && entry->V != v) |
|
1592
|
0 |
4137 |
if (entry) |
|
1615
|
0 |
3 |
if (n <= 2) return 0; /* Shouldn't be here with gorder this low */ |
|
1617
|
3 |
0 |
if (race_rho) { |
|
1619
|
1 |
2 |
if (result) { |
|
1620
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step 0\n"); |
|
1625
|
0 |
2 |
if (a == 0) return 0; /* We don't handle this case */ |
|
1630
|
0 |
2 |
hashmap_count = (m < 65537) ? 65537 : |
|
1631
|
0 |
0 |
(m > 40000000) ? 40000003 : |
|
1639
|
0 |
2 |
Newz(0, PAGES.table, hashmap_count, bsgs_hash_t*); |
|
1651
|
2069 |
0 |
for (i = 1; i <= m; i++) { |
|
1653
|
0 |
2069 |
if (gs_i) { bs_i = i; break; } |
|
1655
|
1 |
2068 |
if (S == aa) { /* We discovered the solution! */ |
|
1656
|
0 |
1 |
if (verbose) printf(" dlp bsgs: solution at BS step %"UVuf"\n", i+1); |
|
1661
|
0 |
2068 |
if (bs_i) { gs_i = i; break; } |
|
1663
|
2068 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
|
1 |
2067 |
if (race_rho && (i % 2048) == 0) { |
|
1665
|
1 |
0 |
if (result) { |
|
1666
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step %"UVuf"\n", i); |
|
1672
|
0 |
2 |
if (!result) { |
|
1674
|
0 |
0 |
if (!(gs_i || bs_i)) { |
|
|
0 |
0 |
if (!(gs_i || bs_i)) { |
|
1676
|
0 |
0 |
if (m < maxm && b > 8*m) b = 8*m; |
|
|
0 |
0 |
if (m < maxm && b > 8*m) b = 8*m; |
|
1677
|
0 |
0 |
for (i = m+1; i < b; i++) { |
|
1679
|
0 |
0 |
if (bs_i) { gs_i = i; break; } |
|
1681
|
0 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
|
0 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
1683
|
0 |
0 |
if (result) { |
|
1684
|
0 |
0 |
if (verbose) printf("rho found solution in BSGS step %"UVuf"\n", i); |
|
1691
|
0 |
0 |
if (gs_i || bs_i) { |
|
|
0 |
0 |
if (gs_i || bs_i) { |
|
1695
|
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)); |
|
1699
|
2 |
0 |
if (result != 0 && powmod(g,result,p) != a) { |
|
|
0 |
2 |
if (result != 0 && powmod(g,result,p) != a) { |
|
1700
|
0 |
0 |
if (verbose) printf("Incorrect DLP BSGS solution: %"UVuf"\n", result); |
|
1703
|
2 |
0 |
if (race_rho && result == 0) { |
|
|
0 |
2 |
if (race_rho && result == 0) { |
|
1715
|
0 |
16 |
if (a >= p) a %= p; |
|
1716
|
0 |
16 |
if (g >= p) g %= p; |
|
1718
|
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) |
|
1721
|
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); |
|
1725
|
15 |
0 |
if (n == 0 || n <= DLP_TRIAL_NUM) { |
|
|
12 |
3 |
if (n == 0 || n <= DLP_TRIAL_NUM) { |
|
1727
|
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"); |
|
1728
|
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; |
|
1733
|
3 |
0 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
|
0 |
3 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
1735
|
0 |
3 |
if (aorder == 0 && gorder != 0) return 0; |
|
|
0 |
0 |
if (aorder == 0 && gorder != 0) return 0; |
|
1736
|
3 |
0 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
|
0 |
3 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
1739
|
3 |
0 |
sqrtn = (n == 0) ? 0 : isqrt(n); |
|
1740
|
0 |
3 |
if (n == 0) n = p-1; |
|
1743
|
3 |
0 |
UV maxent = (sqrtn > 0) ? sqrtn+1 : 100000; |
|
1745
|
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"); |
|
1746
|
3 |
0 |
if (k != 0) return k; |
|
1747
|
0 |
0 |
if (sqrtn > 0 && sqrtn < maxent) return 0; |
|
|
0 |
0 |
if (sqrtn > 0 && sqrtn < maxent) return 0; |
|
1750
|
0 |
0 |
if (verbose) printf(" dlp doing exhaustive trial\n"); |
|
1762
|
0 |
5 |
if (p1 == 0) return 0; /* TODO: Should we plow on with p1=p-1? */ |
|
1764
|
0 |
5 |
if (nfactors == 1) |
|
1766
|
16 |
5 |
for (i = 0; i < nfactors; i++) { |
|
1768
|
1 |
16 |
pi = fac[i]; for (j = 1; j < exp[i]; j++) pi *= fac[i]; |
|
1776
|
5 |
0 |
if (i == 1 && powmod(g, x, p) == a) |
|
|
5 |
0 |
if (i == 1 && powmod(g, x, p) == a) |
|
1786
|
0 |
20 |
if (a >= p) a %= p; |
|
1787
|
0 |
20 |
if (g >= p) g %= p; |
|
1789
|
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) |
|
1796
|
15 |
3 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
|
2 |
13 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
1798
|
3 |
13 |
if (aorder == 0 && gorder != 0) return 0; |
|
|
0 |
3 |
if (aorder == 0 && gorder != 0) return 0; |
|
1799
|
13 |
3 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
|
0 |
13 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
1802
|
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)) { |
|
1803
|
0 |
11 |
if (verbose > 1) printf(" dlp trial znlog(%"UVuf",%"UVuf",%"UVuf")\n",a,g,p); |
|
1808
|
5 |
0 |
if (!is_prob_prime(gorder)) { |
|
1810
|
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"); |
|
1811
|
5 |
0 |
if (k != 0) return k; |