20170802, 08:48  #1 
Aug 2017
3 Posts 
F12
Hi !
F12 factorization is no complete: F12 = p6 * p8_{1} * p8_{2} * p12 * p16 * p54 * c1133 We can represent each divisor as a sum of two squares: p6 = 260^{2} + 217^{2} p8_{1}= 4672^{2} + 2047^{2} p8_{2} = 7295^{2} + 3248^{2} p12 = 424231^{2} + 101500^{2} p16 = 19707737^{2} + 29457380^{2} p54 = 740185352931079335881406872^{2} + 144070437084262635215071007^{2} Then, we can do factorization for this squares: 260 = 2*2*5*13 217 = 7*31 4672 = 2*2*2*2*2*2*73 2047 =23*89 7295 = 5*1459 3248 =2*2*2*2*7*29 424231 = 424231 101500 = 2*2*5*5*5*7*29 19707737 = 7*73*38567 29457380 =2*2*5*1472869 740185352931079335881406872 = 2*2*2*11*43*84317*2319926432777805799 144070437084262635215071007 = 29*41*79811*10706677*141799782829 Can it help for factorization c1133 ? 
20170802, 14:32  #2 
Aug 2006
7^{2}·11^{2} Posts 

20171013, 10:10  #3 
Aug 2017
3 Posts 
We can use general number field sieve (GNFS) as the most efficient algorithm.
For example, for F7 we can take degree=4 for a next polynomial: m=4294967295 My question is: what degree is more effective for F12 ? For example: d=64 m=497705421315412257 or d=31 m=247710686406752022407372990900000000 etc ... How size of m determine the search of factor base and smooth numbers? 
20171013, 12:25  #4 
Einyen
Dec 2003
Denmark
3·23·43 Posts 
The current record for GNFS is 768 bits. You can see here discussions of how hard it would be to factor RSA 1024 bits:
http://www.mersenneforum.org/showthread.php?t=10382 http://www.mersenneforum.org/showthread.php?t=20421 The c1133 from F12 is 3,763 bits! It might never be factored by the GNFS algorithm, and at least not in the 21st century. 
20171013, 12:54  #5  
"Robert Gerbicz"
Oct 2005
Hungary
582_{16} Posts 
Quote:


20171013, 13:20  #6 
Einyen
Dec 2003
Denmark
3×23×43 Posts 
Yeah but the OP was talking about polynomial for GNFS. Still a 4097 bit SNFS is the same difficulty as 24002500 bit GNFS? I have no idea actually, I'm just basing it on the SNFS record is around 12001300 bits vs 768 bits GNFS.
It will still be several decades before that happens. Last fiddled with by ATH on 20171013 at 13:22 
20171013, 13:47  #7 
Jun 2003
17×277 Posts 

20171013, 14:03  #8 
Feb 2017
Nowhere
2·13·137 Posts 
I don't know a whole lot about snfs v. gnfs, but from what I've looked up, snfs is suited to numbers of special forms, and has the advantage that the polynomials generally have very small coefficients. A couple of possibly relevant sources may be
THE FACTORIZATION OF THE NINTH FERMAT NUMBER An Implementation of the Number Field Sieve 
20171013, 14:39  #9 
Aug 2017
3_{16} Posts 

20171013, 15:06  #10 
"Curtis"
Feb 2005
Riverside, CA
4391_{10} Posts 

20171014, 01:59  #11  
Aug 2002
Buenos Aires, Argentina
31×43 Posts 
Quote:
Code:
a = 11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591 b = 200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916 
