mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016 (https://www.mersenneforum.org/showthread.php?t=18640)

pinhodecarlos 2013-10-03 12:30

Offtopic.
Mr. Silverman, R.D., can you update your profile at Scopus?
Thank you in advance,

Carlos

chris2be8 2013-10-03 15:47

Back to the original request, how hard would it be to test the cofactors of F25, F26, etc for primality? If any are prime then the Fermat number would be fully factored.

Chris

Batalov 2013-10-03 16:32

They are likely already tested. It is far from hard - a few days' work. Run them and send the residues to W.Keller. (W.Keller for some reason is resistant to adding extra asterisks to some tested cofactors, above a certain limit set by him. Maybe, he wants to have double- and triple-checked residues.)

philmoore 2013-10-03 21:04

[QUOTE=R.D. Silverman;355074]This method is totally dominated by faster methods. It is pointless.[/QUOTE]

I suggested this as a learning exercise. Learning is never pointless, IMHO.

R.D. Silverman 2013-10-03 21:43

[QUOTE=pinhodecarlos;355079]Offtopic.
Mr. Silverman, R.D., can you update your profile at Scopus?
Thank you in advance,

Carlos[/QUOTE]

My email address has been updated

R.D. Silverman 2013-10-03 21:44

[QUOTE=chris2be8;355094]Back to the original request, how hard would it be to test the cofactors of F25, F26, etc for primality? If any are prime then the Fermat number would be fully factored.

Chris[/QUOTE]

F25, F26, and F27 have been tested. The cofactors are composite.

gd_barnes 2013-10-04 07:00

[QUOTE=chris2be8;355094]Back to the original request, how hard would it be to test the cofactors of F25, F26, etc for primality? If any are prime then the Fermat number would be fully factored.

Chris[/QUOTE]

Someone correct me if I'm wrong but even if the cofactors were PRP, they could not be proven prime, which means that the Fermat number would not be "proven" as fully factored.

I think that for Mr. Guy to win his bet, the only (un)reasonable chance is to fully factor one of F12/F13/F14.

PBMcL 2013-10-04 17:55

Although I wouldn't put any money on it myself, Guy could still win his bet if someone manages to build a quantum computer with enough q-bits to run Shor's algorithm on F12. This, of course, also assumes that they could get the result and publish it before government goons swept in, shouted "national security", and confiscated their hardware.

R.D. Silverman 2013-10-04 20:19

[QUOTE=PBMcL;355237]Although I wouldn't put any money on it myself, Guy could still win his bet if someone manages to build a quantum computer with enough q-bits to run Shor's algorithm on F12. This, of course, also assumes that they could get the result and publish it before government goons swept in, shouted "national security", and confiscated their hardware.[/QUOTE]

I think you took too many quaaludes last night.

philmoore 2013-10-04 21:06

[QUOTE=gd_barnes;355197]Someone correct me if I'm wrong but even if the cofactors were PRP, they could not be proven prime, which means that the Fermat number would not be "proven" as fully factored.

I think that for Mr. Guy to win his bet, the only (un)reasonable chance is to fully factor one of F12/F13/F14.[/QUOTE]

You are correct about the larger cofactors, even the cofactor of F17 is over 39000 digits, far beyond anything proven so far by ECPP.

But I wouldn't consider the chance of completely factoring F12/F13/F14 to be completely unreasonable. If ECM turned up a factor of 65 or 70 digits of F12 by ECM, and no smaller factor had been missed, we would expect the cofactor to have around an 11% chance of being prime. For F13, the probability drops to about half that, and half that again for F14. Unfortunately, after searching to 60 digits, we can only expect about a 1 in 7 chance of finding another factor searching to 70 digits, so maybe we can consider our overall chance of success with F12 to be around 1.5%.

Batalov 2013-10-04 21:35

Primality proofs were for some stretches of time divorced from factorizations, e.g. in the Cunningham project. It is likely that most people would agree that the factorizations of 2^13347311+1 and 2^13372531+1 are complete (some may not): they both are = 3 · "large PRP".

People are understandably much more strict when a primality proof is based on a PRP as a helper, e.g. the KP proof of (8·10^27811-71)/9 was definitely incomplete (before prp7334 was certified with Primo), though most would agree that the N-1 cofactor factorization was complete: Φ[SUB]13905[/SUB](10) = 83431 · 333721 · prp7334 .


All times are UTC. The time now is 11:54.

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