## P+1 curios

Expand Messages
• Trying to factor 134^131+131^134, I obtained: GMP-ECM 5.1-beta [powered by GMP 4.1] [P-1] Input number is
Message 1 of 4 , May 6, 2003
• 0 Attachment
Trying to factor 134^131+131^134, I obtained:

Input number is 25865447487363725783122634349075395812340400623026024679130966646043807574550805573958725860457194408072135499668441003308474484944428943584532115942895847887759143649437935379122607964373488754857613201155063924520774277362143078736973209926360612163137002918023001 (266 digits)
Using B1=10000000, B2=732940912, polynomial x^24, x0=2101091962
Step 1 took 102255ms
Step 2 took 29094ms
********** Factor found in step 2: 1713776305533792578182169122961
Found probable prime factor of 31 digits: 1713776305533792578182169122961
Composite cofactor 15092662562695062190247830140515451896766513154868853489965873041122539539760189456815505401475408896982253689154264478030985178890080361607674298468006609898425851973638515015599202280707306886386928007775058770877765909292554751405641 has 236 digits

All is OK, because

P-1 = 1713776305533792578182169122960 = 2*2*2*2*5*7*17*17*89*401*290827*1497107*681469339

But then I found the same factorization among my P+1 results:

Input number is 25865447487363725783122634349075395812340400623026024679130966646043807574550805573958725860457194408072135499668441003308474484944428943584532115942895847887759143649437935379122607964373488754857613201155063924520774277362143078736973209926360612163137002918023001 (266 digits)
Using B1=10000000, B2=1967819029, polynomial x^1, x0=461132087
Step 1 took 132377ms
Step 2 took 62497ms
Line=1/1 Curves=2/3 B1=10000000 factors=0
C266 Using B1=10000000, B2=1967819029, polynomial x^1, x0=1494475138
Step 1 took 132816ms
Step 2 took 62399ms
[factor found by P-1]
********** Factor found in step 2: 1713776305533792578182169122961
Found probable prime factor of 31 digits: 1713776305533792578182169122961
Composite cofactor 15092662562695062190247830140515451896766513154868853489965873041122539539760189456815505401475408896982253689154264478030985178890080361607674298468006609898425851973638515015599202280707306886386928007775058770877765909292554751405641 has 236 digits
Line=1/1 Curves=3/3 B1=10000000 factors=1
C236 Using B1=10000000, B2=1967819029, polynomial x^1, x0=3018874033
Step 1 took 110956ms
Step 2 took 54854ms

Is it normal? Using B1 = 10^7, we find the factor P with

P+1 = 1713776305533792578182169122962 = 2*3*285629384255632096363694853827

Andrey

[Non-text portions of this message have been removed]
• ... Understand. I should be more attentive before asking a question, as usual... ... Thanks, Andrey
Message 2 of 4 , May 6, 2003
• 0 Attachment
> The first item is in the ECM-GMP documentation. It states that you
> need to run P+1 a total of 3 times since it has roughly a 50/50
> chance of actually executing a P-1 instead of a P+1. I don't know the
> math behind it, I just know what the document states.
>
> The second item is that if you look carefully in the ECM-GMP output,
> you'll see a line within brackets saying that this factor was found
> via P-1.

Understand. I should be more attentive before asking a question, as usual...
:-)

Thanks,

Andrey
• ... Yes, it is normal. If you don t happen upon a lucky starting number for P+1, you end up doing a (very slow) P-1. Paul
Message 3 of 4 , May 6, 2003
• 0 Attachment
> Trying to factor 134^131+131^134, I obtained:
...
> ********** Factor found in step 2: 1713776305533792578182169122961
> Found probable prime factor of 31 digits:
> 1713776305533792578182169122961

> All is OK, because
>
> P-1 = 1713776305533792578182169122960 =
> 2*2*2*2*5*7*17*17*89*401*290827*1497107*681469339
>
> But then I found the same factorization among my P+1 results:
...
> Is it normal? Using B1 = 10^7, we find the factor P with
>
> P+1 = 1713776305533792578182169122962 =
> 2*3*285629384255632096363694853827

Yes, it is normal. If you don't happen upon a lucky starting number for P+1, you end up doing a (very slow) P-1.

Paul
• I made the same identical mistake myself. You have to take into account two items of information. The first item is in the ECM-GMP documentation. It states
Message 4 of 4 , May 6, 2003
• 0 Attachment
I made the same identical mistake myself. You have to take into
account two items of information.

The first item is in the ECM-GMP documentation. It states that you
need to run P+1 a total of 3 times since it has roughly a 50/50
chance of actually executing a P-1 instead of a P+1. I don't know the
math behind it, I just know what the document states.

The second item is that if you look carefully in the ECM-GMP output,
you'll see a line within brackets saying that this factor was found
via P-1. (Look 4 lines into the clip below). This signifies that
while you executed a P+1 pass, the factor was found via P-1. To
determine if there exists a factor via P+1, you must run a total of 3
passes of P+1 and check for a factor to be found without the P-1
statement within the output.

> C266 Using B1=10000000, B2=1967819029, polynomial x^1, x0=1494475138
> Step 1 took 132816ms
> Step 2 took 62399ms
> [factor found by P-1]
> ********** Factor found in step 2: 1713776305533792578182169122961
> Found probable prime factor of 31 digits:
1713776305533792578182169122961
> Composite cofactor
1509266256269506219024783014051545189676651315486885348996587304112253
9539760189456815505401475408896982253689154264478030985178890080361607
6742984680066098984258519736385150155992022807073068863869280077750587
70877765909292554751405641 has 236 digits
Your message has been successfully submitted and would be delivered to recipients shortly.