A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016 - Page 5

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:

Originally Posted by R.D. Silverman

This method is totally dominated by faster methods. It is pointless.

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

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

Quote:

Originally Posted by pinhodecarlos

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

Carlos

My email address has been updated

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

Quote:

Originally Posted by chris2be8

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

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

gd_barnes · 2013-10-04, 07:00

Quote:

Originally Posted by chris2be8

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

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:

Originally Posted by PBMcL

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.

I think you took too many quaaludes last night.

philmoore · 2013-10-04, 21:06

Quote:

Originally Posted by gd_barnes

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.

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: Φ₁₃₉₀₅(10) = 83431 · 333721 · prp7334 .

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Weird freezing error, desperate for a solution.	jasong	Lounge	5	2016-11-18 00:43
September 2016	Batalov	Puzzles	8	2016-10-04 14:10
YAFU Poly Select Deadline	amphoria	YAFU	22	2016-09-17 09:47
Official Ernst (ewmayer) / Richard (cheesehead) feud thread	cheesehead	Soap Box	50	2014-06-30 01:06
Appeal for machines	dave_dm	GMP-ECM	0	2005-06-29 02:23

2013-10-03, 12:30	#45
pinhodecarlos "Carlos Pinho" Oct 2011 Milton Keynes, UK 1001100010111₂ Posts	Offtopic. Mr. Silverman, R.D., can you update your profile at Scopus? Thank you in advance, Carlos

2013-10-03, 15:47	#46
chris2be8 Sep 2009 2⁴·127 Posts	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

2013-10-03, 16:32	#47
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·37·127 Posts	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.)

2013-10-04, 17:55	#52
PBMcL Jan 2005 3E₁₆ Posts	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.

2013-10-04, 21:35	#55
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·37·127 Posts	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: Φ₁₃₉₀₅(10) = 83431 · 333721 · prp7334 .