Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants


Leader Boards



11) Message boards : General discussion : List of prime numbers (Message 120281)
Posted 783 days ago by A_H_O_H — 1-st trillion natural numbers... — 2-nd trillions.

Miller-Rabin algorithm working fastly, and have so low errors percentage even with 10 rounds.
Can this be vectorized to using parralel GPU calculations?

I have JavaScript implementation of this algoritm, using BigIntegers
But 10 million primes in browser not convenient to generate.

I cann't see vectorized implementation of this algoritm, as portable EXE for windows, to be able for using GPU calculations...
.cu files from github need to be compiled,
python realization need to install python and Numba, pyCuda, and this not portable...
I see, this primesieve...
But there is "Sieve of Eratosthenes", and this need memory,
and cann't save prime numbers as result in the file - before full generate all...

Your project working with GPU calculations...

So.. Can your programmers, just for fun,
make Miller-Rabin algorithm vectorized - to be able GPU parallelism there (CUDA, OpenCL, etc),
like this portable EXE:

I see portable GPU programs, with cuda calculations,
like ccminer-x64.exe (portable GPU miner), vanitygen.exe (vanity bitcoin address generator),
scallion.exe (vanity onion-domain for TOR), etc...
All this programs are portable and working with GPU devices!..
12) Message boards : General discussion : List of prime numbers (Message 120250)
Posted 785 days ago by A_H_O_H

There is primes between 1-st trillion natural numbers...
Here is primes - up to 2 trillions of natural numbers.

Miller-Rabin algorithm working fastly, and have so low errors percentage even with 10 rounds.
Can this be vectorized to using parralel GPU calculations?
13) Message boards : General discussion : List of prime numbers (Message 120220)
Posted 787 days ago by A_H_O_H
You can Google for it.
For example, "first 1000 primes" shows many hits.
Among them is

This is a small list...

It depends on what you mean.
And if you type:
you get the answer:

But if I type

i got an error, because client-side JavaScript calculations there...

If you want "the first N prime numbers" or "all prime numbers up to X", which is indeed something used for sieving (judging that the post is in the Sieving subforum), there's little to no reason to store them explicitly as they are much quicker generated on the fly (sieve of Eratosthenes, sieve of Sundaram, etc.) than read from disk/network. Nevertheless, there are lists of those on the internet, such as this.

Last link seems good, but... Only 50 Millions?

I see here: using database with 30 trillions... This is good, and I see fast searching N-th prime...
But... There is no consecutive primes lists with this range...

And... How long will be working the fastest algorithm
to sieve prime numbers and get first trillion consecutive primes, for example?

I think will be better to search Nth-prime,
just by using a skip sectors with consecutive primes,
and without invest there many MIPS, FLOPS and time
to check primality for each number...

1 gram DNA can containing 700 Terabytes information, and maybe this space can be filled as consecutive primes.
So I just see, you don't have projects to calculate consecutive primes, and don't have any database, like this:

So I think this can be calculated, using molecular dinamycs and molecular computers, like the source of synergy for molecular nano-algorithmics...
14) Message boards : General discussion : List of prime numbers (Message 120192)
Posted 788 days ago by A_H_O_H
Hello. Do anyone have the lists of consecutive prime numbers?
15) Message boards : AP26 - AP27 Search : OMG! after 13 years of search, I found 3 primes! (Message 120191)
Posted 788 days ago by A_H_O_H
This is not a primes, this is Arithmetic progressions of the prime numbers.
16) Message boards : AP26 - AP27 Search : List for all APs (Message 117111)
Posted 927 days ago by A_H_O_H
I again want to ask admins to open access for AP's not for me, but
for any ALL another users.

Yes, some numbers are more easily factored than others and must be avoided for cryptography.

But see the range and exponent of this!.. And the speed of factorization!..

Acceptable RSA modulus strength these days is around 10^616.

Their length lower like MegaPrimes, here...
But this is so big numbers...
10^x = 2^y; y = (x (log(2) + log(5)))/log(2) = 2046.31

There is a point on the number line and this have value 2046.31.
That means 2046.31 bits, and bit length of key ≈ 2048 bits.
I don't think the prime numbers must to be so long.

For example, I can see here
a prime numbers over 1 trillion, in the custom range.
There I can collect lists of 1000 primes, without any lags.

It doesn't take long to try them all.

And if you can download it, then clearly someone else already has this list.

I don't think that every number really divided for all prime numbers there, which are writed in the row sequence list.
Wolfram's response so quickly, but this tooks long time
to try divide this for all 35 billion primes from 0 to 1 trillion. π(1T) this is prime pi-function...

Multiplying a pair of numbers from a set of one trillion numbers results in a keyspace of size 10^24.

Compound numbers are factorized there so easy in this range, as you can see in my previous example.
I did used in wolfram two prime numbers from progression, with exponential note n×10^17 for each prime, and compound numbers up to N×10^34
This is more than one and two trillion!

It's not the size of your key that matters, rather it's the size of your keyspace.

Do you have any list with prime numbers - in the range 2^256 - 2^1024?
100?.. 500?.. 1000?..

So come up with a couple of original large primes and keep them secret. Now we're talking.

But the better slowly way, to collect big prime numbers,
I can see in this algorithm...
1. Generate big odd number.
2. Copy and paste to wolframalpha.
3. See factorization, and using largest prime.
For example, here (≈5.52×10^85)
I can see prime factorization:
and number 678364058742890703359868245487209221658124995744414718166011817821443126850887 seems,
like a prime number
This can be not prime, but "maybe prime".

It's also problematic to use very large primes from a list of known very large primes.
These number in the thousands.

Yeap. And if any number is not prime, can be lags and errors.

17) Message boards : AP26 - AP27 Search : List for all APs (Message 117049)
Posted 928 days ago by A_H_O_H

Try to read the first post by JimB in this thread (Message 116926) again! They removed this nice feature because you had a script that mis-used it. You harvested these pages too aggressively.

When you make a script that "crawls" a lot of pages, be sure to have long pauses between each page request. Otherwise you will put too much load on the server.


I'd already read this.
I really did not set a delay when opening many windows,
but it would be wiser to set a timeout on the server,
instead of disabling it FOR ALL USERS.
To do this, admins can using Captcha, ConnectTimeout options for GET queries, and server timeout for HttpRequest at last
(with response, like HTTP 408 Request Timeout,
or message "try to update page lager, after 5... 4... 3... 2... 1... seconds.")

And after this all, I would like to ask admins for unlock AP's for another users.
I don't have any interest for using AP's in PRNG,
and any scripts without timeouts.
I will not try to get AP's or another data - so inconvenient way,
if your server so such an unstable.

And now, I will go to download - 1 trillion prime numbers, in a row sequence. :D

Best regards.
18) Message boards : AP26 - AP27 Search : List for all APs (Message 117040)
Posted 929 days ago by A_H_O_H
The APs that we produce are by definition lists of primes.

I don't see any AP's now in any another user statistics.
Moreover, I see admins did delete AP link from another users.
Now, I can see only list of primes there. Hm...
Why access to AP's was been closed? And how long it will be closed?
Can admins do publishing this again? Or this is any top secret info?

APs are NOT lists of consecutive primes. In general there are many primes between adjacent entries of an AP. What makes an AP interesting is that there are only primes in them and they occur a fixed distance apart.

Yeap, that is what I wanted to say.
The numbers from the AP are very similar by bit length
and it looks like a uniform distribution of prime with fixed common difference for each progression.

For example: 5, 11, 17, 23, 29 forms a very small AP, each member separated from the next by a distance of 6. Note that there are primes in the span between the beginning and end of the AP that are not in the list: 7, 13, 19. It is coincidental that these missing primes also form a small AP having a distance of 6, but you can say that the entire set of primes between 5 and 29 (inclusive) are covered by this pair of APs.

Nice progression, but very shortly.
In the standard note this AP can be writed, like:
5+1/37182145*23#*n for n=0..5 :-)
Is there any pattern or formula to easy find progressions in the primes list, that is wrote in a row sequence?

True. Sometimes the acronym CPAP is used instead of AP when the additional requirement that there are no primes in between, is included.

Yeah, I know, but in CPAP, there is so large primes!
I don't have any sence to using this...
On this site, there is specified a number of their digits!
And there is so difficult to operate with them.

But... If I will do multiplication two primes from AP's
I can easy turn this primes go back!..
For example two primes from my previous AP:
285751091273819999 (for n = 12) × 333388900884401189 (for n = 19)
= 95266242246297053145225031687578811
So I can get a large "composite number".
9.5266242246297053145225031687578811 × 10^34
Hm... But... I'd look at THIS:
And I can see there a field, Prime factorization:

So an easy way to factorize compound numbers with this length
makes it useless to use these primes for encryption, like in RSA or Diffie-Hellman algorithms.

Prior to that, I was betting that most cryptosystems are crypto-resistant
as long as the PRNG have a cryptographically strength.
And now I did loss any sense to using AP's from PrimeGrid to seed PRNG for encrypting.
Maybe there is any sense to using large Mersenne Primes or another big primes, but random entropy is lossing, if I will do selecting one by one from when number of primes in list is limited (50 Mersenne primes only, for example).

Since you have a list of the first 30 billion or so prime numbers, you are free to search for subsets of primes in any manner you like, not necessarily arithmetic progressions.

Hm... People, any one know, how can I compress prime numbers
in the list to don't record all digits of this primes?
Is there any formula?
I see here short notes for big primes, but there is specially primary formulas by type for do brute force calculating this primes in BOINC...
Maybe, I can using formulas, like 3×10^10+(1, 13, 53, 77, 89, etc...)

Also, I have one another idea for using my large archive of prime numbers.
For example:
1. If I have an array with the primes sequence [2, 3, 5, 7, 11, 13, 17]
2. Then I can check maximum numbers from 0 to 17^2 = 289 and lowest odd number 287 can be divided by one of this primes (7×41).
3. If number can not be divided by this primes without remainder - this is "maybe prime number" and I can add this to the array.
4. So if I have 1.4 billion prime numbers in a row sequence,
with maximum value of last prime (30,000,000,001)
then I can calculate all primes in the square of this range (30000000001)^2 ~ 9 × 10^20 then again square (8.1 × 10^41), then again, and again... :-D
19) Message boards : AP26 - AP27 Search : List for all APs (Message 116975)
Posted 930 days ago by A_H_O_H

If you are trying to devise a method of testing unknown numbers for primality, APs are not going to give you this information. You need to run primality tests.

I don't want to using any primality tests and algorithms,
and I want to get random REAL prime number.
I can test is this prime at anytime,
by checking Prime Factorization on the site

It might be that you are trying to create a highly compressed list of known prime numbers, and you are looking to use APs as a method of condensing the information.


Since you have a list of the first 30 billion or so prime numbers, you are free to search for subsets of primes in any manner you like, not necessarily arithmetic progressions.

How to do this without save all primes?
I do not see any pattern in the distribution of prime numbers, which can be expressed by some formula, which would allow unambiguously to generate the present prime number depending on any parameter.
Maybe this is Pi-function (but there is using a limit).
And for me, arithmetic progressions from prime numbers is the shortest record, able to encode a whole series of numbers.

Invent a progression, label each prime in your subset that occurs in the progression at different starting positions, and select the subset of progressions that covers the most prime numbers in the least number of progressions. You might even get a more compressed set when you let some of the progressions overlap, where some prime numbers are represented more than once in your set.

If I will do assign additional addresses for prime numbers and if I will do algorithm to selection prime by addresses,
then the space of information in the list will growing.
I need to save an addresses, then.

It may also be that you are trying to develop a method of selecting a random prime number from the list of all prime numbers. Good luck.

Yes. To do generation prime my script do using two parameters from PRNG (random index and random n).
Index is sets the progression in AP's array,
and after select this - script using n
and return prime number from AP.

For example, I have an array:
//indexes is [0, 1, 2, 3, 4] var progressions_array = ["327782912156715629+56579336*23#*n for n=0..20", //index 0 "282945022318458547+30504792*23#*n for n=0..20", //1 "204086274798537959+30504791*23#*n for n=0..20", //2 "366707529067925443+56138164*23#*n for n=0..19", //3 "298224021515636179+56089556*23#*n for n=0..19" //4 ]; //(3*AP21)+(2*AP20) = 103 prime numbers in five string.

1. generation random index. index = 2;
2. generation n. n = 14;
3. Calculate 23# (23# is Primorial from 23 = 2*3*5*7*11*13*17*19*23 = 223092870 - multiplication all primes before 23)
4. Select progression by index 2:
204086274798537959+30504791*23#*n for n=0..20 204086274798537959+30504791*223092870*0=204086274798537959 204086274798537959+30504791*223092870*1=210891676171478129 204086274798537959+30504791*223092870*2=217697077544418299 204086274798537959+30504791*223092870*3=224502478917358469 204086274798537959+30504791*223092870*4=231307880290298639 204086274798537959+30504791*223092870*5=238113281663238809 204086274798537959+30504791*223092870*6=244918683036178979 204086274798537959+30504791*223092870*7=251724084409119149 204086274798537959+30504791*223092870*8=258529485782059319 204086274798537959+30504791*223092870*9=265334887154999489 204086274798537959+30504791*223092870*10=272140288527939659 204086274798537959+30504791*223092870*11=278945689900879829 204086274798537959+30504791*223092870*12=285751091273819999 204086274798537959+30504791*223092870*13=292556492646760169 204086274798537959+30504791*223092870*14=299361894019700339 204086274798537959+30504791*223092870*15=306167295392640509 204086274798537959+30504791*223092870*16=312972696765580679 204086274798537959+30504791*223092870*17=319778098138520849 204086274798537959+30504791*223092870*18=326583499511461019 204086274798537959+30504791*223092870*19=333388900884401189 204086274798537959+30504791*223092870*20=340194302257341359

4. Calculate prime number for n = 14:

5. Return prime 299361894019700339 with link to check this:
As you can see this is a real prime number

Prime factorization:
299361894019700339 is a prime number.

And this prime number is 2.99361894019700339×10^17
This is more then 30 billion, like a maximum prime number in the list of my archive.

An uncompressed list is the only way of selecting with certainty an arbitrary Nth prime number with uniform distribution from the list.

In the range of n in arithmetic progression from (0 to progression_length), is also obtained an uniform distribution.

To check the number for simplicity, I would have to try to divide the candidates into a prime number - on the all the other prime numbers that stand before it. And this would require storing all this list of primes.
But AP's I can write by only one string, in array.
20) Message boards : AP26 - AP27 Search : List for all APs (Message 116972)
Posted 930 days ago by A_H_O_H
Ok, so is there any reason you're using AP20s? You could use the AP23s at the link I posted. There aren't as many of them, but it should work unless you really need two million primes. This would substantially reduce the server load as you only need to load one page.

There is no any reason to using exactly these AP20s, just this is the most common type of AP's in the list.

Also, I have already included all these progressions in the generator. And as you can see, I did post this link - in Original Post.
Now, on this page, there is 2440 unique arithmetic progressions
("1923 * AP23" + "447 * AP24" + "62 * AP25" + "8 * AP26").
1923 + 447 + 62 + 8 = 2440 AP's
and let's calculating primes there:
1923 * 23 = 44229 primes +
447 * 24 = 10728 primes +
62 * 25 = 1550 primes +
8 * 26 = 208 prime numbers.
Total 56715 prime numbers. And not very good range.

Also, I have on my hard disk - an archive, with 1,302,400,000 prime numbers, they are written in a row, from 2 to 30057700549.
This archive takes 1,401,613,717 bytes in a compressed state (7z, LZMA compressing),
and if I'll unzip this archive, it will expand on 16,418,727,846 bytes ~ 16.4 GB.
16418727846 bytes / 1302400000 primes = 12.60 bytes for each prime number - average space.
12.60 * 2000000 ~ 25213034 bytes ~ 25 megabytes.
At me, with progressions - it has appeared 5 megabytes space.
So I have in 5 times less space and high range, without any compression.

I do not want to do any load on the server any more, even if you open access to these APs. I can use a timeout to open the pages, but it's very long deal and tedious.

I think, would be better if the all progressions were public and quickly organized updates
on the site, or in the public sequences - like OEIS.

Next 10 posts
[Return to PrimeGrid main page]
Copyright © 2005 - 2020 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.88, 0.97, 0.78
Generated 25 Oct 2020 | 11:34:18 UTC