| line |
true |
false |
branch |
|
66
|
0 |
84600 |
if (sp < 1) sp = 1; |
|
67
|
0 |
84600 |
if (endsp > NPRIMES_SMALL-1) endsp = NPRIMES_SMALL-1; |
|
68
|
84600 |
0 |
if (sp > endsp || n == 1) return n; |
|
|
19679 |
64921 |
if (sp > endsp || n == 1) return n; |
|
72
|
64636 |
470287 |
if (f*f > n) break; |
|
73
|
23200 |
470287 |
while (n % f == 0) { |
|
77
|
470002 |
285 |
} while (++sp <= endsp); |
|
79
|
64640 |
281 |
if (f*f > n && n != 1) { |
|
|
63830 |
810 |
if (f*f > n && n != 1) { |
|
87
|
0 |
125 |
if (sp < 1) sp = 1; |
|
88
|
0 |
125 |
if (endsp > NPRIMES_SMALL-1) endsp = NPRIMES_SMALL-1; |
|
89
|
125 |
0 |
if (sp > endsp || n == 1) return n; |
|
|
0 |
125 |
if (sp > endsp || n == 1) return n; |
|
93
|
12 |
9159 |
if (f*f > n) break; |
|
94
|
213 |
9159 |
while (n % f == 0) { |
|
98
|
9046 |
113 |
} while (++sp <= endsp); |
|
100
|
12 |
113 |
if (f*f > n && n != 1) { |
|
|
12 |
0 |
if (f*f > n && n != 1) { |
|
114
|
84464 |
163 |
if (n > 1) { |
|
115
|
53165 |
84464 |
while ( (n & 1) == 0 ) { factors[nfactors++] = 2; n /= 2; } |
|
116
|
34025 |
84464 |
while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
117
|
17831 |
84464 |
while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
122
|
84502 |
125 |
: _trialuv(n, factors, &nfactors, sp, endsp); |
|
126
|
84331 |
296 |
if (n < 2017*2017 && f*f <= n) { /* Trial division from 431 to 2011 */ |
|
|
98 |
84233 |
if (n < 2017*2017 && f*f <= n) { /* Trial division from 431 to 2011 */ |
|
132
|
84331 |
296 |
if (f*f > n && n != 1) { |
|
|
0 |
84331 |
if (f*f > n && n != 1) { |
|
136
|
84627 |
0 |
if (newn) *newn = n; |
|
137
|
84627 |
0 |
if (lastf) *lastf = f; |
|
145
|
186 |
0 |
if (n > 3 && (k = powerof_ret(n, &root))) { |
|
|
8 |
178 |
if (n > 3 && (k = powerof_ret(n, &root))) { |
|
147
|
18 |
8 |
for (i = nfactors; i >= 0; i--) |
|
148
|
38 |
18 |
for (j = 0; j < k; j++) |
|
160
|
0 |
126 |
if (n < 4) { |
|
165
|
0 |
126 |
if (trial) { |
|
167
|
0 |
0 |
if (!(n&1)) { factors[0] = 2; factors[1] = n >> 1; return 2; } |
|
168
|
0 |
0 |
if (!(n%3)) { factors[0] = 3; factors[1] = n / 3; return 2; } |
|
169
|
0 |
0 |
if (!(n%5)) { factors[0] = 5; factors[1] = n / 5; return 2; } |
|
170
|
0 |
0 |
for (sp = 4; (f = primes_small[sp]) < 2011; sp++) { |
|
171
|
0 |
0 |
if ( (n % f) == 0 ) |
|
174
|
0 |
0 |
if (n < f*f) { factors[0] = n; return 1; } |
|
176
|
0 |
126 |
if (primality && is_prime(n)) { |
|
|
0 |
0 |
if (primality && is_prime(n)) { |
|
190
|
41 |
85 |
if (n <= 0xFFFFFFFFU) { |
|
192
|
41 |
0 |
if (nfactors > 1) return nfactors; |
|
198
|
85 |
0 |
UV const nbits = BITS_PER_WORD - clz(n); |
|
210
|
85 |
0 |
if (br_rounds > 0) { |
|
212
|
75 |
10 |
if (nfactors > 1) return nfactors; |
|
216
|
10 |
0 |
if (nfactors > 1) return nfactors; |
|
225
|
0 |
0 |
if (nbits <= 62) { |
|
227
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
231
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
234
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
236
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
238
|
0 |
0 |
if (nfactors > 1) return nfactors; |
|
256
|
84331 |
296 |
if (n == 1) return nfactors; |
|
260
|
113 |
183 |
if (n < 100000000 && n < f*f*f) { |
|
|
110 |
3 |
if (n < 100000000 && n < f*f*f) { |
|
261
|
65 |
45 |
if (MR32(n)) factors[nfactors++] = n; |
|
271
|
8 |
178 |
if (npowerfactors > 1) return nsmallfactors + npowerfactors; |
|
275
|
295 |
119 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
174 |
121 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
37 |
137 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
|
81 |
40 |
while ( (n >= f*f) && (!is_def_prime(n)) ) { |
|
277
|
118 |
0 |
if (split_success != 1 || tofac_stack[ntofac] == 1 || tofac_stack[ntofac] == n) |
|
|
118 |
0 |
if (split_success != 1 || tofac_stack[ntofac] == 1 || tofac_stack[ntofac] == n) |
|
|
0 |
118 |
if (split_success != 1 || tofac_stack[ntofac] == 1 || tofac_stack[ntofac] == n) |
|
283
|
296 |
0 |
if (n != 1) factors[nfactors++] = n; |
|
285
|
118 |
178 |
if (ntofac > 0) n = tofac_stack[ntofac-1]; |
|
286
|
118 |
178 |
} while (ntofac-- > 0); |
|
289
|
118 |
178 |
for (i = nsmallfactors+1; i < nfactors; i++) { |
|
291
|
194 |
48 |
for (j = i; j > 0 && factors[j-1] > fi; j--) |
|
|
124 |
70 |
for (j = i; j > 0 && factors[j-1] > fi; j--) |
|
305
|
852 |
70087 |
if (n < 4) { |
|
314
|
94275 |
70087 |
for (i = 1, j = 0; i < nfactors; i++) { |
|
315
|
30872 |
63403 |
if (fac[i] == fac[i-1]) |
|
325
|
0 |
0 |
if (nf->n == 0) { |
|
326
|
0 |
0 |
MPUassert(nf->nfactors == 1, "factored_t n=0 => nfactors = 0"); |
|
327
|
0 |
0 |
MPUassert(nf->f[0] == 0 && nf->e[0] == 1, "factored_t n=0 => vecprod = n"); |
|
|
0 |
0 |
MPUassert(nf->f[0] == 0 && nf->e[0] == 1, "factored_t n=0 => vecprod = n"); |
|
328
|
0 |
0 |
} else if (nf->n == 1) { |
|
329
|
0 |
0 |
MPUassert(nf->nfactors == 0, "factored_t n=1 => nfactors = 0"); |
|
333
|
0 |
0 |
MPUassert(nf->nfactors <= MPU_MAX_DFACTORS, "factored_t n has too many factors"); |
|
334
|
0 |
0 |
for (i = 0; i < nf->nfactors; i++) { |
|
335
|
0 |
0 |
MPUassert(is_prime(nf->f[i]), "factored_t n has non-prime factor"); |
|
336
|
0 |
0 |
MPUassert(lf < nf->f[i], "factored_t factors not in order"); |
|
338
|
0 |
0 |
MPUassert(nf->e[i] < BITS_PER_WORD, "factored_t exponent k too high"); |
|
339
|
0 |
0 |
MPUassert(nf->e[i] > 0, "factored_t exponent k too low"); |
|
340
|
0 |
0 |
if (nf->e[i] == 1) { |
|
344
|
0 |
0 |
MPUassert(t != UV_MAX, "factored_t f^e overflows") |
|
348
|
0 |
0 |
MPUassert(N == nf->n, "factored_t n is not equal to f^e * f^e ..."); |
|
353
|
0 |
0 |
for (i = 0; i < nf->nfactors; i++) |
|
359
|
13670 |
5835 |
for (i = 0; i < nf->nfactors; i++) |
|
360
|
52 |
13618 |
if (nf->e[i] > 1) |
|
369
|
33916 |
15266 |
for (i = 0; i < nf->nfactors; i++) |
|
370
|
57 |
33859 |
if (nf->e[i] > 1) |
|
372
|
7641 |
7625 |
return nf->nfactors % 2 ? -1 : 1; |
|
377
|
0 |
0 |
for (i = 0; i < nf->nfactors; i++) { |
|
379
|
0 |
0 |
while (e--) |
|
395
|
4 |
191 |
if (n <= 1) return (n==0); |
|
404
|
0 |
579 |
if (f < 2) f = 2; |
|
405
|
575 |
4 |
if (last == 0 || last*last > n) last = UV_MAX; |
|
|
319 |
256 |
if (last == 0 || last*last > n) last = UV_MAX; |
|
407
|
579 |
0 |
if (n < 4 || last < f) { |
|
|
43 |
536 |
if (n < 4 || last < f) { |
|
414
|
536 |
0 |
if (f < primes_small[NPRIMES_SMALL-1]) { |
|
415
|
0 |
536 |
while ( (n & 1) == 0 ) { factors[nfactors++] = 2; n >>= 1; } |
|
416
|
536 |
0 |
if (3<=last) while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
|
0 |
536 |
if (3<=last) while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
417
|
536 |
0 |
if (5<=last) while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
|
0 |
536 |
if (5<=last) while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
418
|
3598 |
4 |
for (sp = 4; sp < (int)NPRIMES_SMALL; sp++) { |
|
420
|
3250 |
348 |
if (f*f > n || f > last) break; |
|
|
3066 |
184 |
if (f*f > n || f > last) break; |
|
421
|
198 |
3066 |
while ( (n%f) == 0 ) { |
|
428
|
188 |
348 |
if (f*f <= n && f <= last) { |
|
|
4 |
184 |
if (f*f <= n && f <= last) { |
|
430
|
2 |
2 |
if (limit > last) limit = last; |
|
432
|
14074 |
4 |
while (f <= limit) { |
|
433
|
2 |
14072 |
if ( (n%f) == 0 ) { |
|
437
|
0 |
2 |
} while ( (n%f) == 0 ); |
|
439
|
2 |
0 |
if (newlimit < limit) limit = newlimit; |
|
446
|
526 |
10 |
if (n != 1) |
|
457
|
8438 |
3655 |
for (i = 0; i < nf.nfactors; i++) { |
|
460
|
11592 |
8438 |
for (j = 0; j < e; j++) { |
|
462
|
29851 |
11592 |
for (s = 0; s < scount; s++) { |
|
464
|
29517 |
334 |
if (t <= k) |
|
478
|
3828 |
3 |
if (n == 0 || maxd == 0) { |
|
|
2 |
3826 |
if (n == 0 || maxd == 0) { |
|
481
|
3736 |
90 |
} else if (n == 1 || maxd == 1) { |
|
|
81 |
3655 |
} else if (n == 1 || maxd == 1) { |
|
488
|
2641 |
1014 |
if (maxd > n) maxd = n; |
|
494
|
4783 |
3655 |
for (i = 1; i < nf.nfactors; i++) |
|
496
|
0 |
3655 |
New(0, divs, ndivisors, UV); |
|
525
|
1589 |
0 |
if (k > 11 || (k > 0 && n >= sigma_overflow[k-1])) return 0; |
|
|
260 |
1329 |
if (k > 11 || (k > 0 && n >= sigma_overflow[k-1])) return 0; |
|
|
0 |
260 |
if (k > 11 || (k > 0 && n >= sigma_overflow[k-1])) return 0; |
|
527
|
370 |
1219 |
if (n <= 1) return n; |
|
530
|
970 |
249 |
if (k == 0) { |
|
531
|
1360 |
970 |
for (i = 0; i < nf.nfactors; i++) |
|
533
|
157 |
92 |
} else if (k == 1) { |
|
534
|
270 |
157 |
for (i = 0; i < nf.nfactors; i++) { |
|
538
|
102 |
270 |
while (e-- > 1) { |
|
545
|
140 |
92 |
for (i = 0; i < nf.nfactors; i++) { |
|
549
|
207 |
140 |
for (j = 1; j < k; j++) pk *= f; |
|
552
|
119 |
140 |
while (e-- > 1) { |
|
572
|
195 |
1 |
if (f == 1 || f == n) { |
|
|
0 |
195 |
if (f == 1 || f == n) { |
|
576
|
73 |
122 |
factors[f >= g] = f; |
|
577
|
122 |
73 |
factors[f < g] = g; |
|
578
|
0 |
195 |
MPUassert( factors[0] * factors[1] == n , "incorrect factoring"); |
|
593
|
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"); |
|
599
|
8 |
2 |
while (r != 0) { |
|
600
|
0 |
8 |
if (rounds-- == 0) return no_factor(n,factors); |
|
606
|
18 |
8 |
} while (r > 0); |
|
618
|
3 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in holf_factor"); |
|
|
0 |
3 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in holf_factor"); |
|
622
|
0 |
3 |
if (is_perfect_square_ret(n,&root)) |
|
625
|
3 |
0 |
if (n <= (UV_MAX >> 6)) { /* Try with premultiplier first */ |
|
626
|
0 |
3 |
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 : |
|
631
|
6839 |
0 |
while (rounds--) { |
|
634
|
2 |
6837 |
if (is_perfect_square_ret(m, &root)) { |
|
636
|
2 |
0 |
if (f > 1 && f < n) |
|
|
2 |
0 |
if (f > 1 && f < n) |
|
639
|
1 |
6836 |
if (ni >= (ni+npre)) break; |
|
642
|
0 |
1 |
if (rounds == (UV) -1) |
|
646
|
1 |
0 |
for (i = 1; i <= rounds; i++) { |
|
652
|
1 |
0 |
if (is_perfect_square_ret(m, &root)) { |
|
653
|
1 |
0 |
f = gcd_ui( (s>root) ? s-root : root-s, n); |
|
664
|
0 |
86 |
if (n < 3) return no_factor(n,factors); |
|
665
|
0 |
86 |
if (!(n&1)) { factors[0] = 2; factors[1] = n/2; return 2; } |
|
666
|
1 |
85 |
if (is_perfect_square_ret(n,&f)) { factors[0] = factors[1] = f; return 2; } |
|
669
|
3883 |
0 |
while (rounds--) { |
|
672
|
85 |
3798 |
if (is_perfect_square_ret(m, &f)) { |
|
674
|
85 |
0 |
if (f > 1 && f < n) |
|
|
85 |
0 |
if (f > 1 && f < n) |
|
677
|
0 |
3798 |
if (ni >= (ni+npre)) break; /* We've overflowed */ |
|
689
|
97 |
0 |
UV const nbits = BITS_PER_WORD - clz(n); |
|
690
|
95 |
2 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
87 |
8 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
61 |
26 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
22 |
39 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
695
|
97 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pbrent_factor"); |
|
|
0 |
97 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pbrent_factor"); |
|
700
|
956 |
10 |
while (rounds > 0) { |
|
704
|
6137 |
867 |
while (rleft > 0) { |
|
709
|
4274 |
1863 |
if (n < (1ULL << 63)) { |
|
711
|
2084 |
2190 |
m = ABSDIFF(Xi,Xm); |
|
712
|
1138997 |
4274 |
while (--irounds > 0) { |
|
714
|
543095 |
595902 |
f = ABSDIFF(Xi,Xm); |
|
717
|
1503 |
360 |
} else if (a == mont1) { |
|
719
|
691 |
812 |
m = ABSDIFF(Xi,Xm); |
|
720
|
460813 |
1503 |
while (--irounds > 0) { |
|
722
|
208276 |
252537 |
f = ABSDIFF(Xi,Xm); |
|
727
|
216 |
144 |
m = ABSDIFF(Xi,Xm); |
|
728
|
108054 |
360 |
while (--irounds > 0) { |
|
730
|
67606 |
40448 |
f = ABSDIFF(Xi,Xm); |
|
735
|
89 |
6048 |
if (f != 1) |
|
739
|
867 |
89 |
if (f == 1) { |
|
743
|
2 |
87 |
if (f == n) { /* back up, with safety */ |
|
746
|
0 |
306 |
if (n < (1ULL << 63) || a == mont1) |
|
|
0 |
0 |
if (n < (1ULL << 63) || a == mont1) |
|
747
|
0 |
306 |
Xi = mont_mulmod(Xi,Xi+a,n); |
|
749
|
0 |
0 |
Xi = addmod(mont_mulmod(Xi,Xi,n),a,n); |
|
750
|
28 |
278 |
m = ABSDIFF(Xi,Xm); |
|
752
|
304 |
2 |
} while (f == 1 && r-- != 0); |
|
|
304 |
0 |
} while (f == 1 && r-- != 0); |
|
754
|
89 |
0 |
if (f == 0 || f == n) { |
|
|
2 |
87 |
if (f == 0 || f == n) { |
|
755
|
0 |
2 |
if (fails-- <= 0) break; |
|
831
|
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"); |
|
835
|
2 |
0 |
while (rounds-- > 0) { |
|
837
|
128 |
2 |
for (i = 0; i < inner; i++) { |
|
841
|
52 |
76 |
f = (U > V) ? U-V : V-U; |
|
845
|
0 |
2 |
if (f == 1) |
|
847
|
2 |
0 |
if (f == n) { /* back up to find a factor*/ |
|
854
|
1 |
5 |
f = gcd_ui( (U > V) ? U-V : V-U, n); |
|
855
|
4 |
2 |
} while (f == 1 && i-- != 0); |
|
|
4 |
0 |
} while (f == 1 && i-- != 0); |
|
857
|
2 |
0 |
if (f == 0 || f == n) { |
|
|
0 |
2 |
if (f == 0 || f == n) { |
|
858
|
0 |
0 |
if (fails-- <= 0) break; |
|
886
|
8 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pminus1_factor"); |
|
|
0 |
8 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pminus1_factor"); |
|
888
|
5 |
3 |
if (B1 <= primes_small[NPRIMES_SMALL-2]) { |
|
890
|
335 |
3 |
for (i = 1; primes_small[i] <= B1; i++) { |
|
892
|
40 |
295 |
if (q <= sqrtB1) { |
|
894
|
52 |
40 |
while (k <= kmin) k *= q; |
|
897
|
9 |
326 |
if ( (j++ % 32) == 0) { |
|
898
|
0 |
9 |
PMINUS1_RECOVER_A; |
|
899
|
9 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
|
7 |
2 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
904
|
0 |
5 |
PMINUS1_RECOVER_A; |
|
906
|
3 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
3 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
9 |
119 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
6 |
3 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
3 |
3 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
18 |
101 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
18 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
18 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
18 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
119 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
0 |
128 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
908
|
128 |
0 |
if (q <= sqrtB1) { |
|
910
|
204 |
128 |
while (k <= kmin) k *= q; |
|
913
|
4 |
124 |
if ( (j++ % 32) == 0) { |
|
914
|
0 |
4 |
PMINUS1_RECOVER_A; |
|
915
|
4 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
|
1 |
3 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
920
|
0 |
3 |
PMINUS1_RECOVER_A; |
|
922
|
0 |
8 |
if (a == 0) return no_factor(n,factors); |
|
926
|
5 |
3 |
if (f == n) { |
|
928
|
5 |
0 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
4 |
1 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
10 |
10 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
6 |
4 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
4 |
2 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
1 |
9 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
1 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
1 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
1 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
10 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
|
0 |
20 |
START_DO_FOR_EACH_PRIME(saveq, B1) { |
|
930
|
89 |
20 |
while (k <= kmin) k *= p; |
|
934
|
5 |
15 |
if (f != 1) |
|
949
|
2 |
6 |
if (f == 1 && B2 > B1) { |
|
|
1 |
1 |
if (f == 1 && B2 > B1) { |
|
958
|
19 |
1 |
for (j = 1; j < 20; j++) { |
|
966
|
1 |
0 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
1 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
1280 |
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 ) { |
|
|
369 |
911 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
370 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
1 |
369 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
369 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
1280 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
|
0 |
1280 |
START_DO_FOR_EACH_PRIME( q+1, B2 ) { |
|
972
|
0 |
1280 |
if (qdiff >= 111) { |
|
976
|
0 |
1280 |
if (bmdiff == 0) { |
|
977
|
0 |
0 |
if (precomp_bm[qdiff-1] != 0) |
|
985
|
0 |
1280 |
if (a == 0) break; |
|
987
|
20 |
1260 |
if ( (j++ % 64) == 0 ) { |
|
989
|
1 |
19 |
if (f != 1) |
|
1004
|
6 |
0 |
UV bit = UVCONST(1) << (clz(exp)-1); |
|
1005
|
339 |
6 |
while (bit) { |
|
1007
|
15 |
324 |
if ( exp & bit ) { |
|
1022
|
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"); |
|
1027
|
2 |
0 |
START_DO_FOR_EACH_PRIME(2, B1) { |
|
|
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) { |
|
1029
|
4 |
0 |
if (p < sqrtB1) { |
|
1031
|
17 |
4 |
while (k <= kmin) |
|
1035
|
4 |
0 |
if (X1 != 2) { |
|
1037
|
2 |
2 |
if (f != 1 && f != n) break; |
|
|
2 |
0 |
if (f != 1 && f != n) break; |
|
1040
|
0 |
2 |
if (X2 != 2) { |
|
1042
|
0 |
0 |
if (f != 1 && f != n) break; |
|
|
0 |
0 |
if (f != 1 && f != n) break; |
|
1098
|
0 |
3 |
if (i & 0x1) { |
|
1104
|
0 |
4 |
if (i >= imax) { |
|
1117
|
3 |
1 |
if (is_perfect_square_ret(Qn,&root)) |
|
1143
|
2 |
1 |
SYMMETRY_POINT_ITERATION; |
|
1144
|
1 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1145
|
0 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1146
|
0 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1147
|
0 |
0 |
if (j++ > 2000000) { |
|
1154
|
3 |
0 |
if (t1 > 1) |
|
1181
|
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"); |
|
1184
|
0 |
2 |
if (n > SQUFOF_MAX) |
|
1187
|
76 |
2 |
for (i = 0; i < NSQUFOF_MULT; i++) { |
|
1193
|
2 |
0 |
while (mults_racing > 0 && rounds_done < rounds) { |
|
|
2 |
0 |
while (mults_racing > 0 && rounds_done < rounds) { |
|
1194
|
3 |
0 |
for (i = 0; i < NSQUFOF_MULT && rounds_done < rounds; i++) { |
|
|
3 |
0 |
for (i = 0; i < NSQUFOF_MULT && rounds_done < rounds; i++) { |
|
1195
|
0 |
3 |
if (mult_save[i].valid == 0) continue; |
|
1198
|
3 |
0 |
if (mult_save[i].valid == -1) { |
|
1199
|
0 |
3 |
if ((SQUFOF_MAX / mult) < n) { |
|
1210
|
0 |
3 |
if (mult_save[i].Qn == 0) |
|
1216
|
3 |
0 |
if (mult_save[i].imax < 20) mult_save[i].imax = 20; |
|
1217
|
0 |
3 |
if (mult_save[i].imax > rounds) mult_save[i].imax = rounds; |
|
1219
|
0 |
3 |
if (mults_racing == 1) /* Do all rounds if only one multiplier left */ |
|
1222
|
3 |
0 |
if (f64 > 1) { |
|
1224
|
2 |
1 |
if (f64red > 1) { |
|
1233
|
1 |
0 |
if (mult_save[i].valid == 0) |
|
1246
|
0 |
0 |
for (i = 0; i < SQR_TAB_SIZE; i++) |
|
1254
|
0 |
2 |
const double Tune = ((n >> 31) >> 5) ? 3.5 : 5.0; |
|
1259
|
0 |
2 |
if (!(n&1)) return found_factor(n, 2, factors); |
|
1263
|
2 |
0 |
if (do_trial) { |
|
1265
|
2 |
0 |
if (FirstCut < 84) FirstCut = 84; |
|
1266
|
0 |
2 |
if (FirstCut > 65535) FirstCut = 65535; |
|
1267
|
10 |
0 |
for (ip = 2; ip < NPRIMES_SMALL; ip++) { |
|
1269
|
0 |
10 |
if (p >= FirstCut) |
|
1271
|
2 |
8 |
if (n % p == 0) |
|
1277
|
0 |
0 |
if (n >= UVCONST(8796393022207)) return no_factor(n,factors); |
|
1283
|
0 |
0 |
if (!sqr_tab_init) make_sqr_tab(); |
|
1286
|
0 |
0 |
for (k = 1; k <= Bred; k++) { |
|
1287
|
0 |
0 |
if (k&1) { inc = 4; r = (k+n) % 4; } |
|
1291
|
0 |
0 |
if (kN >= UVCONST(1152921504606846976)) return no_factor(n,factors); |
|
1295
|
0 |
0 |
x = (k < SQR_TAB_SIZE) ? sqrtn * sqr_tab[k] : sqrt((double)kN); |
|
1297
|
0 |
0 |
if ((UV)a * (UV)a == kN) |
|
1305
|
0 |
0 |
for (a = b; a <= U; c += inc*(a+a+inc), a += inc) { |
|
1307
|
0 |
0 |
if (is_perfect_square_ret(c,&b)) { |
|
1313
|
0 |
0 |
if (do_trial) { |
|
1314
|
0 |
0 |
if (B > 65535) B = 65535; |
|
1320
|
0 |
0 |
if (ip >= NPRIMES_SMALL) ip = NPRIMES_SMALL-1; |
|
1332
|
2 |
1 |
if (B == 0) { B = log2floor(n); B = 8*B*B; } |
|
|
2 |
0 |
if (B == 0) { B = log2floor(n); B = 8*B*B; } |
|
1333
|
2 |
1 |
if (B > isqrt(n)) B = isqrt(n); |
|
1336
|
0 |
3 |
x = (initx == 0) ? 72 : initx; |
|
1339
|
3 |
0 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
3 |
0 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
6 |
93 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
3 |
3 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
2 |
1 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
16 |
77 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
0 |
16 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
0 |
16 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
0 |
16 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
0 |
93 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
|
0 |
99 |
START_DO_FOR_EACH_PRIME(2, B) { |
|
1340
|
14 |
85 |
if (p <= sqrtB) { |
|
1343
|
14 |
0 |
if (plgp < UV_MAX) { |
|
1346
|
0 |
0 |
for (i = 1; i <= lgp; i++) |
|
1352
|
3 |
96 |
f = gcd_ui(x-1, n); if (f > 1) break; |
|
1355
|
3 |
0 |
if (f > 1 && f < n) |
|
|
3 |
0 |
if (f > 1 && f < n) |
|
1367
|
6 |
0 |
if (sqrtn < 10000000U) return 1; /* Below 10^14 */ |
|
1368
|
0 |
0 |
if (sqrtn < 35000000U) return (range > 900); /* Below 10^15 */ |
|
1369
|
0 |
0 |
if (sqrtn < 100000000U) return (range > 1700); /* Below 10^16 */ |
|
1370
|
0 |
0 |
if (sqrtn < 350000000U) return (range > 3400); /* Below 10^17 */ |
|
1371
|
0 |
0 |
if (sqrtn < 1000000000U) return (range > 5500); /* Below 10^18 */ |
|
1372
|
0 |
0 |
if (sqrtn < 3500000000U) return (range > 17000); /* Below 10^19 */ |
|
1381
|
0 |
3 |
New(0, N, hi-lo+1, UV); |
|
1382
|
3010 |
3 |
for (j = 0; j < n; j++) { |
|
1386
|
0 |
3 |
sievelim = _fr_full_sieve(sqrthi, hi-lo) ? sqrthi : icbrt(hi); |
|
1387
|
3 |
0 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
3 |
0 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
9 |
399 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
6 |
3 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
3 |
3 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
90 |
309 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
0 |
90 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
0 |
90 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
0 |
90 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
0 |
399 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
|
3 |
405 |
START_DO_FOR_EACH_PRIME(2, sievelim) { |
|
1389
|
6 |
399 |
if (square_free == 0) { |
|
1391
|
14 |
6 |
for (q = p; q <= kmin; q *= p) { |
|
1393
|
13 |
1 |
if (A < lo) A += q; |
|
1394
|
463 |
14 |
for (j = A-lo; j < n; j += q) { |
|
1401
|
399 |
0 |
if (A < lo) A += q; |
|
1402
|
1240 |
399 |
for (j = A-lo; j < n; j += q) { |
|
1407
|
396 |
3 |
if (A < lo) A += q; |
|
1408
|
5694 |
399 |
for (j = A-lo; j < n; j += q) { |
|
1409
|
3121 |
2573 |
if (N[j] > 0) { |
|
1417
|
3 |
0 |
if (sievelim == sqrthi) { |
|
1419
|
3010 |
3 |
for (j = 0; j < n; j++) { |
|
1420
|
316 |
2694 |
if (N[j] == 1) |
|
1422
|
1609 |
1085 |
else if (N[j] > 0 && N[j] != j+lo) |
|
|
1138 |
471 |
else if (N[j] > 0 && N[j] != j+lo) |
|
1427
|
0 |
0 |
for (j = 0; j < n; j++) { |
|
1429
|
0 |
0 |
if (N[j] > 0 && N[j] != rem) { |
|
|
0 |
0 |
if (N[j] > 0 && N[j] != rem) { |
|
1430
|
0 |
0 |
if (N[j] != 1) |
|
1432
|
0 |
0 |
if (square_free && is_perfect_square(rem)) { |
|
|
0 |
0 |
if (square_free && is_perfect_square(rem)) { |
|
1450
|
3 |
12 |
if (hi-lo+1 > 100) { /* Sieve in chunks */ |
|
1451
|
2 |
1 |
if (square_free) ctx._noffset = (hi <= 42949672965UL) ? 10 : 15; |
|
|
2 |
0 |
if (square_free) ctx._noffset = (hi <= 42949672965UL) ? 10 : 15; |
|
1452
|
1 |
0 |
else ctx._noffset = BITS_PER_WORD - clz(hi); |
|
1455
|
0 |
3 |
New(0, ctx._farray, _fr_chunk * ctx._noffset, UV); |
|
1458
|
0 |
3 |
if (!_fr_full_sieve(t, hi-lo)) t = icbrt(hi); |
|
1462
|
2 |
10 |
New(0, ctx.factors, square_free ? 15 : 63, UV); |
|
1473
|
0 |
3259 |
if (ctx->n >= ctx->hi) |
|
1476
|
3010 |
249 |
if (ctx->_nfactors) { |
|
1477
|
3 |
3007 |
if (ctx->_coffset >= _fr_chunk) { |
|
1480
|
0 |
3 |
if (chi > ctx->hi || chi < clo) chi = ctx->hi; |
|
|
0 |
0 |
if (chi > ctx->hi || chi < clo) chi = ctx->hi; |
|
1488
|
99 |
150 |
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))) |
|
1491
|
77 |
150 |
if (ctx->is_square_free) { |
|
1492
|
58 |
60 |
for (j = 1; j < nfactors; j++) |
|
1493
|
17 |
41 |
if (ctx->factors[j] == ctx->factors[j-1]) |
|
1495
|
17 |
60 |
if (j < nfactors) return 0; |
|
1502
|
15 |
0 |
if (ctx->_farray != 0) Safefree(ctx->_farray); |
|
1503
|
3 |
12 |
if (ctx->_nfactors != 0) Safefree(ctx->_nfactors); |
|
1516
|
0 |
4 |
New(0, N, range, UV); |
|
1519
|
10220 |
4 |
for (i = lo; i <= hi && i >= lo; i++) { |
|
|
10220 |
0 |
for (i = lo; i <= hi && i >= lo; i++) { |
|
1521
|
5112 |
5108 |
if (!(i&1) && i >= 2) { |
|
|
5112 |
0 |
if (!(i&1) && i >= 2) { |
|
1524
|
5100 |
5112 |
while (!(k&1)) { nz++; k >>= 1; } |
|
1525
|
0 |
5112 |
nf[i-lo] = (with_multiplicity) ? nz : 1; |
|
1530
|
4 |
0 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
4 |
0 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
8 |
40 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
8 |
0 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
4 |
4 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
4 |
36 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
0 |
4 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
0 |
4 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
0 |
4 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
0 |
40 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
|
4 |
44 |
START_DO_FOR_EACH_PRIME(3, sqrtn) { |
|
1532
|
1 |
43 |
for (i = P_GT_LO_0(p,p,lo); i < range; i += p) |
|
|
13086 |
44 |
for (i = P_GT_LO_0(p,p,lo); i < range; i += p) |
|
1534
|
70 |
44 |
for (pk = p*p; pk <= hi; pk *= p) { |
|
1535
|
35 |
35 |
for (i = P_GT_LO_0(pk,pk,lo); i < range; i += pk) |
|
|
2746 |
70 |
for (i = P_GT_LO_0(pk,pk,lo); i < range; i += pk) |
|
1536
|
0 |
2746 |
{ N[i] *= p; if (with_multiplicity) nf[i]++; } |
|
1537
|
0 |
70 |
if (pk >= maxpk) break; /* Overflow protection */ |
|
1541
|
10220 |
4 |
for (i = 0; i < range; i++) |
|
1542
|
6821 |
3399 |
if (N[i] < (lo+i)) |
|
1545
|
0 |
4 |
if (lo == 0) nf[0] = 1; |
|
1556
|
3 |
23 |
if (maxrounds > p) maxrounds = p; |
|
1559
|
21 |
5 |
if (p&1) { |
|
1563
|
13934 |
0 |
for (t = g, k = 1; k < maxrounds; k++) { |
|
1564
|
21 |
13913 |
if (t == a) |
|
1566
|
0 |
13913 |
t = mont_mulmod(t, g, p); |
|
1567
|
0 |
13913 |
if (t == g) break; /* Stop at cycle */ |
|
1572
|
9 |
0 |
for (t = g, k = 1; k < maxrounds; k++) { |
|
1573
|
4 |
5 |
if (t == a) |
|
1576
|
1 |
4 |
if (t == g) break; /* Stop at cycle */ |
|
1619
|
0 |
7 |
if (s->failed) return 0; |
|
1620
|
0 |
7 |
if (s->round + rounds > n) rounds = n - s->round; |
|
1622
|
41388 |
3 |
for (i = 1; i <= rounds; i++) { |
|
1626
|
0 |
41388 |
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 ); |
|
1627
|
4 |
41384 |
if (u == U) { |
|
1630
|
0 |
4 |
if (r1 == 0) { |
|
1631
|
0 |
0 |
if (verbose) printf("DLP Rho failure, r=0\n"); |
|
1641
|
1 |
3 |
if (G > 1) { |
|
1642
|
0 |
1 |
if (powmod(g,k,p) == a) { |
|
1643
|
0 |
0 |
if (verbose > 2) printf(" common GCD %"UVuf"\n", G2); |
|
1646
|
128 |
1 |
for (m = 0; m < G; m++) { |
|
1648
|
0 |
128 |
if (powmod(g,k,p) == a) break; |
|
1650
|
0 |
1 |
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); |
|
1654
|
1 |
3 |
if (powmod(g,k,p) != a) { |
|
1655
|
0 |
1 |
if (verbose > 2) printf("r1 = %"UVuf" r2 = %"UVuf" k = %"UVuf"\n", r1, r2, k); |
|
1656
|
0 |
1 |
if (verbose) printf("Incorrect DLP Rho solution: %"UVuf"\n", k); |
|
1664
|
0 |
7 |
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); |
|
1709
|
6919 |
4 |
if (top->nused == 0 || top->nused >= BSGS_ENTRIES_PER_PAGE) { |
|
|
0 |
6919 |
if (top->nused == 0 || top->nused >= BSGS_ENTRIES_PER_PAGE) { |
|
1721
|
4 |
4 |
while (head != 0) { |
|
1735
|
0 |
4 |
while (entry && entry->V != v) |
|
|
0 |
0 |
while (entry && entry->V != v) |
|
1738
|
4 |
0 |
if (!entry) { |
|
1749
|
30 |
827 |
while (entry && entry->V != v) |
|
|
29 |
1 |
while (entry && entry->V != v) |
|
1751
|
1 |
827 |
return (entry) ? entry->M : 0; |
|
1759
|
173 |
6919 |
while (entry && entry->V != v) |
|
|
173 |
0 |
while (entry && entry->V != v) |
|
1762
|
0 |
6919 |
if (entry) |
|
1785
|
0 |
5 |
if (n <= 2) return 0; /* Shouldn't be here with gorder this low */ |
|
1787
|
5 |
0 |
if (race_rho) { |
|
1789
|
1 |
4 |
if (result) { |
|
1790
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step 0\n"); |
|
1795
|
0 |
4 |
if (a == 0) return 0; /* We don't handle this case */ |
|
1800
|
0 |
4 |
hashmap_count = (m < 65537) ? 65537 : |
|
1801
|
0 |
0 |
(m > 40000000) ? 40000003 : |
|
1809
|
0 |
4 |
Newz(0, PAGES.table, hashmap_count, bsgs_hash_t*); |
|
1821
|
3460 |
2 |
for (i = 1; i <= m; i++) { |
|
1823
|
0 |
3460 |
if (gs_i) { bs_i = i; break; } |
|
1825
|
1 |
3459 |
if (S == aa) { /* We discovered the solution! */ |
|
1826
|
0 |
1 |
if (verbose) printf(" dlp bsgs: solution at BS step %"UVuf"\n", i+1); |
|
1831
|
0 |
3459 |
if (bs_i) { gs_i = i; break; } |
|
1833
|
3459 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
|
1 |
3458 |
if (race_rho && (i % 2048) == 0) { |
|
1835
|
1 |
0 |
if (result) { |
|
1836
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step %"UVuf"\n", i); |
|
1842
|
2 |
2 |
if (!result) { |
|
1844
|
2 |
0 |
if (!(gs_i || bs_i)) { |
|
|
2 |
0 |
if (!(gs_i || bs_i)) { |
|
1846
|
2 |
0 |
if (m < maxm && b > 8*m) b = 8*m; |
|
|
2 |
0 |
if (m < maxm && b > 8*m) b = 8*m; |
|
1847
|
828 |
0 |
for (i = m+1; i < b; i++) { |
|
1849
|
1 |
827 |
if (bs_i) { gs_i = i; break; } |
|
1851
|
827 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
|
1 |
826 |
if (race_rho && (i % 2048) == 0) { |
|
1853
|
1 |
0 |
if (result) { |
|
1854
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step %"UVuf"\n", i); |
|
1861
|
1 |
1 |
if (gs_i || bs_i) { |
|
|
0 |
1 |
if (gs_i || bs_i) { |
|
1865
|
0 |
4 |
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)); |
|
1869
|
4 |
0 |
if (result != 0 && powmod(g,result,p) != a) { |
|
|
0 |
4 |
if (result != 0 && powmod(g,result,p) != a) { |
|
1870
|
0 |
0 |
if (verbose) printf("Incorrect DLP BSGS solution: %"UVuf"\n", result); |
|
1873
|
4 |
0 |
if (race_rho && result == 0) { |
|
|
0 |
4 |
if (race_rho && result == 0) { |
|
1885
|
0 |
21 |
if (a >= p) a %= p; |
|
1886
|
0 |
21 |
if (g >= p) g %= p; |
|
1888
|
20 |
1 |
if (a == 1 || g == 0 || p <= 2) |
|
|
20 |
0 |
if (a == 1 || g == 0 || p <= 2) |
|
|
0 |
20 |
if (a == 1 || g == 0 || p <= 2) |
|
1891
|
0 |
20 |
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); |
|
1895
|
20 |
0 |
if (n == 0 || n <= DLP_TRIAL_NUM) { |
|
|
15 |
5 |
if (n == 0 || n <= DLP_TRIAL_NUM) { |
|
1897
|
0 |
15 |
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"); |
|
1898
|
0 |
15 |
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; |
|
1903
|
5 |
0 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
|
0 |
5 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
1905
|
0 |
5 |
if (aorder == 0 && gorder != 0) return 0; |
|
|
0 |
0 |
if (aorder == 0 && gorder != 0) return 0; |
|
1906
|
5 |
0 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
|
0 |
5 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
1910
|
5 |
0 |
sqrtn = (n == 0) ? 0 : isqrt(n); |
|
1911
|
0 |
5 |
if (n == 0) n = p-1; |
|
1914
|
5 |
0 |
UV maxent = (sqrtn > 0) ? sqrtn+1 : 100000; |
|
1916
|
0 |
5 |
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"); |
|
1917
|
5 |
0 |
if (k != 0) return k; |
|
1918
|
0 |
0 |
if (sqrtn > 0 && sqrtn < maxent) return 0; |
|
|
0 |
0 |
if (sqrtn > 0 && sqrtn < maxent) return 0; |
|
1921
|
0 |
0 |
if (verbose) printf(" dlp doing exhaustive trial\n"); |
|
1932
|
0 |
6 |
if (p1 == 0) return 0; /* TODO: Should we plow on with p1=p-1? */ |
|
1934
|
1 |
5 |
if (pf.nfactors == 1) |
|
1936
|
16 |
5 |
for (i = 0; i < pf.nfactors; i++) { |
|
1944
|
5 |
0 |
if (chinese(&x, 0, sol, mod, pf.nfactors) == 1 && powmod(g, x, p) == a) |
|
|
5 |
0 |
if (chinese(&x, 0, sol, mod, pf.nfactors) == 1 && powmod(g, x, p) == a) |
|
1954
|
0 |
22 |
if (a >= p) a %= p; |
|
1955
|
0 |
22 |
if (g >= p) g %= p; |
|
1957
|
20 |
2 |
if (a == 1 || g == 0 || p <= 2) |
|
|
20 |
0 |
if (a == 1 || g == 0 || p <= 2) |
|
|
0 |
20 |
if (a == 1 || g == 0 || p <= 2) |
|
1964
|
17 |
3 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
|
2 |
15 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
1967
|
3 |
15 |
if (aorder == 0 && gorder != 0) return 0; |
|
|
0 |
3 |
if (aorder == 0 && gorder != 0) return 0; |
|
1968
|
15 |
3 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
|
0 |
15 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
1971
|
17 |
1 |
if (a == 0 || p < DLP_TRIAL_NUM || (gorder > 0 && gorder < DLP_TRIAL_NUM)) { |
|
|
7 |
10 |
if (a == 0 || p < DLP_TRIAL_NUM || (gorder > 0 && gorder < DLP_TRIAL_NUM)) { |
|
|
7 |
0 |
if (a == 0 || p < DLP_TRIAL_NUM || (gorder > 0 && gorder < DLP_TRIAL_NUM)) { |
|
|
0 |
7 |
if (a == 0 || p < DLP_TRIAL_NUM || (gorder > 0 && gorder < DLP_TRIAL_NUM)) { |
|
1972
|
0 |
11 |
if (verbose > 1) printf(" dlp trial znlog(%"UVuf",%"UVuf",%"UVuf")\n",a,g,p); |
|
1977
|
6 |
1 |
if (!is_prob_prime(gorder)) { |
|
1979
|
0 |
6 |
if (verbose) printf(" dlp PH %s\n", k!=0 ? "success" : "failure"); |
|
|
0 |
0 |
if (verbose) printf(" dlp PH %s\n", k!=0 ? "success" : "failure"); |
|
1980
|
6 |
0 |
if (k != 0) return k; |