mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Where can i find huge lists of primes up to as close to 2^128 as possible of SPRP's (https://www.mersenneforum.org/showthread.php?t=26747)

 LarsNet 2021-04-27 19:28

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 [url]https://miller-rabin.appspot.com/[/url] 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.

 paulunderwood 2021-04-27 20:49

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.

 LarsNet 2021-04-27 22:15

[QUOTE=paulunderwood;577027]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.[/QUOTE]

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
[/CODE]

 VBCurtis 2021-04-27 22:57

[QUOTE=LarsNet;577037] 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
[/CODE][/QUOTE]

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.

 tuckerkao 2021-04-27 22:57

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 -

 Uncwilly 2021-04-27 23:00

[QUOTE=tuckerkao;577042]This website allows the input of up to 128 digits of numbers to test for its primality,[/QUOTE]And how do you generate a "huge list" from that? TheOP wants a huge list.

 charybdis 2021-04-27 23:00

[URL="http://www.janfeitsma.nl/math/psp2/statistics"]Feitsma's data[/URL] 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 [URL="http://www.janfeitsma.nl/math/psp2/not-sqrt-smooth"]tens of CPU-years[/URL]. 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 [URL="http://www.janfeitsma.nl/math/psp2/sqrt-smooth"]this part[/URL], where the algorithm that Feitsma used would require over a terabyte of memory, so a slower method would likely be required.

 tuckerkao 2021-04-27 23:04

2 Attachment(s)
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.

 paulunderwood 2021-04-27 23:11

[QUOTE=tuckerkao;577045]I have a formula that can generate some primes
8<--------------
[/QUOTE]

The OP is interested in (strong) pseudoprimes not primes :whistle:

 LarsNet 2021-04-28 04:07

[QUOTE=charybdis;577044][URL="http://www.janfeitsma.nl/math/psp2/statistics"]Feitsma's data[/URL] 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 [URL="http://www.janfeitsma.nl/math/psp2/not-sqrt-smooth"]tens of CPU-years[/URL]. 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 [URL="http://www.janfeitsma.nl/math/psp2/sqrt-smooth"]this part[/URL], where the algorithm that Feitsma used would require over a terabyte of memory, so a slower method would likely be required.[/QUOTE]

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

 LaurV 2021-04-28 04:20

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 [URL="https://primes.utm.edu/prove/prove2_3.html"]few PRP tests[/URL]. 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.

 charybdis 2021-04-28 13:38

[QUOTE=LarsNet;577080]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[/QUOTE]

As far as I know no-one has systematically searched for 2-PSPs beyond 2^64. If you want to get to 2^79, you'll probably need lots of fast GPUs, lots of CPUs, and some very efficient code. But as LaurV says, what's the point? The only use I can see would be to extend the search for BPSW pseudoprimes, and this is really only of theoretical interest: even if there is a BPSW pseudoprime below 2^79, it's not like anyone's ever going to come across it by accident. And if we really want to prove primality, APR-CL and ECPP are very quick at this size.

 paulunderwood 2021-04-28 14:35

Has anyone done a speed comparison test for a batch of odd numbers < 2^64 between sprp

[QUOTE]2, 325, 9375, 28178, 450775, 9780504, 1795265022[/QUOTE]

and BPSW?[*]

[*] 2-sprp plus strong 2 selfridge strong Lucas chain.

 LarsNet 2021-04-28 18:44

[QUOTE=LaurV;577082]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 [URL="https://primes.utm.edu/prove/prove2_3.html"]few PRP tests[/URL]. 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.[/QUOTE]

Mostly it's to test against some prime number testings that i've been working on my own. None of them are better than BPSW, but i found what i think is as good a Miller Rabin test as the deterministic test at the same length (sometimes better) than what they have at wikipedia, but i have some other good ideas and it's mostly an intellectual exercise for me and having these list would help me test what i have come up with, mostly so i don't have to bug those here with my ideas and can work on them on my personal time, does that make sense? :-) I'm looking at the link you posted right now, it looks promising.

I feel like my other post ended up being a waste of time for me and others here's time, and if i have I had these bigger number lists to test against then i could have avoided making the post in the first place since i would have had better numbers to test against and came to the same conclusion ( that my test wasn't better) before hand. That's all really, i just have stuff i'm working on and could use a few gig's worth of numbers to test against. I'm really not opposed to spending money on some equipment that would help me generate these numbers, i just don't know what that equipment would be, right now i just have a laptop which isn't enough to generate the number sizes i'm looking for

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