mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-09-28, 14:46   #1
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

24·5·7 Posts
Default P-1 question

It's been a while since I fully read the way P-1 test works so please forgive me if I get this wrong:

Suppose you do P-1 test on M=M332######, with bounds B1=3015000 and B2=48240000.

P-1 stage 1 finds no factor, so the test starts P-1 stage 2 processing 6 of 480 relative primes.

From what I understand, stage 2 with those first 6 relative primes finds six numbers modulo , hoping for a residue of something not equal to 1. Is this correct?

If this is correct, then the reason it starts processing the next 6 relative primes is because all those residues are 1, correct?

Then, instead of starting the next six relative primes in stage 2 with the mod that it found in stage 1, isn't it better to arbitrarily pick one of the mods that was found in stage 2 with the first six relatively primes and use that one with the second six relative primes. Then, pick one of the mods from those second six relative primes and use that for the third six relative primes, etc?
JuanTutors is offline   Reply With Quote
Old 2012-09-28, 15:11   #2
axn
 
axn's Avatar
 
Jun 2003

5×29×37 Posts
Default

Quote:
Originally Posted by dominicanpapi82 View Post
From what I understand, stage 2 with those first 6 relative primes finds six numbers modulo , hoping for a residue of something not equal to 1. Is this correct?

If this is correct, then the reason it starts processing the next 6 relative primes is because all those residues are 1, correct?
Nope. It processes only 6 at a time, because you gave it enough memory to only process 6 at a time. You give more memory, it'll do more rel primes at a time.

Now, you only know if P-1 succeeded or not when you do a GCD. Since GCD is an expensive operation and chance of success is low, you're better off completing the whole stage 2 and doing the GCD.

Quote:
Originally Posted by dominicanpapi82 View Post
Then, instead of starting the next six relative primes in stage 2 with the mod that it found in stage 1, isn't it better to arbitrarily pick one of the mods that was found in stage 2 with the first six relatively primes and use that one with the second six relative primes. Then, pick one of the mods from those second six relative primes and use that for the third six relative primes, etc?
The math doesn't work like that. [IOW, if it was that easy, it would have already been done].
axn is offline   Reply With Quote
Old 2019-08-03, 02:59   #3
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

24·5·7 Posts
Default

I am not a fan of resurrecting threads, but a similar thought came to me when I was self-stalking (back after 10 years ... wow I said some dumb stuff!) and thought that there might be an easy-to-do implementation of the initial idea, minus the misunderstood math.

So from my understanding from reading the GIMPS website, say E is the product of all primes less than B1. We calculate gcd(3^{2Ep}-1,Mp). If no factor is found, we go on to stage 2.

My suggestion WAS for stage 2, if 6 of 480 relative primes are processed at a time. (Yes, I know that way more relative primes are tested nowadays. I'm back to the project after a decade off.) At the time, I thought one of the the 6 GCDs could be used, but of course it can't. But when I was thinking about it again, I realized that 3^{2Ep}-1 is so large that we must be using 3^{2Ep}-1 (mod Mp), which has the same GCD with Mp. If I'm wrong about that, stop reading here.

So my idea actually holds now, in the age of near-instantly-writable files on SSDs. My suggestion is, for any one of the 6 relative primes that are being used in this example, store the value of that number whose GCD you are taking mod Mp on the drive, before taking the GCD. Then, under the assumption that no factor was found, use that stored number in the next step with the next 6 relative primes. Save one of the new numbers, and keep doing that until the process is done. That way the B2 stage is actually done with not 1 prime between B1 and B2 at a time, but in this example, 1/6 of the primes between B1 and B2. The fraction today would be smaller because it's not 6 relative primes processed at a time, but it's not 1/(\pi(B2)-\pi(B1)) which is what it is now.

I know that this is a slow process on a spinning drive, but on an SSD, this should be quite fast. The only added time is the time it takes to write the number to the drive and then pick up the number again.

Am I understanding the process right? Feel free to burst my bubble, but I kinda like the idea. I feel like it can save a large number of tests.

Last fiddled with by JuanTutors on 2019-08-03 at 03:20
JuanTutors is offline   Reply With Quote
Old 2019-08-03, 14:53   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3·5·433 Posts
Default

Quote:
Originally Posted by JuanTutors View Post
say E is the product of all primes less than B1. We calculate gcd(3^{2Ep}-1,Mp).
1 E is the product of POWERS OF primes less than B1. https://en.wikipedia.org/wiki/Pollar...92_1_algorithm.
qfloor(log base q of B1), not just q1.
I think that's described as E is B1-powersmooth, not merely B1-smooth. That makes E a much larger number.

2 As I recall, in prime95 E is calculated ahead of the exponentiation only up to some million bits size, then if applicable the rest of E is computed along the way.

3 The mod Mp is applied many times along the way to keep the calculation of 32Ep "small" enough to be possible.
Quote:

If no factor is found, we go on to stage 2.

My suggestion WAS for stage 2, if 6 of 480 relative primes are processed at a time. (Yes, I know that way more relative primes are tested nowadays. I'm back to the project after a decade off.) At the time, I thought one of the the 6 GCDs could be used, but of course it can't. But when I was thinking about it again, I realized that 3^{2Ep}-1 is so large that we must be using 3^{2Ep}-1 (mod Mp), which has the same GCD with Mp. If I'm wrong about that, stop reading here.

So my idea actually holds now, in the age of near-instantly-writable files on SSDs.
4 Why bother with any kind of a disk; if there's enough ram, use a ram buffer.
5 Number of relative primes per pass in stage 2 can range anywhere from 1, to all of them, depending on exponent and available RAM. There are also scenarios where it is not possible to run even 1.

6 Gcd's are expensive and run on one cpu core.
7 There's ONE gcd at the end of stage 1; ONE at the end of stage 2, in prime95 or CUDAPm1 or GpuOwl.
kriesel is online now   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 00:37.


Fri May 27 00:37:21 UTC 2022 up 42 days, 22:38, 0 users, load averages: 1.80, 2.01, 2.02

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

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