mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2013-10-03, 12:30   #45
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

10011000101112 Posts
Default

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

Carlos
pinhodecarlos is online now   Reply With Quote
Old 2013-10-03, 15:47   #46
chris2be8
 
chris2be8's Avatar
 
Sep 2009

24·127 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2013-10-03, 16:32   #47
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·37·127 Posts
Default

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.)
Batalov is offline   Reply With Quote
Old 2013-10-03, 21:04   #48
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
This method is totally dominated by faster methods. It is pointless.
I suggested this as a learning exercise. Learning is never pointless, IMHO.
philmoore is offline   Reply With Quote
Old 2013-10-03, 21:43   #49
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by pinhodecarlos View Post
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 is offline   Reply With Quote
Old 2013-10-03, 21:44   #50
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-10-04, 07:00   #51
gd_barnes
 
gd_barnes's Avatar
 
May 2007
Kansas; USA

3×3,449 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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.

Last fiddled with by gd_barnes on 2013-10-04 at 07:01
gd_barnes is offline   Reply With Quote
Old 2013-10-04, 17:55   #52
PBMcL
 
PBMcL's Avatar
 
Jan 2005

3E16 Posts
Default

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.
PBMcL is offline   Reply With Quote
Old 2013-10-04, 20:19   #53
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by PBMcL View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2013-10-04, 21:06   #54
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3·373 Posts
Default

Quote:
Originally Posted by gd_barnes View Post
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%.
philmoore is offline   Reply With Quote
Old 2013-10-04, 21:35   #55
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·37·127 Posts
Default

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: Φ13905(10) = 83431 · 333721 · prp7334 .
Batalov is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 12:17.

Thu Apr 22 12:17:51 UTC 2021 up 14 days, 6:58, 0 users, load averages: 2.00, 2.18, 2.07

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.