mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Data

Reply
 
Thread Tools
Old 2014-06-17, 14:14   #45
bloodIce
 
bloodIce's Avatar
 
Feb 2010
Sweden

173 Posts
Default

What is considered to be a definitive proof for a number being prime? What is the golden standard (beyond TF)?
bloodIce is offline   Reply With Quote
Old 2014-06-17, 14:26   #46
Gordon
 
Gordon's Avatar
 
Nov 2008

22·53 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
We don't have to prove that it is incomplete. Anyone claiming
that it is complete must do so.

You are really having trouble with this.

The SET of primes is a strict SUBSET of the set of probable primes.
A prime is a probable prime. The converse is not true in general.

You can not assert that a number is the product of primes
when all we know is that it is the product of some primes and an
integer that may or may not be prime.

Asserting that the number is a product of primes is a CONJECTURE.

We have good evidence that the conjecture is correct, but we do not
know it to be true.
Which brings us neatly back to where I came in, the OP has made an assertion that he can't prove to be true, and until he can it is assumed to be false.

Please, no more misleading claims, you just make yourself look, well....

It's very simple to make untestable claims, like this for instance

I claim that M849153401 has a factor somewhere between 200 & 300 bits. Want to prove me wrong then to verify whether it does or doesn't you'll only need

485,895,372,555,841,087,175,428,001,228,835,474,093,331,694,585,558,681,189,783,437,312,000 ghz days.

In other words my claim is safe for billions of times the known life of the universe.

See, making ridiculous claims is easy, and that's only a 300 bit test never mind 173 thousand digits.

and to give you a head start I've TF'ed it to 67 bits....

Last fiddled with by Gordon on 2014-06-17 at 14:31
Gordon is offline   Reply With Quote
Old 2014-06-17, 14:37   #47
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2×7×409 Posts
Default

Quote:
Originally Posted by Gordon View Post
See, making ridiculous claims is easy ...
I don't agree that claiming a PRP as a complete factorisation is a ridiculous claim. Actually the confidence level for PRPs is extremely high. Indeed it is not definitive proof, but saying it is ridiculous is not right either.
retina is offline   Reply With Quote
Old 2014-06-17, 15:10   #48
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2·32·131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
We don't have to prove that it is incomplete. Anyone claiming that it is complete must do so.

You are really having trouble with this.
Yes, I'm really having trouble with this. My problem is that I am not at all concerned with anyone claiming that it is complete. My problem is that I am concerned with someone claiming that it is incomplete. And I think that you have claimed that the factorization is incomplete.

I'll lay out my logic is excruciating detail. I'm thinking we our disagreement is in step 3 or 4.

======
1. We have a factorization.
(We agree)
2. We don't know if it is a factorization into primes
(We agree)
3. If it IS a factorization into primes, then the number is completely factored.
Your definition of completely factored
A possible source of disagreement is whether or not a factorization into primes that is not proven to be a factorization into primes is a complete factorization. My understanding that is IS a complete factorization, but it is not KNOWN to be a complete factorization
4. You have asserted that is NOT completely factored
Your post, quoted by me
This is also a possible point of disagreement. You may think that that you have merely failed to assert the factorization is complete. I think you have made the much stonger assertion that the factorization in known to be incomplete.
5. Because of #3, your assertion in #4 is equivalent to asserting the known factorization is NOT a factorization into primes.
Here is where the disagreement gets visible
But it makes no sense for the disagreement to be in this step - it's a simple consequence of 3 and 4. So I'm thinking the disagreement must have been in 3 or 4.
wblipp is offline   Reply With Quote
Old 2014-06-17, 15:48   #49
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

601 Posts
Default

With the possibility of quantum computers coming in the near future, Gordon's claim probably won't be safe for very long. Also the large PRP you're talking about may be proven in our lifetimes (I hope so).
Stargate38 is offline   Reply With Quote
Old 2014-06-17, 16:03   #50
Gordon
 
Gordon's Avatar
 
Nov 2008

22·53 Posts
Default

Quote:
Originally Posted by retina View Post
I don't agree that claiming a PRP as a complete factorisation is a ridiculous claim. Actually the confidence level for PRPs is extremely high. Indeed it is not definitive proof, but saying it is ridiculous is not right either.
Neither is the OP's claim of completely factored ....
Gordon is offline   Reply With Quote
Old 2014-06-17, 16:06   #51
Gordon
 
Gordon's Avatar
 
Nov 2008

50010 Posts
Default

Quote:
Originally Posted by wblipp View Post

[snip]

My understanding that is IS a complete factorization, but it is not KNOWN to be a complete factorization

[snip]
Bingo!! Give the man a prize, somebody else also gets it. The OP's claim therefore doesn't stand up.
Gordon is offline   Reply With Quote
Old 2014-06-17, 16:26   #52
Gordon
 
Gordon's Avatar
 
Nov 2008

22·53 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
With the possibility of quantum computers coming in the near future, Gordon's claim probably won't be safe for very long. Also the large PRP you're talking about may be proven in our lifetimes (I hope so).
1. Quantum computing is a lovely idea, how many bits will we need?
RSA says a 2048 bit number is 617 decimal digits
The OP's PRP has 173,528 digits, or 281x as many
Think it will be a while afore we get 575,000 bit QC's
2. I think the chances of factorising a 575,000 bit number in the next - insert any ludicrously large number you like here - years, centuries or aeons are zero.

3. The current world record for quantum factorisation is 143
Gordon is offline   Reply With Quote
Old 2014-06-17, 16:36   #53
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

33·72 Posts
Default

According to http://primes.utm.edu/top20/page.php?id=27 , the largest prime verified by ECPP has 26643 digits, so except if you plan to die in the next 5-10 years, you will be able to check whether the 173528-digit number is prime or not in your lifetime.

In the other hand, verifying Gordon's claim is far more difficult.
alpertron is offline   Reply With Quote
Old 2014-06-17, 16:49   #54
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts
Default

Quote:
Originally Posted by alpertron View Post
According to http://primes.utm.edu/top20/page.php?id=27 , the largest prime verified by ECPP has 26643 digits, so except if you plan to die in the next 5-10 years, you will be able to check whether the 173528-digit number is prime or not in your lifetime.

In the other hand, verifying Gordon's claim is far more difficult.
From what I can tell, ECPP is about O((log n)^4), which means that a 173528-digit number should be about (173528^4 / 26643^4 ~=) 1800 times harder than a 26643-digit number. If we take the naive assumptions that Moore's law holds, with an 18-month doubling period, that we will put the same amount of effort into this proof as the current 2011 record, and that no better algorithm comes along for this purpose, then we should prove it around...
log_2(1800) * (18 months) = 5921 days = 16.2 years
April 3, 2011 + 5921 days = June 2027, so 13 years away.

Lots of inaccuracies here, obviously. Still, 5-10 years sound overly optimistic to me, especially when you consider that there's not much mathematical need to prove Mersenne cofactors (only 1 of the top 20 current ECPP proofs is for a Mersenne cofactor). If there's some interest in it, 13-20 years sounds more reasonable to me. 25+ if there's little interest in proving cofactors like this.

Last fiddled with by Mini-Geek on 2014-06-17 at 16:56
Mini-Geek is offline   Reply With Quote
Old 2014-06-17, 16:55   #55
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001010112 Posts
Default

Well, I was not very far from your timing. Now, you can estimate when we will be able to prove Gordon's claim, so we will need to perform TF until 2^300, as it is possible that there are no factors in the 200 bit to 300 bit range.

It is clear that it will not be in our lifetimes, except if there were some "revolution" in factoring algorithms.

PS: In that range, ECM would be used, but at this moment it is not possible to find 300-bit prime factors using that algorithm, and it would be worse still when you are trying to factor a number with several hundred million digits. And using this algorithm we are not sure that a number below 300 bits is skipped.

Last fiddled with by alpertron on 2014-06-17 at 17:08
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Smallest exponent for mersenne not-factored preda PrimeNet 10 2018-11-04 00:47
Largest Mersenne Number Fully Factored? c10ck3r Data 49 2017-12-10 19:39
Possibility of a Fully-Factored Number Trejack FactorDB 7 2016-05-14 05:38
Estimating the number of primes in a partially-factored number CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16

All times are UTC. The time now is 18:21.

Sun Sep 20 18:21:11 UTC 2020 up 10 days, 15:32, 0 users, load averages: 1.63, 1.59, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.