mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2017-08-02, 08:48   #1
serg2017
 
Aug 2017

3 Posts
Default 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 ?
serg2017 is offline   Reply With Quote
Old 2017-08-02, 14:32   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

Quote:
Originally Posted by serg2017 View Post
Can it help for factorization c1133 ?
No.
CRGreathouse is offline   Reply With Quote
Old 2017-10-13, 10:10   #3
serg2017
 
Aug 2017

3 Posts
Default

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?
serg2017 is offline   Reply With Quote
Old 2017-10-13, 12:25   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

56458 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2017-10-13, 12:54   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26128 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2017-10-13, 13:20   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

11×271 Posts
Default

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
ATH is offline   Reply With Quote
Old 2017-10-13, 13:47   #7
axn
 
axn's Avatar
 
Jun 2003

22·5·239 Posts
Default

Quote:
Originally Posted by serg2017 View Post
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?
axn is offline   Reply With Quote
Old 2017-10-13, 14:03   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×953 Posts
Default

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
Dr Sardonicus is online now   Reply With Quote
Old 2017-10-13, 14:39   #9
serg2017
 
Aug 2017

3 Posts
Default

Quote:
Originally Posted by axn View Post
Why the weird poly? Why not simply m^4+1, m=2^32?
We can use more than one value for m
serg2017 is offline   Reply With Quote
Old 2017-10-13, 15:06   #10
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·2,243 Posts
Default

Quote:
Originally Posted by serg2017 View Post
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.
VBCurtis is offline   Reply With Quote
Old 2017-10-14, 01:59   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·167 Posts
Default

Quote:
Originally Posted by serg2017 View Post
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
alpertron is online now   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 02:19.

Sun Nov 29 02:19:35 UTC 2020 up 79 days, 23:30, 3 users, load averages: 1.02, 1.27, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.