Generating Random Primes

davar55 · 2008-04-22, 17:58

This is a naive question:

Suppose I want to generate an N-digit prime.
I pick an M > N, generate a (random) M-digit number
(by choosing M random digits), and then try to factor M.

What is the probabilty that such a random M-digit number
has an N-digit prime factor (as a function of M and N)?

wblipp · 2008-04-22, 21:34

If M is a "lot" larger then N, then M doesn't matter and the probability at least one factor between 10^N-1 and 10^N is 1/N. Here's how I explained it in the ElevenSmooth FAQ

http://elevensmooth.com/MathFAQ.html#NoFactors

This heuristic breaks down when N gets close to M because you cannot have two 40 digit factors of a 50 digit number. For M < 2N you can use the Dickman function to find the probability the largest prime divisor exceeds N and N+1 digits.

http://mathworld.wolfram.com/DickmanFunction.html

for 2N < M < 3N the corresponding function for second largest divisor can be used. It's heuristically derived in this thread, with confirmation by Brent.

http://www.mersenneforum.org/showthread.php?t=2996

William

davar55 · 2010-12-27, 20:25

I never thought to ask myself the similar question for Mersenne Primes.

In particular, first, can anyone show why every digit
range 10^n to 10^(n+1)-1 must contain at least
one Mersenne Prime?

axn · 2010-12-27, 20:46

Quote:

Originally Posted by davar55

I never thought to ask myself the similar question for Mersenne Primes.

In particular, first, can anyone show why every digit
range 10^n to 10^(n+1)-1 must contain at least
one Mersenne Prime?

I would think that that is a false statement. It is quite conceivable that we would not have, for example, a 9-digit exponent yielding a mersenne prime.

davar55 · 2010-12-27, 21:04

Well, if we could PROVE a lower bound of 1.1 say, and a higher bound
of ten (10.000) for the ratio M_n+1/M_n, that
would imply the truth of my suggestion.

It would also prove that M.primes go on forever.

The trick is, prove a better lower bound and prove 10 is an upper bound.

Note I said "can anyone" not "I can here".

axn · 2010-12-27, 21:10

Quote:

Originally Posted by davar55

The trick is, prove a better lower bound and prove 10 is an upper bound.

For the purposes of the statement, proving an upper bound < 10 would be sufficient, no?

Quote:

Originally Posted by davar55

Note I said "can anyone" not "I can here".

Yes. I was betting on no one being able to prove it -- i.e. there is no fixed upper bound for Mn+1/Mn [actually this is a stronger statement than is probably needed]

davar55 · 2010-12-27, 21:17

Quote:

Originally Posted by axn

For the purposes of the statement, proving an upper bound < 10 would be sufficient, no?

Yes, indeed.

Quote:

Yes. I was betting on no one being able to prove it -- i.e. there is no fixed upper bound for Mn+1/Mn [actually this is a stronger statement than is probably needed]

And that's the crux. I say there is, and it's < 10.

But you don't have to take that on faith ...

CRGreathouse · 2010-12-27, 22:02

Quote:

Originally Posted by davar55

In particular, first, can anyone show why every digit
range 10^n to 10^(n+1)-1 must contain at least
one Mersenne Prime?

The expected number of Mersenne primes in such a range is $e^\gamma\lg10\approx5.9,$ so the chance of a given such interval having no Mersenne primes is about 0.27%. Any 257 disjoint intervals would have about a 50% chance of having at least one failing to have any Mersenne primes. So it's more likely than not (assuming present understanding) that by 10^265 the conjecture will fail, and by 10^2577 it's 99.9% likely.

davar55 · 2010-12-27, 23:51

And by 10^googolplex it's 99.99999999999999999999 % likely.

So what? Your basic assumption is random process, which is
incorrect. I make no such necessary assumption in my "guess".

CRGreathouse · 2010-12-28, 00:06

Quote:

Originally Posted by davar55

Your basic assumption is random process, which is
incorrect. I make no such necessary assumption in my "guess".

I trust you disbelieve the Prime Number Theorem, then? My statement could be made precise, with no use of randomness, just as the PNT can be. It's common to phrase the PNT in probabilistic terms because it's convenient and mathematicians know how to convert from the informal to the formal versions when needed.

Of course the statement itself is conjectural, which makes the informality all the more sensible. But if you can't figure out what a nonrandom version of the statement would look like, I can provide an epsilon-delta transformation for you. Of course the result will be every bit as conjectural as the original version.

davar55 · 2010-12-28, 00:20

I accept the PNT as proven, and I believe the RH is on the
verge of being proven. Randomness is an approximation
to the prime distribution, and can and must be removed from
any final proof of these two theorems.

I think my YJ-Conjecture will prove to be a lemma in the proof
of the infinitude of the Mersenne Primes.

Anti-crankness forbids any grander claims here.

2008-04-22, 17:58	#1
davar55 May 2004 New York City 5·7·11² Posts	Generating Random Primes This is a naive question: Suppose I want to generate an N-digit prime. I pick an M > N, generate a (random) M-digit number (by choosing M random digits), and then try to factor M. What is the probabilty that such a random M-digit number has an N-digit prime factor (as a function of M and N)?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Generating a uniform random n-bit semiprime	danaj	Programming	17	2017-09-15 16:41
random comments, random questions and thread titles made for Google	jasong	Lounge	46	2017-05-09 12:32
About random number (random seed) in Msieve	Greenk12	Factoring	1	2008-11-15 13:56
Generating 2005	Wacky	Puzzles	46	2005-06-05 22:19
Generating Small Primes	wblipp	Software	2	2005-01-05 13:29

2008-04-22, 21:34	#2
wblipp "William" May 2003 Near Grandkid 100101000111₂ Posts	If M is a "lot" larger then N, then M doesn't matter and the probability at least one factor between 10^N-1 and 10^N is 1/N. Here's how I explained it in the ElevenSmooth FAQ http://elevensmooth.com/MathFAQ.html#NoFactors This heuristic breaks down when N gets close to M because you cannot have two 40 digit factors of a 50 digit number. For M < 2N you can use the Dickman function to find the probability the largest prime divisor exceeds N and N+1 digits. http://mathworld.wolfram.com/DickmanFunction.html for 2N < M < 3N the corresponding function for second largest divisor can be used. It's heuristically derived in this thread, with confirmation by Brent. http://www.mersenneforum.org/showthread.php?t=2996 William

2010-12-27, 20:25	#3
davar55 May 2004 New York City 5×7×11² Posts	I never thought to ask myself the similar question for Mersenne Primes. In particular, first, can anyone show why every digit range 10^n to 10^(n+1)-1 must contain at least one Mersenne Prime?

2010-12-27, 21:04	#5
davar55 May 2004 New York City 1000010001011₂ Posts	Well, if we could PROVE a lower bound of 1.1 say, and a higher bound of ten (10.000) for the ratio M_n+1/M_n, that would imply the truth of my suggestion. It would also prove that M.primes go on forever. The trick is, prove a better lower bound and prove 10 is an upper bound. Note I said "can anyone" not "I can here".

2010-12-27, 23:51	#9
davar55 May 2004 New York City 5×7×11² Posts	And by 10^googolplex it's 99.99999999999999999999 % likely. So what? Your basic assumption is random process, which is incorrect. I make no such necessary assumption in my "guess".

2010-12-28, 00:20	#11
davar55 May 2004 New York City 5×7×11² Posts	I accept the PNT as proven, and I believe the RH is on the verge of being proven. Randomness is an approximation to the prime distribution, and can and must be removed from any final proof of these two theorems. I think my YJ-Conjecture will prove to be a lemma in the proof of the infinitude of the Mersenne Primes. Anti-crankness forbids any grander claims here.