P-1 question

JuanTutors · 2012-09-28, 14:46

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?

axn · 2012-09-28, 15:11

Quote:

Originally Posted by dominicanpapi82

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

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].

JuanTutors · 2019-08-03, 02:59

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.

kriesel · 2019-08-03, 14:53

Quote:

Originally Posted by JuanTutors

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.
q^{floor(log base q of B1)}, not just q¹.
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 3^2Ep "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.

2012-09-28, 14:46	#1
JuanTutors "Juan Tutors" Mar 2004 2⁴·5·7 Posts	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?

2019-08-03, 02:59	#3
JuanTutors "Juan Tutors" Mar 2004 2⁴·5·7 Posts	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