mersenneforum.org F12
 Register FAQ Search Today's Posts Mark Forums Read

 2017-08-02, 08:48 #1 serg2017   Aug 2017 3 Posts F12 Hi ! F12 factorization is no complete: F12 = p6 * p81 * p82 * p12 * p16 * p54 * c1133 We can represent each divisor as a sum of two squares: p6 = 2602 + 2172 p81= 46722 + 20472 p82 = 72952 + 32482 p12 = 4242312 + 1015002 p16 = 197077372 + 294573802 p54 = 7401853529310793358814068722 + 1440704370842626352150710072 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 ?
2017-08-02, 14:32   #2
CRGreathouse

Aug 2006

2×2,969 Posts

Quote:
 Originally Posted by serg2017 Can it help for factorization c1133 ?
No.

 2017-10-13, 10:10 #3 serg2017   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^4 + 4*m^3 + 6*m^2 + 4*m + 2 = F7$ 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?
 2017-10-13, 12:25 #4 ATH Einyen     Dec 2003 Denmark 56458 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.
2017-10-13, 12:54   #5
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

26128 Posts

Quote:
 Originally Posted by ATH 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.
It is still a snfs number at 4097 bits.

 2017-10-13, 13:20 #6 ATH Einyen     Dec 2003 Denmark 11×271 Posts Yeah but the OP was talking about polynomial for GNFS. Still a 4097 bit SNFS is the same difficulty as 2400-2500 bit GNFS? I have no idea actually, I'm just basing it on the SNFS record is around 1200-1300 bits vs 768 bits GNFS. It will still be several decades before that happens. Last fiddled with by ATH on 2017-10-13 at 13:22
2017-10-13, 13:47   #7
axn

Jun 2003

22·5·239 Posts

Quote:
 Originally Posted by serg2017 For example, for F7 we can take degree=4 for a next polynomial: $m^4 + 4*m^3 + 6*m^2 + 4*m + 2 = F7$ m=4294967295
Why the weird poly? Why not simply m^4+1, m=2^32?

 2017-10-13, 14:03 #8 Dr Sardonicus     Feb 2017 Nowhere 22×953 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
2017-10-13, 14:39   #9
serg2017

Aug 2017

3 Posts

Quote:
 Originally Posted by axn Why the weird poly? Why not simply m^4+1, m=2^32?
We can use more than one value for m

2017-10-13, 15:06   #10
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2·2,243 Posts

Quote:
 Originally Posted by serg2017 We can use more than one value for m
can you expand on this? I don't grasp how this is a relevant answer to a question about why you chose a weird poly.

2017-10-14, 01:59   #11
alpertron

Aug 2002
Buenos Aires, Argentina

23·167 Posts

Quote:
 Originally Posted by serg2017 Hi ! F12 factorization is no complete: F12 = p6 * p81 * p82 * p12 * p16 * p54 * c1133 We can represent each divisor as a sum of two squares: p6 = 2602 + 2172 p81= 46722 + 20472 p82 = 72952 + 32482 p12 = 4242312 + 1015002 p16 = 197077372 + 294573802 p54 = 7401853529310793358814068722 + 1440704370842626352150710072 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 ?
I do not think so, but I can tell you that c1133 = a2 + b2 where:

Code:
a = 11512882899820054257144225772505994511430981968359355559240636997087397239461885404688940982112272498773691260355731224763278685518244745544198267923163368736091123701779226072209279679342867029500044275233215203437226071842172804234583591297137729569486761340213325710137879698831126615998659706343950808674850862574868322314902443424081205544133789500128645355501388833990928089030944977862262874243179626287736961093227838096073086612878632276868708056678373714902078426666851025890207418013027573248367464970951431311736356210867866665430397629513384884406535591

b = 200632848085394229198405077309776409669556160755822894920478194045891524675173877582799789843512719390209285348887171584058267613825062519170949236869832740299611688879431491248560122275125138227835639875304442149679485916420376715785002453587853905329008047468218821526665318251417289791164787502264540469658007753188396466487968753988674615092615847790001421479841641921279595503860736218792224235350272376658369292603790019796500735806899786991660195728966759044116399240680328117271881207382080232786405040556863376322477213246700048245459183343930058344600346916