20151026, 13:59  #1 
Dec 2002
829 Posts 
unexpected number of relative primes
I am doing P1 on many exponents in the range 12,000,00013,000,000. All report 480 relative primes, but one exponent, M12680077 reports 192 relative primes. Any reason why that may be?
Code:
[Worker #1 Oct 25 21:20] Worker starting [Worker #1 Oct 25 21:20] Setting affinity to run worker on logical CPU #1 [Worker #2 Oct 25 21:20] Waiting 5 seconds to stagger worker starts. [Worker #1 Oct 25 21:20] P1 on M12670211 with B1=300000, B2=6000000 [Worker #1 Oct 25 21:20] Chance of finding a factor is an estimated 4.64% [Worker #1 Oct 25 21:20] Using FFT length 640K, Pass1=640, Pass2=1K [Worker #1 Oct 25 21:20] M12670211 stage 1 is 56.94% complete. [Worker #2 Oct 25 21:20] Worker starting [Worker #2 Oct 25 21:20] Setting affinity to run worker on logical CPU #2 [Worker #2 Oct 25 21:20] P1 on M12672851 with B1=300000, B2=6000000 [Worker #2 Oct 25 21:20] Chance of finding a factor is an estimated 4.64% [Worker #2 Oct 25 21:20] Using FFT length 640K, Pass1=640, Pass2=1K [Worker #2 Oct 25 21:21] Available memory is 1271MB. [Worker #2 Oct 25 21:21] Using 1269MB of memory. Processing 241 relative primes (188 of 480 already processed). [Worker #2 Oct 25 21:25] M12672851 stage 2 is 66.87% complete. [Worker #1 Oct 25 21:53] M12670211 stage 1 is 73.78% complete. Time: 1944.823 sec. [Worker #2 Oct 25 22:24] M12672851 stage 2 is 89.26% complete. Time: 3578.716 sec. [Worker #2 Oct 25 22:25] Available memory is 1271MB. [Worker #2 Oct 25 22:25] Using 307MB of memory. Processing 51 relative primes (429 of 480 already processed). [Worker #1 Oct 25 22:25] M12670211 stage 1 is 90.62% complete. Time: 1943.938 sec. [Worker #1 Oct 25 22:44] M12670211 stage 1 complete. 388218 transforms. Time: 5043.782 sec. [Worker #1 Oct 25 22:45] Stage 1 GCD complete. Time: 36.402 sec. [Worker #1 Oct 25 22:45] Available memory is 973MB. [Worker #1 Oct 25 22:45] Using 970MB of memory. Processing 182 relative primes (0 of 480 already processed). [Worker #2 Oct 25 22:58] M12672851 stage 2 complete. 247334 transforms. Time: 5826.484 sec. [Worker #2 Oct 25 22:58] Stage 2 GCD complete. Time: 44.308 sec. [Worker #2 Oct 25 22:58] M12672851 completed P1, B1=300000, B2=6000000, E=6, We8: 47BDCB4F [Worker #2 Oct 25 22:58] P1 on M12674267 with B1=300000, B2=6000000 [Worker #2 Oct 25 22:58] Chance of finding a factor is an estimated 4.64% [Worker #2 Oct 25 22:58] Using FFT length 640K, Pass1=640, Pass2=1K [Worker #2 Oct 25 23:30] M12674267 stage 1 is 16.84% complete. Time: 1916.145 sec. [Worker #1 Oct 25 23:46] M12670211 stage 2 is 20.98% complete. Time: 3674.827 sec. [Worker #2 Oct 26 00:02] M12674267 stage 1 is 33.68% complete. Time: 1872.311 sec. [Worker #1 Oct 26 00:33] Available memory is 1271MB. [Worker #1 Oct 26 00:33] Using 1269MB of memory. Processing 241 relative primes (182 of 480 already processed). [Worker #2 Oct 26 00:33] M12674267 stage 1 is 50.52% complete. Time: 1906.791 sec. [Worker #1 Oct 26 00:46] M12670211 stage 2 is 41.71% complete. Time: 3557.109 sec. [Worker #2 Oct 26 01:04] M12674267 stage 1 is 67.36% complete. Time: 1815.807 sec. [Worker #2 Oct 26 01:34] M12674267 stage 1 is 84.20% complete. Time: 1817.135 sec. [Worker #1 Oct 26 01:46] M12670211 stage 2 is 64.09% complete. Time: 3611.279 sec. [Worker #2 Oct 26 02:05] M12674267 stage 1 complete. 895430 transforms. Time: 11188.762 sec. [Worker #2 Oct 26 02:06] Stage 1 GCD complete. Time: 39.317 sec. [Worker #2 Oct 26 02:06] Available memory is 640MB. [Worker #1 Oct 26 02:06] Restarting worker with new memory settings. [Worker #1 Oct 26 02:06] P1 on M12670211 with B1=300000, B2=6000000 [Worker #1 Oct 26 02:06] Chance of finding a factor is an estimated 4.64% [Worker #1 Oct 26 02:06] Using FFT length 640K, Pass1=640, Pass2=1K [Worker #1 Oct 26 02:06] Available memory is 644MB. [Worker #1 Oct 26 02:06] Using 641MB of memory. Processing 117 relative primes (182 of 480 already processed). [Worker #2 Oct 26 02:06] Using 636MB of memory. Processing 116 relative primes (0 of 480 already processed). [Worker #1 Oct 26 02:08] M12670211 stage 2 is 71.92% complete. [Worker #1 Oct 26 02:30] Available memory is 644MB. [Worker #1 Oct 26 02:30] Using 641MB of memory. Processing 117 relative primes (299 of 480 already processed). [Worker #1 Oct 26 02:54] Available memory is 644MB. [Worker #1 Oct 26 02:54] Using 373MB of memory. Processing 64 relative primes (416 of 480 already processed). [Worker #2 Oct 26 03:03] M12674267 stage 2 is 20.59% complete. Time: 3418.588 sec. [Worker #1 Oct 26 03:06] M12670211 stage 2 is 91.46% complete. Time: 3457.818 sec. [Worker #2 Oct 26 03:12] Available memory is 907MB. [Worker #2 Oct 26 03:12] Using 904MB of memory. Processing 169 relative primes (116 of 480 already processed). [Worker #1 Oct 26 03:31] M12670211 stage 2 complete. 220836 transforms. Time: 5122.251 sec. [Worker #1 Oct 26 03:32] Stage 2 GCD complete. Time: 38.663 sec. [Worker #1 Oct 26 03:32] M12670211 completed P1, B1=300000, B2=6000000, E=6, We8: 4792CB70 [Worker #1 Oct 26 03:32] P1 on M12669973 with B1=300000, B2=6000000 [Worker #1 Oct 26 03:32] Chance of finding a factor is an estimated 4.64% [Worker #1 Oct 26 03:32] Using FFT length 640K, Pass1=640, Pass2=1K [Worker #2 Oct 26 04:00] M12674267 stage 2 is 41.40% complete. Time: 3467.808 sec. [Worker #1 Oct 26 04:05] M12669973 stage 1 is 16.84% complete. Time: 2006.016 sec. [Worker #1 Oct 26 04:38] M12669973 stage 1 is 33.68% complete. Time: 1995.051 sec. [Worker #2 Oct 26 04:49] Available memory is 1271MB. [Worker #2 Oct 26 04:49] Using 1036MB of memory. Processing 195 relative primes (285 of 480 already processed). [Worker #2 Oct 26 04:59] M12674267 stage 2 is 62.18% complete. Time: 3501.661 sec. [Worker #1 Oct 26 05:11] M12669973 stage 1 is 50.52% complete. Time: 1964.787 sec. [Worker #1 Oct 26 05:44] M12669973 stage 1 is 67.36% complete. Time: 1951.232 sec. [Worker #2 Oct 26 05:57] M12674267 stage 2 is 84.33% complete. Time: 3473.155 sec. [Worker #1 Oct 26 06:16] M12669973 stage 1 is 84.20% complete. Time: 1951.761 sec. [Worker #2 Oct 26 06:39] M12674267 stage 2 complete. 705974 transforms. Time: 16387.541 sec. [Worker #2 Oct 26 06:39] Stage 2 GCD complete. Time: 38.260 sec. [Worker #2 Oct 26 06:39] M12674267 completed P1, B1=300000, B2=6000000, E=6, We8: 478CCB51 [Worker #2 Oct 26 06:39] P1 on M12680077 with B1=300000, B2=6000000 [Worker #2 Oct 26 06:39] Chance of finding a factor is an estimated 4.64% [Worker #2 Oct 26 06:39] Using FFT length 672K, Pass1=896, Pass2=768 [Worker #1 Oct 26 06:46] M12669973 stage 1 complete. 895430 transforms. Time: 11690.266 sec. [Worker #1 Oct 26 06:47] Stage 1 GCD complete. Time: 35.696 sec. [Worker #1 Oct 26 06:47] Available memory is 1271MB. [Worker #1 Oct 26 06:47] Using 1269MB of memory. Processing 241 relative primes (0 of 480 already processed). [Worker #2 Oct 26 07:19] M12680077 stage 1 is 16.84% complete. Time: 2386.904 sec. [Worker #1 Oct 26 07:48] M12669973 stage 2 is 21.03% complete. Time: 3646.844 sec. [Worker #2 Oct 26 07:59] M12680077 stage 1 is 33.68% complete. Time: 2405.173 sec. [Worker #2 Oct 26 08:39] M12680077 stage 1 is 50.52% complete. Time: 2392.055 sec. [Worker #1 Oct 26 08:48] M12669973 stage 2 is 43.40% complete. Time: 3632.655 sec. [Worker #1 Oct 26 09:06] Available memory is 1271MB. [Worker #1 Oct 26 09:06] Using 1259MB of memory. Processing 239 relative primes (241 of 480 already processed). [Worker #2 Oct 26 09:19] M12680077 stage 1 is 67.36% complete. Time: 2404.725 sec. [Worker #1 Oct 26 09:48] M12669973 stage 2 is 64.37% complete. Time: 3580.115 sec. [Worker #2 Oct 26 09:58] M12680077 stage 1 is 84.20% complete. Time: 2350.795 sec. [Worker #2 Oct 26 10:38] M12680077 stage 1 complete. 895432 transforms. Time: 14297.709 sec. [Worker #2 Oct 26 10:38] Stage 1 GCD complete. Time: 38.352 sec. [Worker #2 Oct 26 10:38] Available memory is 640MB. [Worker #1 Oct 26 10:38] Restarting worker with new memory settings. [Worker #1 Oct 26 10:38] P1 on M12669973 with B1=300000, B2=6000000 [Worker #1 Oct 26 10:38] Chance of finding a factor is an estimated 4.64% [Worker #1 Oct 26 10:38] Using FFT length 640K, Pass1=640, Pass2=1K [Worker #1 Oct 26 10:38] Available memory is 642MB. [Worker #1 Oct 26 10:38] Using 641MB of memory. Processing 117 relative primes (241 of 480 already processed). [Worker #2 Oct 26 10:38] Using 638MB of memory. Processing 110 relative primes (0 of 192 already processed). [Worker #1 Oct 26 10:41] M12669973 stage 2 is 83.16% complete. [Worker #1 Oct 26 11:04] Available memory is 642MB. [Worker #1 Oct 26 11:04] Using 641MB of memory. Processing 117 relative primes (358 of 480 already processed). [Worker #1 Oct 26 11:29] Available memory is 642MB. [Worker #1 Oct 26 11:29] Using 75MB of memory. Processing 5 relative primes (475 of 480 already processed). [Worker #1 Oct 26 11:32] M12669973 stage 2 complete. 138172 transforms. Time: 3244.862 sec. [Worker #1 Oct 26 11:33] Stage 2 GCD complete. Time: 36.269 sec. [Worker #1 Oct 26 11:33] M12669973 completed P1, B1=300000, B2=6000000, E=6, We8: 478ECB6E [Worker #1 Oct 26 11:33] P1 on M12670711 with B1=300000, B2=6000000 [Worker #1 Oct 26 11:33] Chance of finding a factor is an estimated 4.64% [Worker #1 Oct 26 11:33] Using FFT length 640K, Pass1=640, Pass2=1K [Worker #2 Oct 26 11:51] M12680077 stage 2 is 20.30% complete. Time: 4367.141 sec. [Worker #1 Oct 26 12:05] M12670711 stage 1 is 16.84% complete. Time: 1940.531 sec. [Worker #1 Oct 26 12:38] M12670711 stage 1 is 33.68% complete. Time: 1987.602 sec. [Worker #2 Oct 26 13:04] M12680077 stage 2 is 41.19% complete. Time: 4399.671 sec. [Worker #1 Oct 26 13:12] M12670711 stage 1 is 50.52% complete. Time: 2003.194 sec. [Worker #1 Oct 26 13:45] M12670711 stage 1 is 67.36% complete. Time: 1986.965 sec. [Worker #2 Oct 26 14:01] Available memory is 1271MB. [Worker #2 Oct 26 14:01] Using 489MB of memory. Processing 82 relative primes (110 of 192 already processed). 
20151026, 15:08  #2 
"Jacob"
Sep 2006
Brussels, Belgium
2^{2}·439 Posts 
The memory was a bit low at the start of that Stage 2 run.
Jacob Last fiddled with by S485122 on 20151026 at 15:10 Reason: word order and too much quoting. 
20151026, 20:49  #3 
Dec 2002
829 Posts 
I was under the impression that a lesser amount of available memory could affect the BrentSuyama factor (E=0 or E=6 etc) or the number of relative primes processed in one batch, but would not affect the total amount of relative primes. If not so, does it somehow affect the change of finding a prime? It did show up in the results with the same E=6 as the others.

20151026, 21:19  #4  
Nov 2003
1D24_{16} Posts 
Quote:
Why does their cardinality matter? 

20151027, 18:31  #5  
Dec 2002
33D_{16} Posts 
Quote:
Specifically I could not figure out why there would by less relative primes if the B1 and B2 bounds remain the same for comparable exponents, and I don't see the lesser amount of relative primes being caused by the amount of available memory, but I may be wrong. 

20151027, 22:12  #6  
P90 years forever!
Aug 2002
Yeehaw, FL
7,691 Posts 
Quote:
The more relative primes used, the more memory is consumed and the faster stage 2 will go. Before you get too excited, were talking a few percent faster  not worth losing any sleep over if prime95 is now selecting a slightly smaller number of relative primes. Maybe there is a problem with prime95's estimate of the amount of memory that is available  or maybe there were more workers in stage 2 at the time this one exponent started stage 2. 

20151027, 22:31  #7 
Dec 2002
829 Posts 
OK, good to know. So, if I understand it correctly, it does not affect the chance of finding a factor, since the bounds and E are the same, it only slows down the program a bit, correct?

20151028, 00:46  #8 
"Kieren"
Jul 2011
In My Own Galaxy!
10158_{10} Posts 
Before I gave up P1 on the CPU recently, I was running a single worker which had 28672 MB available to it. It never used more than a bit under 17 GiB, with RP 480. I don't know if this relates, but it is something I wondered about.

20151029, 11:52  #9  
Nov 2003
16444_{8} Posts 
Quote:
The second stage of P1 computes product over i and j of (a_i  b_j) where a_i and b_j are relatively prime arithmetic sequences. It uses FFT's. The longer the sequences, the more efficient the FFT. However, the sequences (and hence the product) can be broken up into pieces depending on memory. This is a slight simplification. Last fiddled with by R.D. Silverman on 20151029 at 11:53 

20151029, 15:04  #10 
Aug 2002
Buenos Aires, Argentina
10101101111_{2} Posts 
AFAIK Prime95 does not use FFT for Step 2. It uses the standard continuation, because FFT would need a lot of memory when the numbers to be factored have millions of digits. Notice that we are talking about FFT for P1, not FFT for each multiplication which Prime95 always performs.
The P1 algorithm tries to find a factor p of N such that p1 has all factors less than B1 and one factor between B1 and B2. If all factors are less than B1, step 1 will catch it. Since for random numbers the largest factor is a lot larger than the second largest factor (RSA numbers are very uncommon), the factor p will be usually found on step 2. In step 2 the code will have to power the output of step 1 to the different primes between B1 and B2 modulo N. These powers will be multiplied modulo N and at the end of step 2 a gcd is done between the product and N in order to hopefully find the factor p. The most obvious optimization is not to perform the exponentiations, but to precompute the output of step 1 raised to the first even numbers. In this way the exponentiation is replaced by one multiplication. According to https://en.wikipedia.org/wiki/Prime_gap you will need to precompute 57 constants (even powers of the output of Step 1) for B2=1M, 77 constants for B2=10M, 110 constants for B2=100M and 141 constants for B2=1000M. Example: B1 = 100, B2=1000, output of step 1: q. The primes after 100 are 101, 103, 107, 109, 113, 127, 131,... So we have to compute r_{101}=q^{101}, q_{101}=q*r_{101}, r_{103}=r_{101}*q^{2}, q_{103}=q_{101}*r_{103}, r_{107}=r_{103}*q^{4}, q_{107}=q_{103}*r_{107}, r_{109}=r_{107}*q^{2}, q_{109}=q_{107}*r_{109}, r_{113}=r_{109}*q^{4}, q_{113}=q_{109}*r_{113}, r_{127}=r_{113}*q^{14}, q_{127}=q_{113}*r_{127}, r_{131}=r_{127}*q^{4}, q_{131}=q_{127}*r_{131}, ... all multiplications done modulo N. At the end of step 2 the computer checks whether 1 < gcd(q_{997}, N) < N. If this is the case, the algorithm is successful. Since this requires too many precomputations: q^{2}, q^{4}, q^{6}, and so on, there are other methods with less precomputations, but the problem is that the program will use the power of the output of step 1 raised to the power of a composite number, and this is not useful, slowing down the algorithm. Remember that Prime95 multiplies numbers of millions of digits, so the number of multiplications has to be reduced as much as possible. So you will notice that there is a trade off between memory and speed. Last fiddled with by alpertron on 20151029 at 15:21 
20151029, 15:29  #11  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
so for example B1=5000 if this is true should test all composite k up to k = 25000000. edit: or greater because 5000 isn't prime so it should clear the composite k from below k=nextprime(precprime(5000)+1)^2 aka 25030009 Last fiddled with by science_man_88 on 20151029 at 15:37 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Unexpected biases in the distribution of consecutive primes  axn  Lounge  21  20160605 13:00 
Estimating the number of primes in a partiallyfactored number  CRGreathouse  Probability & Probabilistic Number Theory  15  20140813 18:46 
P1 factoring, relative primes  timbit  Information & Answers  0  20090313 18:45 
relative speed of processors  Primeinator  Hardware  10  20050227 18:03 
Relative speeds of hardware for different types of work  S00113  Hardware  7  20040420 19:58 