mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Data (https://www.mersenneforum.org/forumdisplay.php?f=21)
-   -   Mersenne number factored (disbelievers are biting elbows) (https://www.mersenneforum.org/showthread.php?t=19407)

alpertron 2014-06-02 11:32

Mersenne number factored (disbelievers are biting elbows)
 
Using [url]http://www.mersenne.ca/prp.php[/url] , I reserved 1000 Mersenne composite numbers in order to perform PRP on the cofactors.

My computer found that:

M1304983 = 52199321 x PRP-392832

The log from Prime95 is:

[Mon Jun 02 04:50:39 2014]
M1304983/52199321 is a probable prime! We1: D4B7573A,00000000

It appears to be the largest PRP known from Mersenne numbers.

PS: Doing a search on Internet, I found that this PRP was already done:
[URL="http://www.primenumbers.net/prptop/searchform.php?form=%282^p-1%29/%3F&action=Search"]PRP top records[/URL]

Anyway I will continue performing more PRPs on Mersenne number cofactors.

bloodIce 2014-06-02 20:08

It is a pity that this PRP has been reported before, but good luck with the rest. I was doing PRP on cofactors for for a while. Absolutely stupid many would say, but it is funny and anything above the current is a record holder :-).

Batalov 2014-06-02 20:47

It would be, in theory. That is, if one knew exactly how far Never-Odd-Or-Even [B]already [/B]went. Because you don't know, it is a high risk-low return type of research project. The PRP test time goes up, up and up, and the probability of the cofactor being prime goes down and down. You also don't know whether NOOE is [B]still[/B] running his tests; if he actually is, then you are virtually attempting to catch up with a power player with significant resources (or in other words, you are not going to catch up).

alpertron 2014-06-02 21:01

Well, this is not entirely correct, as several new prime factors of Mersenne numbers with exponents lower than 2M are being found every day. So I expect that they have not ran PRP on the new cofactors.

Batalov 2014-06-02 21:24

There is some window in this new pool, I agree.

MatWur-S530113 2014-06-03 02:14

[QUOTE=alpertron;374888]Well, this is not entirely correct, as several new prime factors of Mersenne numbers with exponents lower than 2M are being found every day. So I expect that they have not ran PRP on the new cofactors.[/QUOTE]

I'm not sure about this. Some time ago I run ecm-curves on M-numbers without known factors in different ranges only to get candidates for a prp-test, my own best one (#2 at that list...) should be such a candidate. Only if the known factors are found definetely by TF I would do a prp-test.

Your main problem seems to be of problem of reporting a PRP-result to GIMPS (mersenne.org). As mersenne.ca seems to be 'only' a mirror it doesn't know of the prp-result, because it is not stored at GIMPS. (typically an answer like
[QUOTE]Sending result to server: UID: Wurtinger/i5-4670K, M4206583/322661843389993 is not prime. RES64: A51241E89B25CD16. We4: AE62110B,00000000

PrimeNet error 45: Invalid result type
ar: invalid result type: 150[/QUOTE]will appear in communication thread and prime.log. )
But mersenne.ca works fine if the results are posted there. I assigned 4 hours ago the first 40 available exponents for prp-test at range 2M+. the tests needed 3 hours, then I simply copied the results-lines of results.txt (incl. Timestamps) and posted them at mersenne.ca resultpage. It was shown that they were added as 'not-prp' to the db and a new list of the available exponents for the same range doesn't show these exponents anymore.
So it seems to be only a problem of 'filling-up' the db at mersenne.ca. As Batalov said, it would be helpful if the results of some power players could be added, but on the other hand every new factor 'forces' a new prp-test.
But I like the idea of a prp-db :tu:, I think I will spend some more time for prp-test in the next future.

greetings,

Matthias

bloodIce 2014-06-03 07:22

When I was looking for PRP, what I did was massive attack of some exponent with TF/Pminus1/ECM until it starts to be unreasonable. Unreasonable is subjective and depends on resources you have. If there were new factors, I was doing a PRP test. If there were no factors, at least I report the TF results to GIMPS (if the expo is unfactored) and Pminus1 results to mersenne.ca, ECM is never a loss. I think the chance for a new PRP is in finding new factors in the range 1.5M-3M. That range is still accessible for all methods. I should admit that the best method there is Pminus1, but ECM still kicks some factors.

alpertron 2014-06-03 11:38

In 4 days I cleared more than 1000 exponents in [url]http://www.mersenne.ca[/url] and my idea is to have all the exponents below 2M with PRP done. There are still 3000 exponents to be PRP'ed to reach that goal.

bloodIce 2014-06-03 11:54

That is ambitious goal, but achievable. In two weeks you might be done. I may join on over 2M for a while :-). However I can do several per day, so my chances are null. Good luck, I would love to see new PRP over the current record.

alpertron 2014-06-03 18:45

At this moment all exponents below 1911000 were tested.

alpertron 2014-06-04 01:22

I found that there are some holes in the PRP database on [url]http://www.mersenne.ca[/url]. For example, from the link: [url]http://www.mersenne.ca/prp.php?show=2&min_exponent=1828000&max_exponent=1911149[/url] we can find a lot of exponents without PRP done, but this range cannot be reserved using the form [url]http://www.mersenne.ca/prp.php?show=3&min_exponent=1828000&max_exponent=1911149[/url]

Mini-Geek 2014-06-04 01:41

[QUOTE=alpertron;374996]I found that there are some holes in the PRP database on [url]http://www.mersenne.ca[/url]. For example, from the link: [url]http://www.mersenne.ca/prp.php?show=2&min_exponent=1828000&max_exponent=1911149[/url] we can find a lot of exponents without PRP done, but this range cannot be reserved using the form [url]http://www.mersenne.ca/prp.php?show=3&min_exponent=1828000&max_exponent=1911149[/url][/QUOTE]

The "no"s at your first link mean that a PRP test was run and determined it was composite, not that no test has been run. I don't see any gaps here.

alpertron 2014-06-04 01:45

There are thousands of exponents that have no "no" or "PRP" in that range, so the result is unknown from the point of view of the database.

Mini-Geek 2014-06-04 02:13

[QUOTE=alpertron;374999]There are thousands of exponents that have no "no" or "PRP" in that range, so the result is unknown from the point of view of the database.[/QUOTE]

Oh, I see what you mean. Mea culpa. Assuming all is working as intended, the only apparent cause, then, is that they're reserved to be PRP tested. It says the reservations last for 7 days, so they should soon be complete or available for reservation.

alpertron 2014-06-13 22:20

I've just found a complete factorization:

M576551 = 4612409 x 64758208321 x 242584327930759 x PRP-173528

paulunderwood 2014-06-13 22:45

Congrats! Please submit it to Henri Lifchitz's PRP database. :smile:

alpertron 2014-06-14 00:06

[QUOTE=paulunderwood;375751]Congrats! Please submit it to Henri Lifchitz's PRP database. :smile:[/QUOTE]
I've just did that, thanks.

Gordon 2014-06-14 08:31

[QUOTE=alpertron;375749]I've just found a complete factorization:

M576551 = 4612409 x 64758208321 x 242584327930759 x PRP-173528[/QUOTE]

Just to be pedantic, if it's a PROBABLE prime factor then all we know for certain is that we don't actually know the answer :grin:

For a moment there got quite [U]excited [/U]when I saw completely factored :mad:

retina 2014-06-14 08:51

[QUOTE=Gordon;375794]Just to be pedantic, if it's a PROBABLE prime factor then all we know for certain is that we don't actually know the answer :grin:

For a moment there got quite [U]excited [/U]when I saw completely factored :mad:[/QUOTE]Well since we are being pedantic :ermm: then it is easy to find completely factored Mersenne numbers much larger than any given here. For instance 2[sup]57885161[/sup]-1 is one such number. :evil:

And here is another: 2[sup]2[sup]26[/sup][/sup]-1. :razz:

[color=grey]All numbers presented here meet the definition of a Mersenne number as specified in the current title "New [b]mersenne number[/b] completely factorized".[/color]

Gordon 2014-06-14 09:00

[QUOTE=retina;375795]Well since we are being pedantic :ermm: then it is easy to find completely factored Mersenne numbers much larger than any given here. For instance 2[sup]57885161[/sup]-1 is one such number. :evil:

And here is another: 2[sup]2[sup]26[/sup][/sup]-1. :razz:

[color=grey]All numbers presented here meet the definition of a Mersenne number as specified in the current title "New [b]mersenne number[/b] completely factorized".[/color][/QUOTE]

Then there's that pesky thing called a dictionary :smile:

probable  
1. likely to occur or prove true
2. having more evidence for than against, or evidence that inclines the mind to belief but leaves some room for doubt.
3. affording ground for belief.

So by definition, it is not [U][B]completely[/B][/U] factored.

LaurV 2014-06-14 09:28

[QUOTE=retina;375795]2[sup]2[sup]26[/sup][/sup]-1[/QUOTE]
:orly emu:
This equals (2^2^25-1)(2^2^25+1).
Since when F25 is full factored? :shock:

retina 2014-06-14 10:00

[QUOTE=Gordon;375796]So by definition, it is not [U][B]completely[/B][/U] factored.[/QUOTE]I never said it was. But I did give larger examples that are.

retina 2014-06-14 10:05

[QUOTE=LaurV;375800]This equals (2^2^25-1)(2^2^25+1).
Since when F25 is full factored? :shock:[/QUOTE]Okay, maybe my mistake. I thought that 2[sup]ab[/sup]-1 could be factored by (2[sup]a[/sup]-1) x (1+2[sup]a[/sup]+2[sup]2a[/sup]+2[sup]3a[/sup]+...+2[sup](b-1)a[/sup])

Edit: So, nevermind I guess it is still easy to construct one with 2[sup]pq[/sup]-1?

BudgieJane 2014-06-14 16:40

[QUOTE=Gordon;375796]Then there's that pesky thing called a dictionary :smile:

probable  
1. likely to occur or prove true
2. having more evidence for than against, or evidence that inclines the mind to belief but leaves some room for doubt.
3. affording ground for belief.

So by definition, it is not [U][B]completely[/B][/U] factored.[/QUOTE]

Then there's that other pesky thing called a definition: A probable prime is defined as a number that has passed a probable prime test.

Gordon 2014-06-14 18:45

[QUOTE=BudgieJane;375824]Then there's that other pesky thing called a definition: A probable prime is defined as a number that has passed a probable prime test.[/QUOTE]

Yep, probable, see my previous dictionary definition.

This number is [U][B]100% NOT competely factored[/B][/U], you can dress it up however you want, but the facts don't lie.

alpertron 2014-06-14 22:00

Well, if you want me to be completely pedantic, if you know that the Mersenne number shown is not 100% completely factored, that means that the 173528-digit pseudoprime is composite. What is your proof?

Gordon 2014-06-14 22:12

[QUOTE=alpertron;375847]Well, if you want me to be completely pedantic, if you know that the Mersenne number shown is not 100% completely factored, that means that the 173528-digit pseudoprime is composite. What is your proof?[/QUOTE]

That's just it you see, I don't need proof of anything, I'm not the one making the unverifiable claim, remember [U]your[/U] claim was

"...completely factorized"

So for that to be true there can be no PRP rubbish spouted, show all the factors else [U]you are making a false and misleading claim[/U].

Amazing how many people on here struggle with simple English and seem to believe that

Probable == Definitively

It doesn't... :mooc:

MatWur-S530113 2014-06-15 01:11

Congratz Dario, nice found. Your prp is now listet as #6 of Henri Lifchitz's page of Mersenne cofactors:
[URL]http://www.primenumbers.net/prptop/searchform.php?form=%282^n-1%29%2F%3F&action=Search[/URL]

@Gordon: maybe an expression like '(prp-)completet' is more accurate, but everyone who is interestet in factoring such large M-numbers knows, that a complete factorization of a M-number with an exponent ~500k will have one or more prp's involved. Simply compare the size of the largest proven prime cofactor of a M-number (I don't know the size, I think somewhere 1000-2000 bits) with the size of this M-number. Do you expectet 500 factors with average size of ~1000 bits and all factors are proven as prime (with primo or so)? And the complete thread is talking about "looking for prp's". See f.e.:
[URL]http://www.mersenne.ca/prp.php?show=1&min_exponent=100000&max_exponent=1000000[/URL]

Dario's prp is already included :wink:

mfg
Matthias

Gordon 2014-06-15 10:32

[QUOTE=MatWur-S530113;375868]

[snip]

that a complete factorization of a M-number with an exponent ~500k will have one or more prp's involved. Simply compare the size of the largest proven prime cofactor of a M-number (I don't know the size, I think somewhere 1000-2000 bits) with the size of this M-number. Do you expectet 500 factors with average size of ~1000 bits and all factors are proven as prime

[snip]

[/QUOTE]

Precisely the point, you believe with some degree of confidence that it is prime, it may well be, we'll probably never know in our lifetimes.

All you do know with 100% certainty is that it is [B][U]NOT FACTORED COMPLETELY[/U][/B]

I am reminded of this famous quote

“The less people know, the more stubbornly they know it.” -Osho

axn 2014-06-15 12:11

[QUOTE=Gordon;375882]All you do know with 100% certainty is that it is [B][U]NOT FACTORED COMPLETELY[/U][/B][/QUOTE]

Consider the two statements:

A: We do NOT know with 100% certainty that it is factored completely.

B: We do know with 100% certainty that it is NOT factored completely.

Do you believe these two to be identical?

retina 2014-06-15 13:49

[QUOTE=Gordon;375882]All you do know with 100% certainty is that it is [B][U]NOT FACTORED COMPLETELY[/U][/B][/QUOTE]Actually we don't know that. It might be completely factored, or it might not. We have a high confidence that it is completely factored. But we can't say for certainty that it is not.

potonono 2014-06-15 17:06

I possibly more or less but not definitely rejected the idea that there is in no way any amount of uncertainty that I undeniably do or do not know that it is completely factored.

R.D. Silverman 2014-06-16 17:47

[QUOTE=retina;375894]Actually we don't know that. It might be completely factored, or it might not. We have a high confidence that it is completely factored. But we can't say for certainty that it is not.[/QUOTE]

You are bandying words and undefined terminology.

Start by defining "completely factored".

My definition would be:

A number is completely factored when it is represented as the product
of primes.

Since the number in question has not been represented as the product of
primes, then it most definitely has NOT been completely factored.

science_man_88 2014-06-16 18:10

[QUOTE=R.D. Silverman;375973]You are bandying words and undefined terminology.
[/QUOTE]

what's being pointed out is that without knowing if the PRP is prime or not, we can not know with 100% certainty that it is not completely factored Gordon made that claim. As did you by saying [QUOTE]Since the number in question has not been represented as the product of
primes, then it most definitely has NOT been completely factored.[/QUOTE]

I would replace primes with known primes otherwise you're claiming you know that a 173000 + digit number isn't prime.

edit: I just realized you could use modular arithmetic to limit what it is and if the factorization fits the required number of each remainder. maybe that'll lead me to your logic.

wblipp 2014-06-16 20:48

[QUOTE=R.D. Silverman;375973]the number in question has not been represented as the product of primes[/QUOTE]

Can you prove this statement?

I thought a number was prime or not prime independent of our ability to prove that. The number has been represented as a product. It's possible that it is a product of primes, so it's possible the number has been completely factored.

R.D. Silverman 2014-06-16 22:06

[QUOTE=wblipp;375983]Can you prove this statement?
[/QUOTE]

What drugs are you on? The number has been represented as the product of
SOME primes and a single large PROBABLE PRIME.

It is *conjectured* that it is the product of primes.

Perhaps you need to learn what a conjecture is??

chalsall 2014-06-16 22:14

[QUOTE=R.D. Silverman;375984]Perhaps you need to learn what a conjecture is??[/QUOTE]

Perhaps you need to get out more....

kladner 2014-06-16 22:16

[QUOTE=potonono;375900]I possibly more or less but not definitely rejected the idea that there is in no way any amount of uncertainty that I undeniably do or do not know that it is completely factored.[/QUOTE]

Well said! (Possibly, I think, maybe.) :smile:

chalsall 2014-06-16 22:32

[QUOTE=science_man_88;375974]I just realized you could use modular arithmetic to limit what it is and if the factorization fits the required number of each remainder. maybe that'll lead me to your logic.[/QUOTE]

Each reindeer, did you say?

Prime95 2014-06-17 00:29

[QUOTE=chalsall;375986]Perhaps you need to get out more....[/QUOTE]

Can we cease with the contentless needling of forum members?

retina 2014-06-17 00:56

[QUOTE=Prime95;375996]Can we cease with the contentless needling of forum members?[/QUOTE]Probably not.

wblipp 2014-06-17 03:07

[QUOTE=R.D. Silverman;375984]What drugs are you on?[/QUOTE]
Allopurinol. Baby aspirin. I'm supposed to be taking Simvastatin, but my gout won't tolerate it. I don't think any of these affect my mathematical reasoning.

Let's see if we can figure out what you are trying to say, and where our disagreement.

We all agree that:
[QUOTE=R.D. Silverman;375984]The number has been represented as the product of SOME primes and a single large PROBABLE PRIME.[/Quote]

We all agree that
[QUOTE]It is *conjectured* that it is the product of primes.[/QUOTE]

We have all accepted your definition
[QUOTE]A number is completely factored when it is represented as the product of primes.[/QUOTE]

Where we appear to separate is your statement that:
[QUOTE]the number in question has not been represented as the product of primes[/QUOTE]

I don't see how you can possibly know that. The given representation is either a product of primes, or it isn't, entirely independent of our ability to prove that. Hence it is a complete factorization or it is not, independent of our ability to prove it. Your definition of "completely factored" does NOT require the proof of the primes. Nobody here can PROVE the given factorization is complete - and I don't think anybody has claimed that recently in the thread.

But it is also true the nobody here can PROVE the given factorization is incomplete - yet you have asserted that this true.

If you disagree, please try to explain why.

wblipp 2014-06-17 03:50

Perhaps Bob MEANT to give this definition:

A number is completely factored when it is proven to be represented as the product of primes.

Everything he said would have made sense if "is proven" had been included in his definition of "fully factored."

R.D. Silverman 2014-06-17 10:51

[QUOTE=wblipp;376003]I don't see how you can possibly know that. The given representation is either a product of primes, or it isn't, entirely independent of our ability to prove that. Hence it is a complete factorization or it is not, independent of our ability to prove it. Your definition of "completely factored" does NOT require the proof of the primes. Nobody here can PROVE the given factorization is complete - and I don't think anybody has claimed that recently in the thread.

But it is also true the nobody here can PROVE the given factorization is incomplete - yet you have asserted that this true.

If you disagree, please try to explain why.[/QUOTE]

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.

bloodIce 2014-06-17 14:14

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

Gordon 2014-06-17 14:26

[QUOTE=R.D. Silverman;376014]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.[/QUOTE]

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 2014-06-17 14:37

[QUOTE=Gordon;376025]See, making ridiculous claims is easy ...[/QUOTE]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 2014-06-17 15:10

[QUOTE=R.D. Silverman;376014]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.[/QUOTE]

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.

======
[B]1.[/B] We have a factorization.[INDENT][I](We agree)[/I][/INDENT]
[B]2.[/B] We don't know if it is a factorization into primes[INDENT][I](We agree)[/I][/INDENT]
[B]3.[/B] If it IS a factorization into primes, then the number is completely factored.[INDENT][I]Your definition of completely factored[/I][/INDENT][INDENT][INDENT][I][B]A possible source of disagreement[/B] 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[/I][/INDENT][/INDENT]
[B]4.[/B] You have asserted that is NOT completely factored[INDENT][I]Your post, quoted by me[/I][/INDENT][INDENT][INDENT][I][B]This is also a possible point of disagreement.[/B] 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.[/I][/INDENT][/INDENT]
[B]5[/B]. Because of #3, your assertion in #4 is equivalent to asserting the known factorization is NOT a factorization into primes.[INDENT][I]Here is where the disagreement gets visible[/I][/INDENT][INDENT][INDENT][I]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.[/I][/INDENT][/INDENT]

Stargate38 2014-06-17 15:48

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 2014-06-17 16:03

[QUOTE=retina;376027]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.[/QUOTE]

Neither is the OP's claim of [U]completely factored[/U] ....

Gordon 2014-06-17 16:06

[QUOTE=wblipp;376029]

[snip]

My understanding that is IS a complete factorization, [U]but it is not KNOWN[/U] to be a complete factorization

[snip]

[/QUOTE]

Bingo!! Give the man a prize, somebody else also gets it. The OP's claim therefore doesn't stand up.

Gordon 2014-06-17 16:26

[QUOTE=Stargate38;376031]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).[/QUOTE]

1. Quantum computing is a lovely idea, how many bits will we need?
[INDENT][URL="http://en.wikipedia.org/wiki/RSA_numbers"]RSA[/URL] says a 2048 bit number is 617 decimal digits[/INDENT][INDENT]The OP's PRP has 173,528 digits, or 281x as many[/INDENT][INDENT]Think it will be a while afore we get 575,000 bit QC's[/INDENT]
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 2014-06-17 16:36

According to [url]http://primes.utm.edu/top20/page.php?id=27[/url] , 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 2014-06-17 16:49

[QUOTE=alpertron;376042]According to [url]http://primes.utm.edu/top20/page.php?id=27[/url] , 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.[/QUOTE]

From what I can tell, ECPP is [URL="http://en.wikipedia.org/wiki/Elliptic_curve_primality"]about O((log n)^4)[/URL], 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 2014-06-17 16:55

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.

R.D. Silverman 2014-06-17 17:13

[QUOTE=wblipp;376029]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.
[/QUOTE]

What you are concerned with is irrelevant. We do not know that
the factorization is complete. This is a fact. The probable prime may
not be prime. Do you understand that "not complete" means "incomplete"??
Why is this so hard for you?


[QUOTE]
And I think that you have claimed that the factorization is incomplete.

I'll lay out my logic is excruciating detail.
[/QUOTE]

It isn't logic. It is simple bandying of words.

[QUOTE]
I think you have made the much stonger assertion that the factorization in known to be incomplete.
[/QUOTE]

What "much stronger assertion"?? Your claim is idiotic. We do not have a
complete factorization into primes until we have a set of integers whose
product equals the original number and each integer in our set is prime.
We do not have that!!!!! Therefore we do not have a complete factorization.
Therefore it is incomplete BY THE DEFINITION OF INCOMPLETE.

[QUOTE]
Because of #3, your assertion in #4 is equivalent to asserting the known factorization is NOT a factorization into primes.
[/QUOTE]

This is a correct assertion. We have a factorization into SOME primes,
plus a number that may or may not be prime. PRIME does NOT equal
PROBABLE PRIME. We do not have a factorization into primes, since
we do not know if the ultimate factor is prime.

CRGreathouse 2014-06-17 17:39

[QUOTE=R.D. Silverman;376047]What you are concerned with is irrelevant. We do not know that
the factorization is complete. This is a fact. The probable prime may
not be prime. Do you understand that "not complete" means "incomplete"??
Why is this so hard for you?[/QUOTE]

The confusion seems straightforward: the claims "the factorization is known to be incomplete" and "the factorization is not known to be complete" have been confounded. The latter is correct, while the former is incorrect.

R.D. Silverman 2014-06-17 18:41

[QUOTE=CRGreathouse;376049]The confusion seems straightforward: the claims "the factorization is known to be incomplete" and "the factorization is not known to be complete" have been confounded. The latter is correct, while the former is incorrect.[/QUOTE]

Does "incomplete factorization" mean:

"known to have more prime factors than is currently known" (i.e. the
factorization is known to be incomplete) [your first phrase]

or

"may have more prime factors than is currently known".

I argue the latter. A factorization is complete when we know all of its
prime factors. It a number might have additional unknown prime factors
than what is already known, then it must be considered incomplete.

wblipp 2014-06-17 18:49

[QUOTE=R.D. Silverman;376047]We have a factorization into SOME primes, plus a number that may or may not be prime.[/QUOTE]

Isn't this the same as
[INDENT][B]We have a factorization that may or may not be a factorization into primes
[/B][/INDENT]
Isn't that the same as[INDENT][B]We have a factorization that may or not be a complete factorization[/B][/INDENT]
Isn't that the same as[INDENT][B]The number may or may not be completely factored[/B][/INDENT]
And doesn't that make the following assertion [B]unproven[/B]?[INDENT][B]The number is not completely factored[/B][/INDENT]

Batalov 2014-06-17 19:04

[QUOTE=wblipp;376056][INDENT][B]The number is not completely factored[/B][/INDENT][/QUOTE]
Parsing this sentence is like parsing "[URL="http://en.wikipedia.org/wiki/Syntactic_ambiguity"]Eduardum occidere nolite timere bonum est[/URL]." (А Рussian textbook example sentence is "[URL="http://ru.wikipedia.org/wiki/Казнить_нельзя_помиловать"]Казнить нельзя помиловать[/URL].")

One person will see [I]potatoe[/I]:
{The number} is {not completely} {factored}
and another will see [I]potahto[/I]:
{The number} is not {completely factored}

wblipp 2014-06-17 19:09

[QUOTE=R.D. Silverman;376055]I argue the latter. A factorization is complete when we know all of its prime factors. It a number might have additional unknown prime factors than what is already known, then it must be considered incomplete.[/QUOTE]

That's not what your definition of "completely factored" says. This changes your definition in the manner I suggested you might have in mind very early in this exchange. All I've been doing is showing that, BY YOUR DEFINITION, you CANNOT prove the number is not completely factored. Apparently you have been working off your intuition instead your definition.

wblipp 2014-06-17 19:19

[QUOTE=R.D. Silverman;376055]A factorization is complete when we know all of its prime factors. It a number might have additional unknown prime factors
than what is already known, then it must be considered incomplete.[/QUOTE]

Perhaps you mean to say "A factorization is complete when we know that we know all of its prime factors."

For the case under consideration, it is likely that that the factors we know are all the prime factors. The extra level of "know" is necessary if we want to move from "it is not known to be completely factored" to "it is not completely factored."

Gordon 2014-06-17 19:27

[QUOTE=wblipp;376060]Perhaps you mean to say "A factorization is complete when we know that we know all of its prime factors."

For the case under consideration, it is likely that that the factors we know are all the prime factors. The extra level of "know" is necessary if we want to move from "it is not known to be completely factored" to "it is not completely factored."[/QUOTE]

You are losing sight of the fact that the [U]original claim[/U] was this number is [I]COMPLETELY FACTORED[/I], which we now all seem to accept we don't know, [B][U]therefore the original claim is FALSE[/U][/B].

Why? The opposite of true is always false, it is binary, it's one or the other. Until proven true it's false. It's not that difficult.

CRGreathouse 2014-06-17 19:29

[QUOTE=R.D. Silverman;376055]Does "incomplete factorization" mean[/QUOTE]

Indeed, this is the ambiguity to which I referred.

science_man_88 2014-06-17 19:37

[QUOTE=Gordon;376062]You are losing sight of the fact that the [U]original claim[/U] was this number is [I]COMPLETELY FACTORED[/I], which we now all seem to accept we don't know, [B][U]therefore the original claim is FALSE[/U][/B].

Why? The opposite of true is always false, it is binary, it's one or the other. Until proven true it's false. It's not that difficult.[/QUOTE]

because you made a claim that you knew 100% that it was not completely factored. which in theory means you know it to be composite, because you know all the PRP's factors is off the table if it is indeed composite, Because, this means you know the full factorization of the number originally talked about. Your turn to prove it can not be a prime.

chalsall 2014-06-17 19:40

[QUOTE=Gordon;376062]Until proven true it's false. It's not that difficult.[/QUOTE]

Until a statement is proven false it might still be true. Or its state may be unknown.

CRGreathouse 2014-06-17 19:45

[QUOTE=chalsall;376066]Until a statement is proven false it might still be true. Or its state may be unknown.[/QUOTE]

Indeed.

Gordon 2014-06-17 19:48

[QUOTE=science_man_88;376065]because you made a claim that you knew 100% that it was not completely factored. which in theory means you know it to be composite, because you know all the PRP's factors is off the table if it is indeed composite, Because, this means you know the full factorization of the number originally talked about. Your turn to prove it can not be a prime.[/QUOTE]

I don't have to prove anything, I didn't make the unprovable claim of completely factored.

Gordon 2014-06-17 19:49

[QUOTE=chalsall;376066]Until a statement is proven false it might still be true. Or its state may be unknown.[/QUOTE]

True/False isn't a tri-state affair.

science_man_88 2014-06-17 19:51

[QUOTE=Gordon;376068]I don't have to prove anything, I didn't make the unprovable claim of completely factored.[/QUOTE]

unprovable and unprovable in our life time are two completely different things.

I'd argue you might want to reconsider as you also made a claim that you knew something 100% certainty , that is really the part of the completely factored argument you are going after.

science_man_88 2014-06-17 19:53

[QUOTE=Gordon;376069]True/False isn't a tri-state affair.[/QUOTE]

what about simply unproven ?

Mini-Geek 2014-06-17 20:03

[QUOTE=Gordon;376069]True/False isn't a tri-state affair.[/QUOTE]

"MM127 is prime" is a statement that is either true or false. Its value is knowable, in theory (simply run an LL test). Its value is unknown, and hypothesized by many to be false.
So you're right: obviously it's a completely binary affair. But we don't know which, so it can be considered a tri- or poly-state affair (unknown, conjectured true, conjectured false, etc.).

Gordon 2014-06-17 20:10

[QUOTE=science_man_88;376070]unprovable and unprovable in our life time are two completely different things.

I'd argue you might want to reconsider as you also made a claim that you knew something 100% certainty , that is really the part of the completely factored argument you are going after.[/QUOTE]

Unprovable or in our lifetime for anyone reading this IS the same thing on any practical basis as WE will never know :smile:

Until the original claimant presents their proof of primality, then it is composite. what I said was logically true. If a little inconvenient for some.

Gordon 2014-06-17 20:11

[QUOTE=Mini-Geek;376072]"MM127 is prime" is a statement that is either true or false. Its value is knowable, in theory (simply run an LL test). Its value is unknown, and hypothesized by many to be false.
So you're right: obviously it's a completely binary affair. But we don't know which, so it can be considered a tri- or poly-state affair (unknown, conjectured true, conjectured false, etc.).[/QUOTE]

..and in a binary state anything not true is by definition false. :mooc:

alpertron 2014-06-17 20:15

[QUOTE=Gordon;376073]Unprovable or in our lifetime for anyone reading this IS the same thing on any practical basis as WE will never know :smile:

Until the original claimant presents their proof of primality, then it is composite. what I said was logically true. If a little inconvenient for some.[/QUOTE]

An integer number greater than 1 is prime or composite independent from proofs. At this time it is not known whether that big number is prime or not. So we do not know whether it is composite or not. It is wrong to claim that it is composite because you have not presented any proof for that.

It is also wrong to say that the number cannot be proved prime or composite in our lifetimes, as shown in posts #53 to #55

chalsall 2014-06-17 20:15

[QUOTE=Gordon;376069]True/False isn't a tri-state affair.[/QUOTE]

Actually, it is.

Read up a bit about quantum uncertainty.

chalsall 2014-06-17 20:27

[QUOTE=Gordon;376074]..and in a binary state anything not true is by definition false. :mooc:[/QUOTE]

Are you familiar with the concept that nothing can be proved, but only disproved?

R.D. Silverman 2014-06-17 20:39

[QUOTE=wblipp;376056]Isn't this the same as
[INDENT][B]We have a factorization that may or may not be a factorization into primes
[/B][/INDENT]
Isn't that the same as[INDENT][B]We have a factorization that may or not be a complete factorization[/B][/INDENT][/QUOTE]

No, it is not the same. Unless you know that the factorization is complete
then it is incomplete.

Consider the set of known complete factorizations. Complete means
that all of its prime factors are known. IF a number is NOT IN THIS SET,
(i.e. it is in the complentary set) then its factorization IS NOT COMPLETE.

Furthermore, since it is not in the set, we KNOW that it is not complete.
Knowing that it is not complete and knowing that it must have additional
unknown prime factors are two different things.

[QUOTE]
Isn't that the same as[INDENT][B]The number may or may not be completely factored[/B][/INDENT][/QUOTE]

No. There is no "may be" about it. The number DEFINITELY is not
completely factored.

wblipp 2014-06-17 22:01

[QUOTE=R.D. Silverman;376078]No, it is not the same. Unless you know that the factorization is complete then it is incomplete.[/QUOTE]

In post #33 you said:
[QUOTE=R.D. Silverman;375973]
Start by defining "completely factored".

My definition would be:

A number is completely factored when it is represented as the product of primes.[/QUOTE]

I do not understand how these two statements are consistent. Is there some magic being hidden in the word "represented?" Or are you playing some word games of making a distinction between the meaning of "completely factored" and "factorization is complete?" Unless there is some such sophistry here, I don't see how your definition of "completely factored" requires you to KNOW that the factorization is complete.

I'm only claiming that it is possible that the known factorization meets the definition - that it is NOT provable by us today that the known factorization does not meet the definition.

kladner 2014-06-17 22:38

[QUOTE] Is there some [B]magic being[/B] hidden in the word "represented?"[/QUOTE]
Deus ex mathematica?

Gordon 2014-06-17 22:55

[QUOTE=wblipp;376084]

[snip]

I'm only claiming that it is possible that the known factorization meets the definition

[snip]

[/QUOTE]

It is POSSIBLE that the number has been fully factored it is IMPOSSIBLE to state that it has been because nobody knows.

Yet again someone else gets it, the original claim was false.

Xyzzy 2014-06-18 00:06

1 Attachment(s)
[COLOR="White"].[/COLOR]

Jayder 2014-06-18 00:07

I'm guessing Mr. Silverman's definition considers "primes" to be known and proven primes, only. If there is any doubt, you can't consider it a prime. It seems like he's saying that if you don't know for sure, you don't know at all.

Funnily, this topic reminds me of [URL="http://www.mersenneforum.org/showthread.php?t=17747"]this fun topic from last year[/URL]. (Good for a read.)

[QUOTE=Gordon;376088]It is POSSIBLE that the number has been fully factored it is IMPOSSIBLE to state that it has been because nobody knows.

Yet again someone else gets it, the original claim was false.[/QUOTE]
If my friend flips a fair coin and asks me to guess whether it came up heads or tails, and I [U]guess[/U] heads, is my guess instantly assumed false because I cannot prove it?

Now let's say the coin is unfair, and it is overwhelmingly more likely to turn up heads than it is tails. Is it [U]impossible[/U] for me to state that it is [I]most likely[/I] heads?

It would be wrong of me to say that it is certainly heads, as it would be to state that this Mersenne number has certainly been factored.

There is a lot of miscommunication and differing views/interpretations in this thread. Where you likely saw the original thread title as an unequivocal assertion, I (and it seems others) saw it as an educated guess.

[QUOTE=Gordon;376062][T]he [U]original claim[/U] was this number is [I]COMPLETELY FACTORED[/I], which we now all seem to accept we don't know, [B][U]therefore the original claim is FALSE[/U][/B].[/QUOTE]
"The original guess was the coin came up [I][B]HEADS[/B][/I], which we now all seem to accept [I]we don't know[/I], therefore the original claim is FALSE."

By calling the original claim of heads false, aren't you saying that it must be assumed tails? Even in the face of overwhelming odds against it being tails? Does that really make sense to you? It's possible that you're not communicating yourself well, but that's what it looks like you're saying.

Maybe you're saying the part that's false is that it's "known"? Because that would be true, but that doesn't look like that's what you're saying.

Gordon 2014-06-18 09:59

[QUOTE=Jayder;376096]

[snip]

If my friend flips a fair coin and asks me to guess whether it came up heads or tails, and I guess heads, is my guess instantly assumed false because I cannot prove it?

Where you likely saw the original thread title as an unequivocal assertion, I (and it seems others) saw it as an educated guess.

[snip]

[/QUOTE]

Unless you flip the coin so high that it leaves orbit you get proof in 2 seconds. Bad analogy.

The OP stated "[U]I've[/U] just [U]found [/U]a complete factorization"

I don't care what dictionary you are using that is an unequivocal assertion. It doesn't say

"I might have.."

"I could have.."

"I think.."

So as it is unprovable (at present or whatever) as a feinitive assertion it is false.

It really is quite simple.

Of course if the OP wishes to retract his claim and replace it with

"It looks like I might have completely factored Mxxxxx as all that is left is a 173,000 digit number which is PRP with a high degree of confidence"

Gordon 2014-06-18 10:03

[QUOTE=Jayder;376096]

[snip]

Maybe you're saying the part that's false is that it's "known"? Because that would be true, but that doesn't look like that's what you're saying.

[snip]
[/QUOTE]

The op made the claim that it was "known", he claimed he had completely factored.

I think we can all agree that it "might" be prime, it might even be "likely" prime, but the one it definitely isn't is [U]known[/U] prime.

Therefore the original assertion is false.

BudgieJane 2014-06-18 11:32

[QUOTE=Gordon;376121]
The OP stated "[U]I've[/U] just [U]found [/U]a complete factorization"
[/quote]

What's wrong with a factorization that includes composite factors? Note that in what you quoted the OP doesn't say "I've just found a complete [I]prime[/I] factorization".

[quote]
"It looks like I might have completely factored Mxxxxx as all that is left is a 173,000 digit number which is PRP with a high degree of confidence"[/QUOTE]

Since far too many people are being far too pedantic in this thread, shouldn't this statement end "which is PRP with a high degree of confidence that it is prime"?

R.D. Silverman 2014-06-18 11:35

[QUOTE=BudgieJane;376126]......


Since far too many people are being far too pedantic in this thread, [/QUOTE]

You seem to fail to understand. Precise definitions are what mathematics
is about. This is a mathematical discussion.

I suggest that you learn about the use of quantifiers in mathematics.

BudgieJane 2014-06-18 11:37

[QUOTE=chalsall;376066]Until a statement is proven false it might still be true. Or its state may be unknown.[/QUOTE]

So instead of using black/white Boolean logic to describe the state, shouldn't we use 50-shades-of-grey fuzzy logic (or, rather, infinite number of shades of grey)?

BudgieJane 2014-06-18 11:43

[QUOTE=R.D. Silverman;376127]You seem to fail to understand. Precise definitions are what mathematics
is about. This is a mathematical discussion.

I suggest that you learn about the use of quantifiers in mathematics.[/QUOTE]

No I don't. I agree about precise definitions, which is why I said in the bit you didn't quote that the OP didn't say that (s)he had found a complete [i]prime[/i] factorization. This statement is not precise enough, because the factorization could include composite factors and the statement would still be true.

Or are you going to tell me that the definition of "complete factorization" is "complete factorization into primes"?

Too many people being pedantic to me means more than zero. Is that exact enough?

science_man_88 2014-06-18 11:52

[QUOTE=BudgieJane;376129]No I don't. I agree about precise definitions, which is why I said in the bit you didn't quote that the OP didn't say that (s)he had found a complete [i]prime[/i] factorization. This statement is not precise enough, because the factorization could include composite factors and the statement would still be true.

Or are you going to tell me that the definition of "complete factorization" is "complete factorization into primes"?

Too many people being pedantic to me means more than zero. Is that exact enough?[/QUOTE]

he already did:

[QUOTE="post 33"]A number is completely factored when it is represented as the product
of primes.[/QUOTE]

R.D. Silverman 2014-06-18 12:00

[QUOTE=BudgieJane;376129]No I don't. I agree about precise definitions, which is why I said in the bit you didn't quote that the OP didn't say that (s)he had found a complete [i]prime[/i] factorization. This statement is not precise enough, because the factorization could include composite factors and the statement would still be true.
[/QUOTE]

You are an idiot. And you can't read. I gave a definition of complete
factorization within this thread. Apparently you didn't read it.
[QUOTE]

Or are you going to tell me that the definition of "complete factorization" is "complete factorization into primes"?
[/QUOTE]

Hey Idiot. Go read the definition.

[QUOTE]
Too many people being pedantic to me means more than zero. Is that exact enough?[/QUOTE]

The first sentence just above is meaningless gibberish.

Gordon 2014-06-18 13:08

[QUOTE=BudgieJane;376126]

[snip]

What's wrong with a factorization that includes composite factors?

[snip][/QUOTE]

Are you being serious?

Which part of [SIZE="6"][B][U]"completely factored"[/U][/B][/SIZE] allows for composite factors?

you seem to struggle with comprehension of the English language...

Brian-E 2014-06-18 13:45

This discussion has been interesting to me, but I hope it's not going to be spoiled by people throwing insults around now. Even in Mathematics, the subtleties of language in definitions still surely leaves room for civilised debate without recourse to intimidation?
:unsure:

R.D. Silverman 2014-06-18 13:52

[QUOTE=Brian-E;376135]This discussion has been interesting to me, but I hope it's not going to be spoiled by people throwing insults around now. Even in Mathematics, the subtleties of language in definitions still surely leaves room for civilised debate without recourse to intimidation?
:unsure:[/QUOTE]

We can also try to carry on a conversation without people deliberately
being argumentative for the sake of being argumentative, or being
deliberately obtuse for the purpose of trolling.

I have given cogent explanations, yet I continue to get stupid arguments
from people who clearly do not know what they are talking about. We also
get comments that are totally nonsensical/meaningless.

retina 2014-06-18 14:07

[QUOTE=R.D. Silverman;376136]We also get comments that are totally nonsensical/meaningless.[/QUOTE]Welcome to the Internet. We can't change people but we can change how we react and respond to people.

R.D. Silverman 2014-06-18 14:28

[QUOTE=retina;376138]Welcome to the Internet. We can't change people but we can change how we react and respond to people.[/QUOTE]

Indeed. I agree about "how we respond to people".

When I ask a question or enter into a discussion about mathematics
with people who clearly have superior knowledge, I do not presume to
argue with them when they explain something.

I might not understand the answer and ask further questions, but I certainly
do not argue with them. Why? Because I do not [i]know enough[/i] to say
anything argumentative. If I did know enough, then there would be no
need for me to ask in the first place! If I *still* do not understand, then I
ask for guidance and information about what I should study so that I
[i]can[/i] understand.

To argue back, in a technical discussion, with someone who clearly has
superior knowledge of the subject is just plain [b]arrogant[/b] (and rude).
I choose to respond to such rudeness and arrogance in my own way.
If respondants do not like my replies then I say that this too is part of the Internet.

Many of the responders in this thread display such arrogance. They clearly
have not mastered math even at the pre-college (or even lower) level,
yet out of ignorance they [b]keep arguing[/b] (repetitively!)
even when given simple explanations.

This is either classic Dunning & Kruger [i]or[/i] deliberate trolling.

alpertron 2014-06-18 15:18

[QUOTE=Gordon;376133]Are you being serious?

Which part of [SIZE="6"][B][U]"completely factored"[/U][/B][/SIZE] allows for composite factors?

you seem to struggle with comprehension of the English language...[/QUOTE]

Gordon, I know that there is an extremely small probability that the big cofactor is not prime and so the Mersenne number is composite (we will need ECPP or a better algorithm to be invented in the future to settle the question), but it is clear that after determining that the cofactor is a pseudoprime, no one would try to continue running TF, P-1, ECM, etc. on that Mersenne number.

That's why I said that the number was completely factored. It was not intended to have mathematical rigor.

Please notice that you are walking a lot but you finish always in the same place, like carousel riding. And icons like :mooc: do not help to the conversation.


All times are UTC. The time now is 15:31.

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