Extrapolation: How long until the minimum megaprime?

CRGreathouse · 2011-04-15, 03:40

No doubt many are thinking of M6972593, but I mean the smallest prime with one million digits. How difficult would this be to find?

The straightforward approach would be to sieve a small number (few million) candidates to a high enough level (at least 10^14?) to remove most of the composites, and then ~10,000 pseudoprimality tests (requiring effort similar to a standard LL test -- smaller numbers but not as optimized, presumably). This would be too hard to be practical today without a distributed effort, it seems, but when might it be reasonable?

I would also be interested in guesses for how much longer until this number could be *proved* to be the first such prime. Unlike finding it, proving its primality might not be possible in my lifetime, barring breakthroughs in algorithms (not particularly unlikely, I suppose).

axn · 2011-04-15, 05:45

Quote:

Originally Posted by CRGreathouse

The straightforward approach would be to sieve a small number (few million) candidates to a high enough level (at least 10^14?) to remove most of the composites, and then ~10,000 pseudoprimality tests (requiring effort similar to a standard LL test -- smaller numbers but not as optimized, presumably).

ln(10^999999) / (e^gamma ln(10^14)) ~= 40000 expected prp tests.

xilman · 2011-04-15, 09:01

Quote:

Originally Posted by CRGreathouse

Unlike finding it, proving its primality might not be possible in my lifetime, barring breakthroughs in algorithms (not particularly unlikely, I suppose).

It might be possible, but very very unlikely. Enough factors may be found of N \pm 1, and enough of their factors, and so on...

It's not a project which I'd be very interested in, TBH.

Much more interesting, IMO, is to create a proven prime of some ridiculously large size and high Kolmogorov complexity by driving the N \pm 1 tests in reverse.

Paul

science_man_88 · 2011-04-15, 12:06

Quote:

Originally Posted by CRGreathouse

No doubt many are thinking of M6972593, but I mean the smallest prime with one million digits. How difficult would this be to find?

The straightforward approach would be to sieve a small number (few million) candidates to a high enough level (at least 10^14?) to remove most of the composites, and then ~10,000 pseudoprimality tests (requiring effort similar to a standard LL test -- smaller numbers but not as optimized, presumably). This would be too hard to be practical today without a distributed effort, it seems, but when might it be reasonable?

I would also be interested in guesses for how much longer until this number could be *proved* to be the first such prime. Unlike finding it, proving its primality might not be possible in my lifetime, barring breakthroughs in algorithms (not particularly unlikely, I suppose).

as 10^1000000 is 4 mod 6 the first possible prime is 10^1000000 + 1 and if within the first 100 after that it must follow:

10^1000000 + n for $n \in \{{1,5,7,.......}\}<br />$

xilman · 2011-04-15, 12:13

Quote:

Originally Posted by science_man_88

as 10^1000000 is 4 mod 6 the first possible prime is 10^1000000 + 1 and if within the first 100 after that it must follow:

10^1000000 + n for $n \in \{{1,5,7,.......}\}<br />$

It's easy to show that 10^1000000 has 1000001 digits and so is much larger than the first megaprime.

I suggest that you try again.

Paul

P.S. 10^999999+1 is composite. Prove this.

science_man_88 · 2011-04-15, 12:18

Quote:

Originally Posted by xilman

It's easy to show that 10^1000000 has 1000001 digits and so is much larger than the first megaprime.

I suggest that you try again.

Paul

P.S. 10^999999+1 is composite. Prove this.

I forget some times at least I'm trying. lol

CRGreathouse · 2011-04-15, 15:35

axn: In my defense, I intended "tens (not hundreds) of thousands of tests".

Quote:

Originally Posted by xilman

It might be possible, but very very unlikely. Enough factors may be found of N \pm 1, and enough of their factors, and so on...

It's not a project which I'd be very interested in, TBH.

I'm not asking how to do it today, but rather how long until it's easy enough that someone says "what the heck, I'll calculate that". Do you think ten years? Twenty?

petrw1 · 2011-04-15, 16:09

We can narrow it down to somewhere between:

http://primes.utm.edu/primes/lists/all.txt

Code:

rank  description                    digits who  year comment
35  59*2^3408416-1                  1026038 L426 2010 
36  3139*2^3321905-1                 999997 L185 2008

science_man_88 · 2011-04-15, 16:12

Quote:

Originally Posted by xilman

It's easy to show that 10^1000000 has 1000001 digits and so is much larger than the first megaprime.

I suggest that you try again.

Paul

P.S. 10^999999+1 is composite. Prove this.

I can't I know it's 5 mod 6 and 41 mod 120 but that's all I've worked out. I can't remember what else to work out.

science_man_88 · 2011-04-15, 16:16

oh and it's 1 mod 4 by my math. which brings me back ( I believe the rule is 4x+3 as well as 6n+5, if so it can't be prime).

Brian-E · 2011-04-15, 16:29

Science Man, is there anything you notice about the numbers $10^1+1$ , $10^3+1$ , $10^5+1$ , ... , $10^{(2n+1)}+1$ , ... and can you prove the property for all n?

2011-04-15, 03:40	#1
CRGreathouse Aug 2006 3·1,993 Posts	Extrapolation: How long until the minimum megaprime? No doubt many are thinking of M6972593, but I mean the smallest prime with one million digits. How difficult would this be to find? The straightforward approach would be to sieve a small number (few million) candidates to a high enough level (at least 10^14?) to remove most of the composites, and then ~10,000 pseudoprimality tests (requiring effort similar to a standard LL test -- smaller numbers but not as optimized, presumably). This would be too hard to be practical today without a distributed effort, it seems, but when might it be reasonable? I would also be interested in guesses for how much longer until this number could be proved to be the first such prime. Unlike finding it, proving its primality might not be possible in my lifetime, barring breakthroughs in algorithms (not particularly unlikely, I suppose).

2011-04-15, 16:09	#8
petrw1 1976 Toyota Corona years forever! "Wayne" Nov 2006 Saskatchewan, Canada 1010000111100₂ Posts	We can narrow it down to somewhere between: http://primes.utm.edu/primes/lists/all.txt Code: rank description digits who year comment 35 592^3408416-1 1026038 L426 2010 36 31392^3321905-1 999997 L185 2008

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sci-Tech extrapolation into Sci-Fi.	jwaltos	Reading	0	2017-10-31 19:00
Estimating minimum relations	bchaffin	Factoring	24	2012-03-24 18:37
Using long long's in Mingw with 32-bit Windows XP	grandpascorpion	Programming	7	2009-10-04 12:13
I think it's gonna be a long, long time	panic	Hardware	9	2009-09-11 05:11
Msieve NFS minimum size	10metreh	Msieve	35	2009-04-02 19:14

2011-04-15, 16:16	#10
science_man_88 "Forget I exist" Jul 2009 Dumbassville 20C0₁₆ Posts	oh and it's 1 mod 4 by my math. which brings me back ( I believe the rule is 4x+3 as well as 6n+5, if so it can't be prime).

2011-04-15, 16:29	#11
Brian-E "Brian" Jul 2007 The Netherlands 2·3·5·109 Posts	Science Man, is there anything you notice about the numbers $10^1+1$ , $10^3+1$ , $10^5+1$ , ... , $10^{(2n+1)}+1$ , ... and can you prove the property for all n?