| line |
true |
false |
branch |
|
60
|
33475 |
151 |
if (n > 1) { |
|
61
|
14264 |
33475 |
while ( (n & 1) == 0 ) { factors[nfactors++] = 2; n /= 2; } |
|
62
|
10234 |
33475 |
while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
63
|
5882 |
33475 |
while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
66
|
26727 |
6899 |
if (f*f <= n) { |
|
70
|
26639 |
88 |
if (n <= 4294967295U) { |
|
72
|
226484 |
110 |
while (sp < lastsp) { |
|
73
|
13129 |
226484 |
while ( (un%f) == 0 ) { |
|
78
|
26529 |
199955 |
if (f*f > un) break; |
|
82
|
6236 |
76 |
while (sp < lastsp) { |
|
83
|
168 |
6236 |
while ( (n%f) == 0 ) { |
|
88
|
12 |
6224 |
if (f*f > n) break; |
|
92
|
26563 |
164 |
if (n < 2011*2011 && f*f <= n) { /* Trial division from 431 to 2003 */ |
|
|
22 |
26541 |
if (n < 2011*2011 && f*f <= n) { /* Trial division from 431 to 2003 */ |
|
94
|
1568 |
0 |
while (sp < NPRIMES_SMALL) { |
|
95
|
14 |
1568 |
while ( (un%f) == 0 ) { |
|
100
|
22 |
1546 |
if (f*f > un) break; |
|
105
|
33462 |
164 |
if (f*f > n) { |
|
106
|
29602 |
3860 |
if (n != 1) factors[nfactors++] = n; |
|
111
|
61 |
103 |
if (n < 200000000 && n < f*f*f) { |
|
|
46 |
15 |
if (n < 200000000 && n < f*f*f) { |
|
112
|
23 |
23 |
if (is_prob_prime(n)) factors[nfactors++] = n; |
|
123
|
4 |
114 |
if (k > 1) { |
|
126
|
10 |
4 |
for (i = nfactors; i >= 0; i--) |
|
127
|
20 |
10 |
for (j = 0; j < k; j++) |
|
140
|
180 |
76 |
while ( (n >= f*f) && (!is_prob_prime(n)) ) { |
|
|
71 |
109 |
while ( (n >= f*f) && (!is_prob_prime(n)) ) { |
|
143
|
71 |
0 |
UV const nbits = BITS_PER_WORD - clz(n); |
|
145
|
20 |
51 |
UV const br_rounds = 8000 + (9000 * ((nbits <= 45) ? 0 : (nbits-45))); |
|
156
|
71 |
0 |
if (!split_success && nbits <= 28) { /* This should always succeed */ |
|
|
16 |
55 |
if (!split_success && nbits <= 28) { /* This should always succeed */ |
|
158
|
0 |
16 |
if (verbose) printf("holf %d\n", split_success); |
|
161
|
55 |
16 |
if (!split_success && br_rounds > 0) { |
|
|
55 |
0 |
if (!split_success && br_rounds > 0) { |
|
163
|
0 |
55 |
if (verbose) printf("pbrent %d\n", split_success); |
|
166
|
0 |
71 |
if (!split_success) { |
|
168
|
0 |
0 |
if (verbose) printf("second pbrent %d\n", split_success); |
|
172
|
0 |
71 |
if (!split_success && nbits <= 62) { |
|
|
0 |
0 |
if (!split_success && nbits <= 62) { |
|
174
|
0 |
0 |
if (verbose) printf("squfof %d\n", split_success); |
|
177
|
0 |
71 |
if (!split_success) { |
|
179
|
0 |
0 |
if (verbose) printf("pminus1 %d\n", split_success); |
|
181
|
0 |
0 |
if (!split_success) { |
|
183
|
0 |
0 |
if (verbose) printf("long prho %d\n", split_success); |
|
184
|
0 |
0 |
if (!split_success) { |
|
186
|
0 |
0 |
if (verbose) printf("long pbrent %d\n", split_success); |
|
191
|
71 |
0 |
if (split_success) { |
|
192
|
0 |
71 |
MPUassert( split_success == 1, "split factor returned more than 2 factors"); |
|
194
|
71 |
0 |
if ((tofac_stack[ntofac] == n) || (tofac_stack[ntofac] == 1)) |
|
|
0 |
71 |
if ((tofac_stack[ntofac] == n) || (tofac_stack[ntofac] == 1)) |
|
201
|
0 |
0 |
if (verbose) printf("doing trial on %"UVuf"\n", n); |
|
202
|
0 |
0 |
while (f <= limit) { |
|
203
|
0 |
0 |
if ( (n%f) == 0 ) { |
|
207
|
0 |
0 |
} while ( (n%f) == 0 ); |
|
217
|
185 |
0 |
if (n != 1) factors[nfactors++] = n; |
|
219
|
71 |
114 |
if (ntofac > 0) n = tofac_stack[ntofac-1]; |
|
220
|
71 |
114 |
} while (ntofac-- > 0); |
|
223
|
71 |
114 |
for (i = nsmallfactors+1; i < nfactors; i++) { |
|
225
|
119 |
23 |
for (j = i; j > 0 && factors[j-1] > fi; j--) |
|
|
71 |
48 |
for (j = i; j > 0 && factors[j-1] > fi; j--) |
|
238
|
4 |
12211 |
if (n == 1) return 0; |
|
241
|
39 |
12172 |
if (exponents == 0) { |
|
242
|
92 |
39 |
for (; i < nfactors; i++) |
|
243
|
62 |
30 |
if (factors[i] != factors[i-1]) |
|
247
|
15656 |
12172 |
for (; i < nfactors; i++) { |
|
248
|
12314 |
3342 |
if (factors[i] != factors[i-1]) { |
|
264
|
3 |
1616 |
if (maxtrial == 0) maxtrial = UV_MAX; |
|
267
|
1611 |
8 |
if (n < 4 || maxtrial < 2) { |
|
|
0 |
1611 |
if (n < 4 || maxtrial < 2) { |
|
272
|
1621 |
1611 |
while ( (n & 1) == 0 ) { factors[nfactors++] = 2; n /= 2; } |
|
273
|
1608 |
3 |
if (3<=maxtrial) while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
|
804 |
1608 |
if (3<=maxtrial) while ( (n % 3) == 0 ) { factors[nfactors++] = 3; n /= 3; } |
|
274
|
1505 |
106 |
if (5<=maxtrial) while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
|
371 |
1505 |
if (5<=maxtrial) while ( (n % 5) == 0 ) { factors[nfactors++] = 5; n /= 5; } |
|
276
|
1255 |
356 |
if (7*7 <= n) { |
|
278
|
5242 |
3 |
while (++sp < NPRIMES_SMALL) { |
|
280
|
4560 |
682 |
if (f*f > n || f > maxtrial) break; |
|
|
3990 |
570 |
if (f*f > n || f > maxtrial) break; |
|
281
|
384 |
3990 |
while ( (n%f) == 0 ) { |
|
287
|
573 |
682 |
if (f*f <= n && f <= maxtrial) { |
|
|
3 |
570 |
if (f*f <= n && f <= maxtrial) { |
|
289
|
2 |
1 |
if (limit > maxtrial) limit = maxtrial; |
|
291
|
7903 |
3 |
while (f <= limit) { |
|
292
|
2 |
7901 |
if ( (n%f) == 0 ) { |
|
296
|
0 |
2 |
} while ( (n%f) == 0 ); |
|
298
|
2 |
0 |
if (newlimit < limit) limit = newlimit; |
|
306
|
1486 |
125 |
if (n != 1) |
|
316
|
7957 |
3468 |
for (s = 0; s < nfactors; s++) { |
|
318
|
10930 |
7957 |
for (j = 0; j < e; j++) { |
|
320
|
24475 |
10930 |
for (i = 0; i < scount; i++) |
|
327
|
43817 |
4354 |
{ const UV *x = a, *y = b; return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; } |
|
|
43817 |
0 |
{ const UV *x = a, *y = b; return (*x > *y) ? 1 : (*x < *y) ? -1 : 0; } |
|
336
|
4 |
3468 |
if (n <= 1) { |
|
338
|
1 |
3 |
if (n == 0) { divs[0] = 0; divs[1] = 1; *num_divisors = 2; } |
|
339
|
3 |
1 |
if (n == 1) { divs[0] = 1; *num_divisors = 1; } |
|
346
|
4489 |
3468 |
for (i = 1; i < nfactors; i++) |
|
348
|
0 |
3468 |
New(0, divs, ndivisors, UV); |
|
377
|
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; |
|
378
|
287 |
1218 |
if (n <= 1) /* n=0 divisors are [0,1] */ |
|
379
|
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] */ |
|
381
|
974 |
244 |
if (k == 0) { |
|
382
|
1365 |
974 |
for (i = 0; i < nfac; i++) { |
|
384
|
832 |
974 |
while (i+1 < nfac && f == factors[i+1]) { e++; i++; } |
|
|
441 |
391 |
while (i+1 < nfac && f == factors[i+1]) { e++; i++; } |
|
387
|
157 |
87 |
} else if (k == 1) { |
|
388
|
270 |
157 |
for (i = 0; i < nfac; i++) { |
|
391
|
215 |
157 |
while (i+1 < nfac && f == factors[i+1]) { |
|
|
102 |
113 |
while (i+1 < nfac && f == factors[i+1]) { |
|
399
|
135 |
87 |
for (i = 0; i < nfac; i++) { |
|
402
|
193 |
135 |
for (j = 1; j < (int)k; j++) pk *= f; |
|
405
|
101 |
87 |
while (i+1 < nfac && f == factors[i+1]) { |
|
|
53 |
48 |
while (i+1 < nfac && f == factors[i+1]) { |
|
423
|
110 |
0 |
if (f == 1 || f2 == 1) { |
|
|
0 |
110 |
if (f == 1 || f2 == 1) { |
|
429
|
0 |
110 |
MPUassert( factors[0] * factors[1] == n , "incorrect factoring"); |
|
440
|
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"); |
|
446
|
8 |
2 |
while (r != 0) { |
|
447
|
0 |
8 |
if (rounds-- == 0) { factors[0] = n; return 1; } |
|
453
|
18 |
8 |
} while (r > 0); |
|
464
|
41 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in holf_factor"); |
|
|
0 |
41 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in holf_factor"); |
|
468
|
1 |
40 |
if (is_perfect_square(n)) |
|
471
|
40 |
0 |
if (n <= (UV_MAX >> 6)) { /* Try with premultiplier first */ |
|
472
|
0 |
40 |
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 : |
|
490
|
2111 |
0 |
while (rounds--) { |
|
494
|
1577 |
534 |
if (!((f*0x8bc40d7d) & (f*0xa1e2f5d1) & 0x14020a)) { |
|
496
|
40 |
1537 |
if (m == f*f) { |
|
498
|
40 |
0 |
if (f > 1 && f < n) |
|
|
40 |
0 |
if (f > 1 && f < n) |
|
502
|
0 |
2071 |
if (ni >= (ni+npre)) break; |
|
508
|
0 |
0 |
for (i = 1; i <= rounds; i++) { |
|
514
|
0 |
0 |
if (is_perfect_square(m)) { |
|
516
|
0 |
0 |
f = gcd_ui( (s>f) ? s-f : f-s, n); |
|
531
|
59 |
0 |
UV const nbits = BITS_PER_WORD - clz(n); |
|
532
|
47 |
12 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
45 |
2 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
26 |
19 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
|
10 |
16 |
const UV inner = (nbits <= 31) ? 32 : (nbits <= 35) ? 64 : (nbits <= 40) ? 160 : (nbits <= 52) ? 256 : 320; |
|
537
|
59 |
0 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pbrent_factor"); |
|
|
0 |
59 |
MPUassert( (n >= 3) && ((n%2) != 0) , "bad n in pbrent_factor"); |
|
542
|
522 |
0 |
while (rounds > 0) { |
|
546
|
1315 |
463 |
while (rleft > 0) { |
|
551
|
961 |
354 |
if (n < (1ULL << 63)) { |
|
553
|
439 |
522 |
m = ABSDIFF(Xi,Xm); |
|
554
|
165599 |
961 |
while (--irounds > 0) { |
|
556
|
67447 |
98152 |
f = ABSDIFF(Xi,Xm); |
|
559
|
354 |
0 |
} else if (a == mont1) { |
|
561
|
201 |
153 |
m = ABSDIFF(Xi,Xm); |
|
562
|
103835 |
354 |
while (--irounds > 0) { |
|
564
|
59454 |
44381 |
f = ABSDIFF(Xi,Xm); |
|
569
|
0 |
0 |
m = ABSDIFF(Xi,Xm); |
|
570
|
0 |
0 |
while (--irounds > 0) { |
|
572
|
0 |
0 |
f = ABSDIFF(Xi,Xm); |
|
577
|
59 |
1256 |
if (f != 1) |
|
581
|
463 |
59 |
if (f == 1) { |
|
585
|
0 |
59 |
if (f == n) { /* back up, with safety */ |
|
588
|
0 |
0 |
if (n < (1ULL << 63) || a == mont1) |
|
|
0 |
0 |
if (n < (1ULL << 63) || a == mont1) |
|
589
|
0 |
0 |
Xi = mont_mulmod(Xi,Xi+a,n); |
|
591
|
0 |
0 |
Xi = addmod(mont_mulmod(Xi,Xi,n),a,n); |
|
592
|
0 |
0 |
m = ABSDIFF(Xi,Xm); |
|
594
|
0 |
0 |
} while (f == 1 && r-- != 0); |
|
|
0 |
0 |
} while (f == 1 && r-- != 0); |
|
596
|
59 |
0 |
if (f == 0 || f == n) { |
|
|
0 |
59 |
if (f == 0 || f == n) { |
|
597
|
0 |
0 |
if (fails-- <= 0) break; |
|
677
|
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"); |
|
690
|
2 |
0 |
while (rounds-- > 0) { |
|
692
|
128 |
2 |
for (i = 0; i < inner; i++) { |
|
696
|
59 |
69 |
f = (U > V) ? U-V : V-U; |
|
700
|
0 |
2 |
if (f == 1) |
|
702
|
2 |
0 |
if (f == n) { /* back up to find a factor*/ |
|
709
|
3 |
3 |
f = gcd_ui( (U > V) ? U-V : V-U, n); |
|
710
|
4 |
2 |
} while (f == 1 && i-- != 0); |
|
|
4 |
0 |
} while (f == 1 && i-- != 0); |
|
712
|
2 |
0 |
if (f == 0 || f == n) { |
|
|
0 |
2 |
if (f == 0 || f == n) { |
|
713
|
0 |
0 |
if (fails-- <= 0) break; |
|
742
|
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"); |
|
744
|
0 |
2 |
if (B1 <= primes_small[NPRIMES_SMALL-2]) { |
|
746
|
0 |
0 |
for (i = 1; primes_small[i] <= B1; i++) { |
|
748
|
0 |
0 |
if (q <= sqrtB1) { |
|
750
|
0 |
0 |
while (k <= kmin) k *= q; |
|
753
|
0 |
0 |
if ( (j++ % 32) == 0) { |
|
754
|
0 |
0 |
PMINUS1_RECOVER_A; |
|
755
|
0 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
|
0 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
760
|
0 |
0 |
PMINUS1_RECOVER_A; |
|
762
|
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) { |
|
764
|
64 |
0 |
if (q <= sqrtB1) { |
|
766
|
136 |
64 |
while (k <= kmin) k *= q; |
|
769
|
2 |
62 |
if ( (j++ % 32) == 0) { |
|
770
|
0 |
2 |
PMINUS1_RECOVER_A; |
|
771
|
2 |
0 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
|
0 |
2 |
if (a == 0 || gcd_ui(a-1, n) != 1) |
|
776
|
0 |
2 |
PMINUS1_RECOVER_A; |
|
778
|
0 |
2 |
if (a == 0) { factors[0] = n; return 1; } |
|
782
|
2 |
0 |
if (f == n) { |
|
784
|
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) { |
|
786
|
58 |
4 |
while (k <= kmin) k *= p; |
|
790
|
2 |
2 |
if (f != 1) |
|
805
|
0 |
2 |
if (f == 1 && B2 > B1) { |
|
|
0 |
0 |
if (f == 1 && B2 > B1) { |
|
814
|
0 |
0 |
for (j = 1; j < 20; j++) { |
|
822
|
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 ) { |
|
828
|
0 |
0 |
if (qdiff >= 111) { |
|
832
|
0 |
0 |
if (bmdiff == 0) { |
|
833
|
0 |
0 |
if (precomp_bm[qdiff-1] != 0) |
|
841
|
0 |
0 |
if (a == 0) break; |
|
843
|
0 |
0 |
if ( (j++ % 64) == 0 ) { |
|
845
|
0 |
0 |
if (f != 1) |
|
860
|
6 |
0 |
UV bit = UVCONST(1) << (clz(exp)-1); |
|
861
|
339 |
6 |
while (bit) { |
|
863
|
15 |
324 |
if ( exp & bit ) { |
|
878
|
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"); |
|
883
|
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) { |
|
885
|
4 |
0 |
if (p < sqrtB1) { |
|
887
|
17 |
4 |
while (k <= kmin) |
|
891
|
4 |
0 |
if (X1 != 2) { |
|
893
|
2 |
2 |
if (f != 1 && f != n) break; |
|
|
2 |
0 |
if (f != 1 && f != n) break; |
|
896
|
0 |
2 |
if (X2 != 2) { |
|
898
|
0 |
0 |
if (f != 1 && f != n) break; |
|
|
0 |
0 |
if (f != 1 && f != n) break; |
|
953
|
0 |
3 |
if (i & 0x1) { |
|
959
|
0 |
4 |
if (i >= imax) { |
|
973
|
3 |
1 |
if (!((t2*0x8bc40d7d) & (t2*0xa1e2f5d1) & 0x14020a)) { |
|
975
|
3 |
0 |
if (Qn == t1*t1) |
|
1002
|
2 |
1 |
SYMMETRY_POINT_ITERATION; |
|
1003
|
1 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1004
|
0 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1005
|
0 |
0 |
SYMMETRY_POINT_ITERATION; |
|
1006
|
0 |
0 |
if (j++ > 2000000) { |
|
1013
|
3 |
0 |
if (t1 > 1) |
|
1041
|
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"); |
|
1044
|
0 |
2 |
if (n > SQUFOF_MAX) { |
|
1048
|
76 |
2 |
for (i = 0; i < NSQUFOF_MULT; i++) { |
|
1056
|
3 |
0 |
for (i = 0; i < NSQUFOF_MULT; i++) { |
|
1057
|
0 |
3 |
if (mult_save[i].valid == 0) continue; |
|
1060
|
3 |
0 |
if (mult_save[i].valid == -1) { |
|
1061
|
0 |
3 |
if ((SQUFOF_MAX / mult) < n) { |
|
1068
|
3 |
0 |
if (mult_save[i].imax < 20) mult_save[i].imax = 20; |
|
1069
|
0 |
3 |
if (mult_save[i].imax > rounds) mult_save[i].imax = rounds; |
|
1073
|
0 |
3 |
if (mult_save[i].Qn == 0) |
|
1080
|
3 |
0 |
if (f64 > 1) { |
|
1081
|
3 |
0 |
if (f64 != mult) { |
|
1083
|
2 |
1 |
if (f64 != 1) { |
|
1095
|
0 |
1 |
if (mult_save[i].valid == 1) |
|
1098
|
0 |
1 |
if (rounds_done >= rounds) |
|
1101
|
0 |
0 |
} while (still_racing && rounds_done < rounds); |
|
|
0 |
0 |
} while (still_racing && rounds_done < rounds); |
|
1113
|
0 |
0 |
for (i = 0; i < SQR_TAB_SIZE; i++) |
|
1121
|
0 |
0 |
const double Tune = ((n >> 31) >> 5) ? 3.5 : 5.0; |
|
1126
|
0 |
0 |
if (!(n&1)) return found_factor(n, 2, factors); |
|
1130
|
0 |
0 |
if (do_trial) { |
|
1132
|
0 |
0 |
if (FirstCut < 84) FirstCut = 84; |
|
1133
|
0 |
0 |
if (FirstCut > 65535) FirstCut = 65535; |
|
1134
|
0 |
0 |
for (ip = 2; ip < NPRIMES_SMALL; ip++) { |
|
1136
|
0 |
0 |
if (p >= FirstCut) |
|
1138
|
0 |
0 |
if (n % p == 0) |
|
1143
|
0 |
0 |
if (n >= UVCONST(8796393022207)) { factors[0] = n; return 1; } |
|
1148
|
0 |
0 |
if (!sqr_tab_init) make_sqr_tab(); |
|
1151
|
0 |
0 |
for (k = 1; k <= Bred; k++) { |
|
1152
|
0 |
0 |
if (k&1) { inc = 4; r = (k+n) % 4; } |
|
1155
|
0 |
0 |
if (kN >= UVCONST(1152921504606846976)) { factors[0] = n; return 1; } |
|
1158
|
0 |
0 |
x = (k < SQR_TAB_SIZE) ? sqrtn * sqr_tab[k] : sqrt((double)kN); |
|
1160
|
0 |
0 |
if ((UV)a * (UV)a == kN) |
|
1168
|
0 |
0 |
for (a = b; a <= U; c += inc*(a+a+inc), a += inc) { |
|
1171
|
0 |
0 |
if (!((b*0x8bc40d7d) & (b*0xa1e2f5d1) & 0x14020a)) { |
|
1173
|
0 |
0 |
if (c == b*b) { |
|
1180
|
0 |
0 |
if (do_trial) { |
|
1181
|
0 |
0 |
if (B > 65535) B = 65535; |
|
1195
|
0 |
23 |
if (maxrounds > p) maxrounds = p; |
|
1198
|
18 |
5 |
if (p&1) { |
|
1202
|
13930 |
0 |
for (t = g, k = 1; k < maxrounds; k++) { |
|
1203
|
18 |
13912 |
if (t == a) |
|
1205
|
0 |
13912 |
t = mont_mulmod(t, g, p); |
|
1206
|
0 |
13912 |
if (t == g) break; /* Stop at cycle */ |
|
1211
|
9 |
0 |
for (t = g, k = 1; k < maxrounds; k++) { |
|
1212
|
4 |
5 |
if (t == a) |
|
1215
|
1 |
4 |
if (t == g) break; /* Stop at cycle */ |
|
1258
|
0 |
4 |
if (s->failed) return 0; |
|
1259
|
0 |
4 |
if (s->round + rounds > n) rounds = n - s->round; |
|
1261
|
26785 |
2 |
for (i = 1; i <= rounds; i++) { |
|
1265
|
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 ); |
|
1266
|
2 |
26783 |
if (u == U) { |
|
1269
|
0 |
2 |
if (r1 == 0) { |
|
1270
|
0 |
0 |
if (verbose) printf("DLP Rho failure, r=0\n"); |
|
1280
|
0 |
2 |
if (G > 1) { |
|
1281
|
0 |
0 |
if (powmod(g,k,p) == a) { |
|
1282
|
0 |
0 |
if (verbose > 2) printf(" common GCD %"UVuf"\n", G2); |
|
1285
|
0 |
0 |
for (m = 0; m < G; m++) { |
|
1287
|
0 |
0 |
if (powmod(g,k,p) == a) break; |
|
1289
|
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); |
|
1293
|
0 |
2 |
if (powmod(g,k,p) != a) { |
|
1294
|
0 |
0 |
if (verbose > 2) printf("r1 = %"UVuf" r2 = %"UVuf" k = %"UVuf"\n", r1, r2, k); |
|
1295
|
0 |
0 |
if (verbose) printf("Incorrect DLP Rho solution: %"UVuf"\n", k); |
|
1303
|
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); |
|
1348
|
4137 |
2 |
if (top->nused == 0 || top->nused >= BSGS_ENTRIES_PER_PAGE) { |
|
|
0 |
4137 |
if (top->nused == 0 || top->nused >= BSGS_ENTRIES_PER_PAGE) { |
|
1360
|
2 |
2 |
while (head != 0) { |
|
1374
|
0 |
2 |
while (entry && entry->V != v) |
|
|
0 |
0 |
while (entry && entry->V != v) |
|
1377
|
2 |
0 |
if (!entry) { |
|
1388
|
0 |
0 |
while (entry && entry->V != v) |
|
|
0 |
0 |
while (entry && entry->V != v) |
|
1390
|
0 |
0 |
return (entry) ? entry->M : 0; |
|
1398
|
123 |
4137 |
while (entry && entry->V != v) |
|
|
123 |
0 |
while (entry && entry->V != v) |
|
1401
|
0 |
4137 |
if (entry) |
|
1424
|
0 |
3 |
if (n <= 2) return 0; /* Shouldn't be here with gorder this low */ |
|
1426
|
3 |
0 |
if (race_rho) { |
|
1428
|
1 |
2 |
if (result) { |
|
1429
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step 0\n"); |
|
1434
|
0 |
2 |
if (a == 0) return 0; /* We don't handle this case */ |
|
1439
|
0 |
2 |
hashmap_count = (m < 65537) ? 65537 : |
|
1440
|
0 |
0 |
(m > 40000000) ? 40000003 : |
|
1448
|
0 |
2 |
Newz(0, PAGES.table, hashmap_count, bsgs_hash_t*); |
|
1460
|
2069 |
0 |
for (i = 1; i <= m; i++) { |
|
1462
|
0 |
2069 |
if (gs_i) { bs_i = i; break; } |
|
1464
|
1 |
2068 |
if (S == aa) { /* We discovered the solution! */ |
|
1465
|
0 |
1 |
if (verbose) printf(" dlp bsgs: solution at BS step %"UVuf"\n", i+1); |
|
1470
|
0 |
2068 |
if (bs_i) { gs_i = i; break; } |
|
1472
|
2068 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
|
1 |
2067 |
if (race_rho && (i % 2048) == 0) { |
|
1474
|
1 |
0 |
if (result) { |
|
1475
|
0 |
1 |
if (verbose) printf("rho found solution in BSGS step %"UVuf"\n", i); |
|
1481
|
0 |
2 |
if (!result) { |
|
1483
|
0 |
0 |
if (!(gs_i || bs_i)) { |
|
|
0 |
0 |
if (!(gs_i || bs_i)) { |
|
1485
|
0 |
0 |
if (m < maxm && b > 8*m) b = 8*m; |
|
|
0 |
0 |
if (m < maxm && b > 8*m) b = 8*m; |
|
1486
|
0 |
0 |
for (i = m+1; i < b; i++) { |
|
1488
|
0 |
0 |
if (bs_i) { gs_i = i; break; } |
|
1490
|
0 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
|
0 |
0 |
if (race_rho && (i % 2048) == 0) { |
|
1492
|
0 |
0 |
if (result) { |
|
1493
|
0 |
0 |
if (verbose) printf("rho found solution in BSGS step %"UVuf"\n", i); |
|
1500
|
0 |
0 |
if (gs_i || bs_i) { |
|
|
0 |
0 |
if (gs_i || bs_i) { |
|
1504
|
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)); |
|
1508
|
2 |
0 |
if (result != 0 && powmod(g,result,p) != a) { |
|
|
0 |
2 |
if (result != 0 && powmod(g,result,p) != a) { |
|
1509
|
0 |
0 |
if (verbose) printf("Incorrect DLP BSGS solution: %"UVuf"\n", result); |
|
1512
|
2 |
0 |
if (race_rho && result == 0) { |
|
|
0 |
2 |
if (race_rho && result == 0) { |
|
1524
|
0 |
16 |
if (a >= p) a %= p; |
|
1525
|
0 |
16 |
if (g >= p) g %= p; |
|
1527
|
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) |
|
1530
|
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); |
|
1534
|
15 |
0 |
if (n == 0 || n <= DLP_TRIAL_NUM) { |
|
|
12 |
3 |
if (n == 0 || n <= DLP_TRIAL_NUM) { |
|
1536
|
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"); |
|
1537
|
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; |
|
1542
|
3 |
0 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
|
0 |
3 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
1544
|
0 |
3 |
if (aorder == 0 && gorder != 0) return 0; |
|
|
0 |
0 |
if (aorder == 0 && gorder != 0) return 0; |
|
1545
|
3 |
0 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
|
0 |
3 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
1548
|
3 |
0 |
sqrtn = (n == 0) ? 0 : isqrt(n); |
|
1549
|
0 |
3 |
if (n == 0) n = p-1; |
|
1552
|
3 |
0 |
UV maxent = (sqrtn > 0) ? sqrtn+1 : 100000; |
|
1554
|
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"); |
|
1555
|
3 |
0 |
if (k != 0) return k; |
|
1556
|
0 |
0 |
if (sqrtn > 0 && sqrtn < maxent) return 0; |
|
|
0 |
0 |
if (sqrtn > 0 && sqrtn < maxent) return 0; |
|
1559
|
0 |
0 |
if (verbose) printf(" dlp doing exhaustive trial\n"); |
|
1571
|
0 |
5 |
if (p1 == 0) return 0; /* TODO: Should we plow on with p1=p-1? */ |
|
1573
|
0 |
5 |
if (nfactors == 1) |
|
1575
|
16 |
5 |
for (i = 0; i < nfactors; i++) { |
|
1577
|
1 |
16 |
pi = fac[i]; for (j = 1; j < exp[i]; j++) pi *= fac[i]; |
|
1585
|
5 |
0 |
if (i == 1 && powmod(g, x, p) == a) |
|
|
5 |
0 |
if (i == 1 && powmod(g, x, p) == a) |
|
1595
|
0 |
20 |
if (a >= p) a %= p; |
|
1596
|
0 |
20 |
if (g >= p) g %= p; |
|
1598
|
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) |
|
1605
|
15 |
3 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
|
2 |
13 |
if (gorder != 0 && powmod(a, gorder, p) != 1) return 0; |
|
1607
|
3 |
13 |
if (aorder == 0 && gorder != 0) return 0; |
|
|
0 |
3 |
if (aorder == 0 && gorder != 0) return 0; |
|
1608
|
13 |
3 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
|
0 |
13 |
if (aorder != 0 && gorder % aorder != 0) return 0; |
|
1611
|
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)) { |
|
1612
|
0 |
11 |
if (verbose > 1) printf(" dlp trial znlog(%"UVuf",%"UVuf",%"UVuf")\n",a,g,p); |
|
1617
|
5 |
0 |
if (!is_prob_prime(gorder)) { |
|
1619
|
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"); |
|
1620
|
5 |
0 |
if (k != 0) return k; |