mersenneforum.org > Data Mersenne number factored (disbelievers are biting elbows)
 Register FAQ Search Today's Posts Mark Forums Read

 2014-06-17, 14:14 #45 bloodIce     Feb 2010 Sweden 173 Posts What is considered to be a definitive proof for a number being prime? What is the golden standard (beyond TF)?
2014-06-17, 14:26   #46
Gordon

Nov 2008

22·53 Posts

Quote:
 Originally Posted by R.D. Silverman 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.

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

2014-06-17, 14:37   #47
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2×7×409 Posts

Quote:
 Originally Posted by Gordon 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.

2014-06-17, 15:10   #48
wblipp

"William"
May 2003
New Haven

2·32·131 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
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
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.

 2014-06-17, 15:48 #49 Stargate38     "Daniel Jackson" May 2011 14285714285714285714 601 Posts 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).
2014-06-17, 16:03   #50
Gordon

Nov 2008

22·53 Posts

Quote:
 Originally Posted by retina 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 ....

2014-06-17, 16:06   #51
Gordon

Nov 2008

50010 Posts

Quote:
 Originally Posted by wblipp [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.

2014-06-17, 16:26   #52
Gordon

Nov 2008

22·53 Posts

Quote:
 Originally Posted by Stargate38 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

 2014-06-17, 16:36 #53 alpertron     Aug 2002 Buenos Aires, Argentina 33·72 Posts 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.
2014-06-17, 16:49   #54
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

426710 Posts

Quote:
 Originally Posted by alpertron 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

 2014-06-17, 16:55 #55 alpertron     Aug 2002 Buenos Aires, Argentina 101001010112 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post preda PrimeNet 10 2018-11-04 00:47 c10ck3r Data 49 2017-12-10 19:39 Trejack FactorDB 7 2016-05-14 05:38 CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46 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