Mersenne number factored (disbelievers are biting elbows)

[bloodIce]

What is considered to be a definitive proof for a number being prime? What is the golden standard (beyond TF)?

[Gordon]

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.

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....

[retina]

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.

[wblipp]

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.

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.

[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).

[Gordon]

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 ....

[Gordon]

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.

[Gordon]

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

[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.

[Mini-Geek]

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.

[alpertron]

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.