mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-04-27, 19:28   #1
LarsNet
 
Mar 2021

22×11 Posts
Minus Where can i find huge lists of primes up to as close to 2^128 as possible of SPRP's

For example i can find 2-SPRP-2-to-64.zip at https://miller-rabin.appspot.com/ Are there any other repos or places i can find large numbers like this. Wikipedia often mention tests at higher than 2^64 but fails to link to them, i'm wondering if anyone here knows of any places to find numbers like these to test against.

Also, if such lists don't exist publicly, if i wanted to make a 2-SPRP-2 list to say 2^79, what would be the minimum investment required to do something like this and what kind of equipment what be needed.

Last fiddled with by LarsNet on 2021-04-27 at 19:45
LarsNet is offline   Reply With Quote
Old 2021-04-27, 20:49   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23×17×29 Posts
Default

I would imagine a list up to 2^65 would take twice as much disk space as the list up to 2^64. Thus such a file would be 2^64 times as big as the the list up to 2^64. That would be about 1,000,000,000,000,000,000,000 Gigabytes.

Last fiddled with by paulunderwood on 2021-04-27 at 20:49
paulunderwood is online now   Reply With Quote
Old 2021-04-27, 22:15   #3
LarsNet
 
Mar 2021

22×11 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I would imagine a list up to 2^65 would take twice as much disk space as the list up to 2^64. Thus such a file would be 2^64 times as big as the the list up to 2^64. That would be about 1,000,000,000,000,000,000,000 Gigabytes.
The lists i'm looking to build would only be a smaller subset of the numbers, like for this list i have from the miller rabin site is composite 2-SPRP only, so the size isn't too bad:

Code:
$ ls -al 2-SPRP-2-to-64.txt
-rw-rw-r-- 1 user user 663879564 Apr 19  2011 2-SPRP-2-to-64.txt
LarsNet is offline   Reply With Quote
Old 2021-04-27, 22:57   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

3·19·89 Posts
Default

Quote:
Originally Posted by LarsNet View Post
so the size isn't too bad:

Code:
$ ls -al 2-SPRP-2-to-64.txt
-rw-rw-r-- 1 user user 663879564 Apr 19  2011 2-SPRP-2-to-64.txt
663MB for 2^64 list. 2^79 is 32000x bigger than 2^64, so such a list would be.... big.

I think you'd be better off generating such a list live and testing them as they're generated. I'd rather spend 100x running time than 100x disk space! Of course, I've no idea how fast they are to generate vs read from disk, nor how many times you'll want to use the list- maybe you should find out before you buy 20TB of storage.

Last fiddled with by VBCurtis on 2021-04-27 at 22:57
VBCurtis is offline   Reply With Quote
Old 2021-04-27, 22:57   #5
tuckerkao
 
"Tucker Kao"
Jan 2020
Head Base M168202123

5·113 Posts
Default

This website allows the input of up to 128 digits of the numbers to test for its primality, the format can be composed of a short formula as well -
https://www.numberempire.com/primenumbers.php

Last fiddled with by tuckerkao on 2021-04-27 at 23:00
tuckerkao is offline   Reply With Quote
Old 2021-04-27, 23:00   #6
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

1012410 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
This website allows the input of up to 128 digits of numbers to test for its primality,
And how do you generate a "huge list" from that? TheOP wants a huge list.
Uncwilly is offline   Reply With Quote
Old 2021-04-27, 23:00   #7
charybdis
 
charybdis's Avatar
 
Apr 2020

10438 Posts
Default

Feitsma's data suggests a rough 4.5-times increase in the number of 2-PSPs for each additional 5 powers of 2. So the file for 2^79 would be ~90 times the size of the file for 2^64: very large for a download but not hard to store. 2^128 would of course be totally impractical. The proportion of 2-PSPs below 2^64 that are strong pseudoprimes is about 27%, and this appears to increase as the numbers get bigger, so it's not a whole load easier to only store the SPSPs.

The larger problem would be finding all these PSPs. The search up to 2^64 took tens of CPU-years. Granted, that was in 2009, and GPUs would likely be useful as it appears that the most difficult part of the search involved doing a lot of trial-factoring of Mersenne numbers. Going up to 2^79 ought to be ~2^15 times harder than 2^64 (as we just have to trial-divide 15 bits higher, right?). Even if using modern GPUs gives a speedup of factor 2^15 relative to CPUs from 2009 - others can enlighten me on what a realistic number would be - this would still suggest tens of GPU-years for a search to 2^79.

And that's before we get on to this part, where the algorithm that Feitsma used would require over a terabyte of memory, so a slower method would likely be required.
charybdis is offline   Reply With Quote
Old 2021-04-27, 23:04   #8
tuckerkao
 
"Tucker Kao"
Jan 2020
Head Base M168202123

5·113 Posts
Default

I have a formula that can generate some 128 digits primes with each smaller prime, but I still haven't figured out a way to generate large amount of primes with very short period of time.

I only have around 200 of them.

The examples use 103374113, I can always substitute that number with another prime of the similar size, then try to adjust the 2^m and 3^n.
Attached Thumbnails
Click image for larger version

Name:	2^10 times 3^204 times 103374113 - 1.png
Views:	49
Size:	28.8 KB
ID:	24777   Click image for larger version

Name:	2^313 times 3^14 times 103374113 - 1.png
Views:	48
Size:	28.7 KB
ID:	24778  

Last fiddled with by tuckerkao on 2021-04-27 at 23:12
tuckerkao is offline   Reply With Quote
Old 2021-04-27, 23:11   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

23·17·29 Posts
Default

Quote:
Originally Posted by tuckerkao View Post
I have a formula that can generate some primes
8<--------------
The OP is interested in (strong) pseudoprimes not primes

Last fiddled with by paulunderwood on 2021-04-27 at 23:28
paulunderwood is online now   Reply With Quote
Old 2021-04-28, 04:07   #10
LarsNet
 
Mar 2021

22·11 Posts
Default

Quote:
Originally Posted by charybdis View Post
Feitsma's data suggests a rough 4.5-times increase in the number of 2-PSPs for each additional 5 powers of 2. So the file for 2^79 would be ~90 times the size of the file for 2^64: very large for a download but not hard to store. 2^128 would of course be totally impractical. The proportion of 2-PSPs below 2^64 that are strong pseudoprimes is about 27%, and this appears to increase as the numbers get bigger, so it's not a whole load easier to only store the SPSPs.

The larger problem would be finding all these PSPs. The search up to 2^64 took tens of CPU-years. Granted, that was in 2009, and GPUs would likely be useful as it appears that the most difficult part of the search involved doing a lot of trial-factoring of Mersenne numbers. Going up to 2^79 ought to be ~2^15 times harder than 2^64 (as we just have to trial-divide 15 bits higher, right?). Even if using modern GPUs gives a speedup of factor 2^15 relative to CPUs from 2009 - others can enlighten me on what a realistic number would be - this would still suggest tens of GPU-years for a search to 2^79.

And that's before we get on to this part, where the algorithm that Feitsma used would require over a terabyte of memory, so a slower method would likely be required.
Charybdis, this is awesome to me, i'm looking for these SPRP's, is there really no place to download them at? Obcoisouly i'm hoping for sizes larger than 64 but it really seems like if i want to do this that i'm going to have to buy the hardware and make them myself

Last fiddled with by LarsNet on 2021-04-28 at 04:10
LarsNet is offline   Reply With Quote
Old 2021-04-28, 04:20   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24×613 Posts
Default

What's the purpose of such a list? You can check the primality of any such small N extremely fast, by doing few divisions (very low TF) and then 1, or 2, or few PRP tests. That is because somebody else already did all the work for you, and such tests at this size take microseconds on a modern computer. That would be much faster than reading from a many-GB-sized file.
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where to find Prime Gap lists? jaydfox Prime Gap Searches 43 2021-07-19 17:56
Using CUDA to find better SPRP classifiers SPWorley Computer Science & Computational Number Theory 11 2012-11-21 20:13
Why arent there many softwares for finding Huge Primes blistervol Math 2 2012-08-20 17:26
An aliquot sequence with huge, huge, huge tracts of sand !!! garambois Aliquot Sequences 50 2012-01-19 18:25
Why Search for these Huge Primes? Unregistered Math 8 2005-04-27 00:55

All times are UTC. The time now is 06:55.


Tue Dec 7 06:55:44 UTC 2021 up 137 days, 1:24, 0 users, load averages: 1.30, 1.31, 1.27

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