- **Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=8*)

- - **trial factoring and P-1**
(*https://www.mersenneforum.org/showthread.php?t=5295*)

trial factoring and P-1When doing P-1 factoring the b1 is actually b1*M
suppose we test M=67 to b1=1000 It actually look for factor of the form (2*....*M*b1*M+1) If it is (2*...*M+1) then the factor is found right away. Would it become faster to do P-1 testing rather than trial at higher mersenne numbers? ex. 79299959 has been P-1 tested to 8000000 so 2*...*79299959*8000000*79299959+1 76bits+ trial shows 79299959,72 or Have I got the whole thing wrong:redface: ps I never do stage 2 as it messes stage 1 save files. I keep my files as it continues to higher level from where it leftoff. |

[quote=jocelynl]When doing P-1 factoring the b1 is actually b1*M[/quote]What is your definition of M?
My understanding is that, in the Prime95 implementation of the P-1 algorithm, b1 is the upper limit on the prime factors of the "k" of potential factors 2kp+1 of 2[sup]p[/sup]-1 that are to be found by the P-1 method. That is, stage 1 P-1 with b1 = 10000 performed on 2[sup]p[/sup]-1 will find any factor 2kp+1 of 2[sup]p[/sup]-1 in which the largest prime factor of k is less than (or equal to, if b1 were prime itself) 10000. |

[quote=cheesehead]My understanding is that, in the Prime95 implementation of the P-1 algorithm, b1 is the upper limit on the prime factors of the "k" of potential factors 2kp+1 of 2[sup]p[/sup]-1 that are to be found by the P-1 method.
That is, stage 1 P-1 with b1 = 10000 performed on 2[sup]p[/sup]-1 will find any factor 2kp+1 of 2[sup]p[/sup]-1 in which the largest prime factor of k is less than (or equal to, if b1 were prime itself) 10000.[/quote]Correction: My understanding is that, in the Prime95 implementation of the P-1 algorithm, b1 is the upper limit on the [U]power-of-a-[/U]prime factors of the "k" of potential factors 2kp+1 of 2[sup]p[/sup]-1 that are to be found by the P-1 method. That is, stage 1 P-1 with b1 = 10000 performed on 2[sup]p[/sup]-1 will find any factor 2kp+1 of 2[sup]p[/sup]-1 in which the largest [U]power-of-a-[/U]prime factor of k is less than (or equal to, if b1 were prime itself) 10000. Example: 59704785388637019242567 is a factor of 2[sup]6049993[/sup] - 1. 59704785388637019242567 = 2 * 4934285493275531 * 6049993 + 1. Prime95's P-1 stage 1 with b1 = 4000 would find this factor because the largest prime-power factor of 4934285493275531 is less than 4000. 4934285493275531 = 61[sup]2[/sup] * 593 * 983 * 1153 [COLOR=green]×[/COLOR] 1973. 61[sup]2[/sup] = 3721. In this example the factor 59704785388637019242567 could have been found in stage 1 with b1 as low as 3721. Also, Prime95's P-1 stage 2 with b1 = 2000 and b2 = 4000 would find this factor because the largest prime-power factor of 4934285493275531 is less than 4000 and all other prime-power factors are less than 2000. (In fact, b1/b2 as low as b1 = 1973, b2 = 3721 would have worked.) |

[QUOTE=cheesehead]Also, Prime95's P-1 stage 2 with b1 = 2000 and b2 = 4000 would find this factor because the largest prime-power factor of 4934285493275531 is less than 4000 and all other prime-power factors are less than 2000. (In fact, b1/b2 as low as b1 = 1973, b2 = 3721 would have worked.)[/QUOTE]
AFAIK, stage 2 only considers primes and not prime powers. So this would not be found. |

[QUOTE=cheesehead]Correction:
My understanding is that, in the Prime95 implementation of the P-1 algorithm, b1 is the upper limit on the [U]power-of-a-[/U]prime factors of the "k" of potential factors 2kp+1 of 2[sup]p[/sup]-1 that are to be found by the P-1 method. That is, stage 1 P-1 with b1 = 10000 performed on 2[sup]p[/sup]-1 will find any factor 2kp+1 of 2[sup]p[/sup]-1 in which the largest [U]power-of-a-[/U]prime factor of k is less than (or equal to, if b1 were prime itself) 10000. Example: 59704785388637019242567 is a factor of 2[sup]6049993[/sup] - 1. 59704785388637019242567 = 2 * 4934285493275531 * 6049993 + 1. Prime95's P-1 stage 1 with b1 = 4000 would find this factor because the largest prime-power factor of 4934285493275531 is less than 4000. 4934285493275531 = 61[sup]2[/sup] * 593 * 983 * 1153 [COLOR=green]×[/COLOR] 1973. 61[sup]2[/sup] = 3721. In this example the factor 59704785388637019242567 could have been found in stage 1 with b1 as low as 3721. Also, Prime95's P-1 stage 2 with b1 = 2000 and b2 = 4000 would find this factor because the largest prime-power factor of 4934285493275531 is less than 4000 and all other prime-power factors are less than 2000. (In fact, b1/b2 as low as b1 = 1973, b2 = 3721 would have worked.)[/QUOTE] I stand corrected!:redface: |

[quote=axn1]AFAIK, stage 2 only considers primes and not prime powers. So this would not be found.[/quote]Oops, I forgot that I had a weakness in my stage 2 understanding, and got carried-away with my prime-power correction. Thank you.
jocelynl, I presume you've noted axn1's correction to my erroneous paragraph about stage 2. |

BTW, let this be a lesson.
I failed to actually TRY running Pminus1=6049993,2000,4000,0,0 to confirm that stage 2 would find the 61[sup]2[/sup] = 3721 prime-power factor of 4934285493275531 before I made my erroneous posting: [quote=cheesehead, in error!]Also, Prime95's P-1 stage 2 with b1 = 2000 and b2 = 4000 would find this factor because the largest prime-power factor of 4934285493275531 is less than 4000 and all other prime-power factors are less than 2000. (In fact, b1/b2 as low as b1 = 1973, b2 = 3721 would have worked.)[/quote] It would've taken just 4 minutes, including set-up time, to run that on my Athlon 1200. But that didn't occur to me before I threw in that erroneous last paragraph about stage 2, which was an idea I got just as I was about to post all the preceding (and correct) part about stage 1[SIZE=1], which was itself a correction of my first hasty posting ...:redface: [/SIZE] |

[QUOTE=jocelynl]I never do stage 2 as it messes stage 1 save files. I keep my files as it continues to higher level from where it leftoff.[/QUOTE]
Please notice that in general the factor is found in step 2. You can read how the p-1 works at [URL="http://www.mersennewiki.org/index.php/P-1"]MersenneWiki[/URL]. |

[QUOTE=alpertron]Please notice that in general the factor is found in step 2. You can read how the p-1 works at [URL="http://www.mersennewiki.org/index.php/P-1"]MersenneWiki[/URL].[/QUOTE]
I find that step 2 is a wast of time since all your effort are thrown to garbage when you test step 1 a little further. It would be nice if step 2 could test past 2^32 but I'm not complaining. It's fun to have a factor pop up once in a while. |

All times are UTC. The time now is 04:57. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.