Thread for posting tiny primes

[3.14159]

Originally Posted by axn

Sure. Just sieve till 1.17*10^17

Actually, it's removed 1200 candidates today. It would only take 10 or 11 days to get the desired one in 20.

[CRGreathouse]

Originally Posted by 3.14159

I use Miller-Rabin for those proofs. And, the app divides by any odd number that ends in 1, 3, 7, or 9, regardless of whether or not it is prime.

...?

You asked about getting lists of small primes. bsquared asked "How small"? You said 10-30 digits. I explained that this would be too many primes, even if I took the square root interpretation. Now you say that you're not using trial division for numbers of that size.

Great... but then we're right back to bsquared's question: How big of a list do you want?

[axn]

Originally Posted by 3.14159

Actually, it's removed 1200 candidates today. It would only take 10 or 11 days to get the desired one in 20.

Wow. You can sieve till 10^17 in 10 days! That means you must have 10000 cores sieving!!!

[axn]

Originally Posted by 3.14159

Actually, it's removed 1200 candidates today. It would only take 10 or 11 days to get the desired one in 20.

Various projected milestones

p=6.34e12: 1 in 15
p=4.52e13: 1 in 16
p=3.23e14: 1 in 17
p=2.30e15: 1 in 18
p=1.64e16: 1 in 19
p=1.17e17: 1 in 20

PS:- These numbers are specific for your current sieve.

[3.14159]

Originally Posted by CRGreathouse

You asked about getting lists of small primes. bsquared asked "How small"? You said 10-30 digits. I explained that this would be too many primes, even if I took the square root interpretation. Now you say that you're not using trial division for numbers of that size.

Okay: To clear things up:
1. 10 digits would only require division up to at most 316227.
2. Trial division - Up to about 18 digits.
3. Miller-Rabin - Up to about 30 digits.

Everything is cleared.

Originally Posted by axn

Wow. You can sieve till 10^17 in 10 days! That means you must have 10000 cores sieving!!!

HAHAHA, the most entertaining strawman I've ever heard.

Originally Posted by axn

PS:- These numbers are specific for your current sieve.

For my specific case?

[CRGreathouse]

Originally Posted by 3.14159

Okay: To clear things up:
1. 10 digits would only require division up to at most 316227.
2. Trial division - Up to about 18 digits.
3. Miller-Rabin - Up to about 30 digits.

Everything is cleared.

So you're asking about making a list of primes up to 10^9?

I just use Pari for that size; its algorithm is plenty good enough for me.

default(primelimit,10^9)

takes about 3.3 seconds on my machine.

You can also try Bernstein's primegen if you like.

[science_man_88]

Originally Posted by CRGreathouse

So you're asking about making a list of primes up to 10^9?

I just use Pari for that size; its algorithm is plenty good enough for me.

default(primelimit,10^9)

takes about 3.3 seconds on my machine.

You can also try Bernstein's primegen if you like.

think he's asking for 10^10 to 10^30 myself but I could be wrong.

though depending base it could be up to infinity base 2 about 10^9 base 10 10^10-9.99999999999999999999999999999*10^30 base 16 16^10-F.FFFFFFFFFFFFFFFFFFFFFFFFFFFFF16^30 ?

[3.14159]

Originally Posted by science_man_88

think he's asking for 10^10 to 10^30 myself but I could be wrong.

Trial division proofs only require that you divide up to the square root of that number. Only primes up to 10⁹ are needed to prove the primality of any 18-digit number. And about 10-30 iterations of Miller-Rabin (random-based) will guarantee the primality of any number up to 10³⁰.

[science_man_88]

Originally Posted by 3.14159

Trial division proofs only require that you divide up to the square root of that number. Only primes up to 10^9 are needed to prove the primality of any 18-digit number.

I was talking of the range you wanted to prove I wasn't aware about what he was talking about obviously. I know about the sqrt part.

[3.14159]

I tested the (ispseudoprime) function to the comparison against my methods, coded.

The results are: (For a 5628-digit PRP):
ispseudoprime: 36.083 seconds
isSPRP: 12.355 seconds

Nearly three times as fast.

[CRGreathouse]

Originally Posted by 3.14159

And about 10-30 iterations of Miller-Rabin (random-based) will guarantee the primality of any number up to 10³⁰.

For some meaning of "guarantee", at least.

Of course as I've said, if you're looking to get that kind of certainty you'd be better off with one Miller-Rabin and a few applications of some modern test, e.g. Damgård-Frandsen; for the time it would take you to do 10 M-Rs (1 M-
R + 3 D-F), you can get higher confidence than you'd get for 30 M-Rs: 1/142657607172096 vs. only 1/1073741824. They're better in the average case, too.

Originally Posted by 3.14159

I tested the (ispseudoprime) function to the comparison against my methods, coded.

The results are: (For a 5628-digit PRP):
ispseudoprime: 36.083 seconds
isSPRP: 12.355 seconds

Nearly three times as fast.

Sure, because ispseudoprime() is stronger. If you want just one test do

ispseudoprime(n, 1)

(though that will still do some trial division).