mersenneforum.org > Math trial factoring and P-1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-01-06, 21:20 #1 jocelynl   Sep 2002 2·131 Posts trial factoring and P-1 When 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 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.
2006-01-08, 04:29   #2
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by jocelynl When doing P-1 factoring the b1 is actually b1*M
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 2p-1 that are to be found by the P-1 method.

That is, stage 1 P-1 with b1 = 10000 performed on 2p-1 will find any factor 2kp+1 of 2p-1 in which the largest prime factor of k is less than (or equal to, if b1 were prime itself) 10000.

Last fiddled with by cheesehead on 2006-01-08 at 04:42

2006-01-08, 05:45   #3
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts

Quote:
 Originally Posted by 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 2p-1 that are to be found by the P-1 method. That is, stage 1 P-1 with b1 = 10000 performed on 2p-1 will find any factor 2kp+1 of 2p-1 in which the largest prime factor of k is less than (or equal to, if b1 were prime itself) 10000.
Correction:

My understanding is that, in the Prime95 implementation of the P-1 algorithm, b1 is the upper limit on the power-of-a-prime factors of the "k" of potential factors 2kp+1 of 2p-1 that are to be found by the P-1 method.

That is, stage 1 P-1 with b1 = 10000 performed on 2p-1 will find any factor 2kp+1 of 2p-1 in which the largest power-of-a-prime factor of k is less than (or equal to, if b1 were prime itself) 10000.

Example:

59704785388637019242567 is a factor of 26049993 - 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 = 612 * 593 * 983 * 1153 × 1973.

612 = 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.)

2006-01-08, 08:14   #4
axn

Jun 2003

22·32·151 Posts

Quote:
 Originally Posted by 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.)
AFAIK, stage 2 only considers primes and not prime powers. So this would not be found.

2006-01-08, 16:16   #5
jocelynl

Sep 2002

2·131 Posts

Quote:
 Originally Posted by cheesehead Correction: My understanding is that, in the Prime95 implementation of the P-1 algorithm, b1 is the upper limit on the power-of-a-prime factors of the "k" of potential factors 2kp+1 of 2p-1 that are to be found by the P-1 method. That is, stage 1 P-1 with b1 = 10000 performed on 2p-1 will find any factor 2kp+1 of 2p-1 in which the largest power-of-a-prime factor of k is less than (or equal to, if b1 were prime itself) 10000. Example: 59704785388637019242567 is a factor of 26049993 - 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 = 612 * 593 * 983 * 1153 × 1973. 612 = 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.)
I stand corrected!

2006-01-09, 02:35   #6
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts

Quote:
 Originally Posted by axn1 AFAIK, stage 2 only considers primes and not prime powers. So this would not be found.
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.

Last fiddled with by cheesehead on 2006-01-09 at 02:37

2006-01-22, 18:48   #7
cheesehead

"Richard B. Woods"
Aug 2002
Wisconsin USA

1E0C16 Posts

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 612 = 3721 prime-power factor of 4934285493275531 before I made my erroneous posting:
Quote:
 Originally Posted by 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.)
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, which was itself a correction of my first hasty posting ...

2006-01-22, 19:47   #8
alpertron

Aug 2002
Buenos Aires, Argentina

1,493 Posts

Quote:
 Originally Posted by 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.
Please notice that in general the factor is found in step 2. You can read how the p-1 works at MersenneWiki.

2006-02-01, 14:12   #9
jocelynl

Sep 2002

2×131 Posts

Quote:
 Originally Posted by alpertron Please notice that in general the factor is found in step 2. You can read how the p-1 works at MersenneWiki.
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.

Last fiddled with by jocelynl on 2006-02-01 at 14:13

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Unregistered Information & Answers 5 2012-08-02 03:47 odin Software 4 2010-08-08 20:23 S485122 PrimeNet 1 2007-09-06 00:52 michael Software 23 2004-01-06 08:54 gbvalor Math 4 2003-05-22 02:04

All times are UTC. The time now is 17:10.

Sat Jan 28 17:10:11 UTC 2023 up 163 days, 14:38, 0 users, load averages: 1.00, 1.12, 1.06

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔