-   GMP-ECM (
-   -   Why do these P+1 factorizations work? (

Mr. P-1 2009-03-29 16:32

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[/code]

p+1 = 5661205017073505552389802 = 2 * 13 * 1693921 * 128541209715699337
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[/code]

p+1 = 896774094182730749592 = 2^3 * 3 * 659 * 4093351 * 13851838237
p-1 = 896774094182730749590 = 2 * 5 * 11 * 257 * 25307 * 102611 * 12215821

akruppa 2009-03-29 17:17

In P-1, if all factors [I]p[/I] of [I]N[/I] are [I]p[/I]≡1 (mod [I]m[/I]) for some [I]m[/I], then N≡1 (mod [I]m[/I]), and we can include [I]m[/I] in the stage 1 exponent by exponentiating by [I]N[/I]-1, without actually knowing what [I]m[/I] is. GMP-ECM does that, so that for example for cyclotomic numbers Φ[sub]m[/sub](x), the known factor [I]m[/I] in [I]p[/I]-1 is always included, without the user having to specify [I]m[/I] via the -go parameter.

For P+1, we adapt this to exponentiating by [I]N[/I][sup]2[/sup]-1 in stage 1. This way, if all factors are [I]p[/I]≡±1 (mod [I]m[/I]) for some [I]m[/I], we are certain to include [I]m[/I] in the exponent.

In your two cases, [I]N[/I][sup]2[/sup]-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.


Mr. P-1 2009-03-30 07:54

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?

akruppa 2009-03-30 14:05

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. :sad:)


ATH 2009-10-11 10:49

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] [B][P+1][/B]
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 [B]P-1[/B]]
********** Factor found in step 2: 19038883797876537274366477800610849
Found probable prime factor of 35 digits: 19038883797876537274366477800610849
Composite cofactor ((2^2917+1)/3)/19038883797876537274366477800610849 has 844 digits

akruppa 2009-10-11 12:44

P+1 can either end up working in a group of order p-1 or p+1, depending on whether x[SUB]0[/SUB][SUP]2[/SUP] - 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.


All times are UTC. The time now is 07:13.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.