mersenneforum.org unexpected number of relative primes
 Register FAQ Search Today's Posts Mark Forums Read

 2015-10-26, 13:59 #1 tha     Dec 2002 11011000002 Posts unexpected number of relative primes I am doing P-1 on many exponents in the range 12,000,000-13,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] P-1 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] P-1 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 P-1, B1=300000, B2=6000000, E=6, We8: 47BDCB4F [Worker #2 Oct 25 22:58] P-1 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] P-1 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 P-1, B1=300000, B2=6000000, E=6, We8: 4792CB70 [Worker #1 Oct 26 03:32] P-1 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 P-1, B1=300000, B2=6000000, E=6, We8: 478CCB51 [Worker #2 Oct 26 06:39] P-1 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] P-1 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 P-1, B1=300000, B2=6000000, E=6, We8: 478ECB6E [Worker #1 Oct 26 11:33] P-1 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).
2015-10-26, 15:08   #2
S485122

"Jacob"
Sep 2006
Brussels, Belgium

1,901 Posts

Quote:
 Originally Posted by tha Code: [Worker #2 Oct 26 10:38] Available memory is 640MB.
The memory was a bit low at the start of that Stage 2 run.

Jacob

Last fiddled with by S485122 on 2015-10-26 at 15:10 Reason: word order and too much quoting.

2015-10-26, 20:49   #3
tha

Dec 2002

25×33 Posts

Quote:
 Originally Posted by S485122 The memory was a bit low at the start of that Stage 2 run.
I was under the impression that a lesser amount of available memory could affect the Brent-Suyama 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.

2015-10-26, 21:19   #4
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2×33×139 Posts

Quote:
 Originally Posted by tha I am doing P-1 on many exponents in the range 12,000,000-13,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] P-1 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] P-1 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 P-1, B1=300000, B2=6000000, E=6, We8: 47BDCB4F [Worker #2 Oct 25 22:58] P-1 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] P-1 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 P-1, B1=300000, B2=6000000, E=6, We8: 4792CB70 [Worker #1 Oct 26 03:32] P-1 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 P-1, B1=300000, B2=6000000, E=6, We8: 478CCB51 [Worker #2 Oct 26 06:39] P-1 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] P-1 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 P-1, B1=300000, B2=6000000, E=6, We8: 478ECB6E [Worker #1 Oct 26 11:33] P-1 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).
You might start by asking yourself. How are these 'relative primes' used in the algorithm? What is their purpose?
Why does their cardinality matter?

2015-10-27, 18:31   #5
tha

Dec 2002

25·33 Posts

Quote:
 Originally Posted by R.D. Silverman You might start by asking yourself. How are these 'relative primes' used in the algorithm? What is their purpose? Why does their cardinality matter?
Well, I just encountered something I didn't expect. I did spend half an hour on reading up on 'relative primes' and Pollards algorithm before my first posting, but that was not enough for me to determine the cause. My interest in this case was not academic, but rather to see if any action on my side may be required to optimise the settings. All respect for your knowledge and willingness to teach as well as your reminders that we can elevate ourselves by keeping up more discipline in our own studying. But I am also busy doing other things and just want to know if and what would be needed to avoid inefficiencies, if any indeed do occur.

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.

2015-10-27, 22:12   #6
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

815110 Posts

Quote:
 Originally Posted by tha ...and I don't see the lesser amount of relative primes being caused by the amount of available memory, but I may be wrong.
The amount of available memory is a major factor in prime95's choice of the number of relative primes.

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.

2015-10-27, 22:31   #7
tha

Dec 2002

11011000002 Posts

Quote:
 Originally Posted by Prime95 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.
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?

2015-10-28, 00:46   #8

"Kieren"
Jul 2011
In My Own Galaxy!

2·3·1,693 Posts

Quote:
 Originally Posted by Prime95 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.
Before I gave up P-1 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.

2015-10-29, 11:52   #9
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2×33×139 Posts

Quote:
 Originally Posted by kladner Before I gave up P-1 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.
Read my joint paper with Peter.

The second stage of P-1 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 2015-10-29 at 11:53

 2015-10-29, 15:04 #10 alpertron     Aug 2002 Buenos Aires, Argentina 22·373 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 P-1, not FFT for each multiplication which Prime95 always performs. The P-1 algorithm tries to find a factor p of N such that p-1 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 r101=q101, q101=q*r101, r103=r101*q2, q103=q101*r103, r107=r103*q4, q107=q103*r107, r109=r107*q2, q109=q107*r109, r113=r109*q4, q113=q109*r113, r127=r113*q14, q127=q113*r127, r131=r127*q4, q131=q127*r131, ... all multiplications done modulo N. At the end of step 2 the computer checks whether 1 < gcd(q997, N) < N. If this is the case, the algorithm is successful. Since this requires too many precomputations: q2, q4, q6, 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 2015-10-29 at 15:21
2015-10-29, 15:29   #11
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2×3×23×61 Posts

Quote:
 Originally Posted by alpertron So you will notice that there is a trade off between memory and speed.
another thing to keep in mind is that P-1 is adapted for mersenne factoring to find factors when k is B1 smooth.

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 2015-10-29 at 15:37

 Similar Threads Thread Thread Starter Forum Replies Last Post axn Lounge 21 2016-06-05 13:00 CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46 timbit Information & Answers 0 2009-03-13 18:45 Primeinator Hardware 10 2005-02-27 18:03 S00113 Hardware 7 2004-04-20 19:58

All times are UTC. The time now is 07:26.

Sat Jan 28 07:26:09 UTC 2023 up 163 days, 4:54, 0 users, load averages: 1.53, 1.48, 1.42