2009-03-29, 16:32 | #1 |
Jun 2003
7·167 Posts |
Why do these P+1 factorizations work?
Code:
$ echo 264230314763760208834215981504580626343342447 | ecm -x0 407367722 -pp1 1312500 0 GMP-ECM 6.2 [powered by GMP 4.2.2] [P+1] Input number is 264230314763760208834215981504580626343342447 (45 digits) Using B1=1312500, B2=0, polynomial x^1, x0=407367722 Step 1 took 1776ms ********** Factor found in step 1: 5661205017073505552389801 Found probable prime factor of 25 digits: 5661205017073505552389801 Probable prime cofactor 46673864303955381847 has 20 digits p-1 = 5661205017073505552389800 = 2^3 * 3 * 5^2 * 7 * 19 * 137 * 619 * 215899 * 12223199 Neither p+1 nor p-1 is smooth to the given bound. Here's another: Code:
$ echo 2855451057157704997579326497626590663028969 | ecm -pp1 -x0 3338685868 1277500 0 GMP-ECM 6.2 [powered by GMP 4.2.2] [P+1] Input number is 2855451057157704997579326497626590663028969 (43 digits) Using B1=1277500, B2=0, polynomial x^1, x0=3338685868 Step 1 took 1720ms ********** Factor found in step 1: 896774094182730749591 Found probable prime factor of 21 digits: 896774094182730749591 Probable prime cofactor 3184136423744490284159 has 22 digits p-1 = 896774094182730749590 = 2 * 5 * 11 * 257 * 25307 * 102611 * 12215821 |
2009-03-29, 17:17 | #2 |
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts |
In P-1, if all factors p of N are p≡1 (mod m) for some m, then N≡1 (mod m), and we can include m in the stage 1 exponent by exponentiating by N-1, without actually knowing what m is. GMP-ECM does that, so that for example for cyclotomic numbers Φ_{m}(x), the known factor m in p-1 is always included, without the user having to specify m via the -go parameter.
For P+1, we adapt this to exponentiating by N^{2}-1 in stage 1. This way, if all factors are p≡±1 (mod m) for some m, we are certain to include m in the exponent. In your two cases, N^{2}-1 happens to be divisible by 12223199 and 12215821, respectively, so these to primes got included in stage 1 even though they are greater than B1. Alex Last fiddled with by akruppa on 2009-03-30 at 22:49 Reason: typos |
2009-03-30, 07:54 | #3 |
Jun 2003
7·167 Posts |
That's great! In fact, I already knew about the 12223199 and 12215821 factors of p-1. Both Ns are composite factors of Mersennes found by P-1, and I was looking for the best way to resolve them. Of course I can break them in seconds by throwing a few curves at them, but using P+1 to the original P-1 bounds breaks them in a fraction of a second.
The downside is that sometimes you get a "found input number N" and the program halts even if there are more runs to do. Is there a way to make in continue when that happens? Last fiddled with by Mr. P-1 on 2009-03-30 at 07:57 |
2009-03-30, 14:05 | #4 |
"Nancy"
Aug 2002
Alexandria
2,467 Posts |
Hmm... a "Don't take N for an answer" option should not be too hard, once I figure out how the loop in main.c works again. In the meantime, if you find N frequently, it's a strong hint that the B1,B2 values are too high.
If you give "-v -v" verboseness and a composite factor is found in stage 2, it'll test each point of evaluation for a factor (instead of just their product) and try to determine the largest prime factor in the group order associated with each prime factor of N. A side effect is that usually the prime factors of the composite factor of N are printed. (And when I tested whether that code actually still works, I found that the code could segfault sometimes... fixed in SVN, but beware if you use 6.2.2. There are enough bugs piling up that we may need a 6.2.3 soon. ) Alex |
2009-10-11, 10:49 | #5 |
Einyen
Dec 2003
Denmark
3,347 Posts |
Is this also why this factor was found by P-1 during P+1?
GMP-ECM 6.2.3 [powered by GMP 4.2.1_MPIR_1.1.1] [P+1] Input number is (2^2917+1)/3 (878 digits) Using B1=10000000, B2=93541776130, polynomial x^1, x0=3358300603 Step 1 took 75640ms Step 2 took 100922ms [factor found by P-1] ********** Factor found in step 2: 19038883797876537274366477800610849 Found probable prime factor of 35 digits: 19038883797876537274366477800610849 Composite cofactor ((2^2917+1)/3)/19038883797876537274366477800610849 has 844 digits |
2009-10-11, 12:44 | #6 |
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts |
P+1 can either end up working in a group of order p-1 or p+1, depending on whether x_{0}^{2} - 4 is a quadratic residue modulo p or not. Since we don't know p in advance, we can't tell which one it was until after p was found. If it was actually p-1, the GMP-ECM prints the message you quoted. The effect of getting either p-1 or p+1 is pretty fundamental to how P+1 works, we don't know how to construct a quadratic extension of GF(p) reliably without knowing p. The extra exponentiation etc. we do in GMP-ECM is not related to this.
Alex |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Aurifeuillian Factorizations | Raman | Cunningham Tables | 39 | 2020-08-28 14:34 |
The worth or futility of gratituous factorizations | R.D. Silverman | Factoring | 79 | 2012-01-12 10:58 |
algorithms for special factorizations | jjcale | Factoring | 6 | 2011-07-28 02:06 |
Schinzel's Aurifeuillian style factorizations? | wblipp | Math | 2 | 2010-08-15 20:33 |
Prime k-value density rating and factorizations | gd_barnes | No Prime Left Behind | 25 | 2009-07-30 12:06 |