mersenneforum.org factoring Semiprimes with Proximal factors
 Register FAQ Search Today's Posts Mark Forums Read

 2022-06-24, 20:18 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×1,153 Posts factoring Semiprimes with Proximal factors I believe that Fermat's factorization method is ideal for factoring composites with factors that are of about the same size. This is why encryption semiprimes use factors that are Proximal but not too close to be easily factored using Fermat's method. However, Fermat's method involves multitudes of trials, which makes it too slow for very large integers. Is there a faster alternative for factoring composites with Proximal factors? What method would be ideal for factoring say: Code: 6281316756600375138979450760417229861125568223203259505512810775373873695935867806186889688171270951007172871039770744372957515829909725294130442497572043506353805580320667681464965319713467399242353302628481120519996693477157642385509498655453869505337844554641216204374957680552415362421838944208142335431588371274692587373543194663115987968177705112806593810425091226345543119831729026254522772400547525984518164758938560208388817668492083225434164484920438568881134231643421126924977098576842117761359812889876973212540837879373073066027458947148176704199805117011 = 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143014656281293986085422447616048193476466358247318858203179152407921243360061125374826607259060650540627831264217954326876841746735963052061076691 * 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143005753767122480538321576709096742366054307138157365525349302375042767063068755221561296769468805213900014005910021487510023263479824298570171521 Thanks in advance.
2022-06-24, 21:39   #2
charybdis

Apr 2020

53·7 Posts

Quote:
 Originally Posted by a1call What method would be ideal for factoring say: Code: 6281316756600375138979450760417229861125568223203259505512810775373873695935867806186889688171270951007172871039770744372957515829909725294130442497572043506353805580320667681464965319713467399242353302628481120519996693477157642385509498655453869505337844554641216204374957680552415362421838944208142335431588371274692587373543194663115987968177705112806593810425091226345543119831729026254522772400547525984518164758938560208388817668492083225434164484920438568881134231643421126924977098576842117761359812889876973212540837879373073066027458947148176704199805117011 = 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143014656281293986085422447616048193476466358247318858203179152407921243360061125374826607259060650540627831264217954326876841746735963052061076691 * 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143005753767122480538321576709096742366054307138157365525349302375042767063068755221561296769468805213900014005910021487510023263479824298570171521
Fermat's method. It works on the first try.

 2022-06-24, 21:48 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×1,153 Posts Thank you very much for the info. As you well know I am not very knowledgeable in factoring. Did you use a ready made factoring software or a calculator such as Pari? Did you hit the squares on the 1st try? Again thanks for your time.
 2022-06-24, 23:19 #4 charybdis     Apr 2020 53×7 Posts I used PARI: Code: gp > \p 400 realprecision = 404 significant digits (400 digits displayed) gp > N=6281316756600375138979450760417229861125568223203259505512810775373873695935867806186889688171270951007172871039770744372957515829909725294130442497572043506353805580320667681464965319713467399242353302628481120519996693477157642385509498655453869505337844554641216204374957680552415362421838944208142335431588371274692587373543194663115987968177705112806593810425091226345543119831729026254522772400547525984518164758938560208388817668492083225434164484920438568881134231643421126924977098576842117761359812889876973212540837879373073066027458947148176704199805117011 %1 = 6281316756600375138979450760417229861125568223203259505512810775373873695935867806186889688171270951007172871039770744372957515829909725294130442497572043506353805580320667681464965319713467399242353302628481120519996693477157642385509498655453869505337844554641216204374957680552415362421838944208142335431588371274692587373543194663115987968177705112806593810425091226345543119831729026254522772400547525984518164758938560208388817668492083225434164484920438568881134231643421126924977098576842117761359812889876973212540837879373073066027458947148176704199805117011 gp > m=ceil(sqrt(N)) <-- finds smallest number whose square is greater than N %2 = 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143010205024208233311872012162572467921260332692738111864264227391482005211564940298193952014264727877263922635063987907193432505107893675315624106 gp > issquare(m^2-N,&s) <-- checks if m^2-N is a square, and sets s equal to the square root if it is %3 = 1 gp > m-s %4 = 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143005753767122480538321576709096742366054307138157365525349302375042767063068755221561296769468805213900014005910021487510023263479824298570171521 gp > m+s %5 = 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143014656281293986085422447616048193476466358247318858203179152407921243360061125374826607259060650540627831264217954326876841746735963052061076691 The difference between N and the first square above N is a square, so Fermat works on the first try. Fermat will always work on the first try if N has a factor that is within N^(1/4) of sqrt(N).
 2022-06-24, 23:25 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 44028 Posts Well I tried the following calculators on a similar but much smaller and web-friendly integer without any success: Code: 37598509921358937130067447226996383490394965883350770227491949626316296206227551680872850721799316915254863210166862451532957886446390226981 = 6131762382982476362788562753503495138812658361807492968973779515889901 * 6131762382982476362788562753503495060507087787406616806191258317645081 PARI-GP: Code: factor(37598509921358937130067447226996383490394965883350770227491949626316296206227551680872850721799316915254863210166862451532957886446390226981) https://www.wolframalpha.com/input?i...86446390226981 http://www.socr.ucla.edu/Applets.dir...mposition.html Don't any of them use Fermat's factorization method at all?
2022-06-24, 23:29   #6
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

230610 Posts

Quote:
 Originally Posted by charybdis I used PARI: Code: gp > \p 400 realprecision = 404 significant digits (400 digits displayed) gp > N=6281316756600375138979450760417229861125568223203259505512810775373873695935867806186889688171270951007172871039770744372957515829909725294130442497572043506353805580320667681464965319713467399242353302628481120519996693477157642385509498655453869505337844554641216204374957680552415362421838944208142335431588371274692587373543194663115987968177705112806593810425091226345543119831729026254522772400547525984518164758938560208388817668492083225434164484920438568881134231643421126924977098576842117761359812889876973212540837879373073066027458947148176704199805117011 %1 = 6281316756600375138979450760417229861125568223203259505512810775373873695935867806186889688171270951007172871039770744372957515829909725294130442497572043506353805580320667681464965319713467399242353302628481120519996693477157642385509498655453869505337844554641216204374957680552415362421838944208142335431588371274692587373543194663115987968177705112806593810425091226345543119831729026254522772400547525984518164758938560208388817668492083225434164484920438568881134231643421126924977098576842117761359812889876973212540837879373073066027458947148176704199805117011 gp > m=ceil(sqrt(N)) <-- finds smallest number whose square is greater than N %2 = 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143010205024208233311872012162572467921260332692738111864264227391482005211564940298193952014264727877263922635063987907193432505107893675315624106 gp > issquare(m^2-N,&s) <-- checks if m^2-N is a square, and sets s equal to the square root if it is %3 = 1 gp > m-s %4 = 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143005753767122480538321576709096742366054307138157365525349302375042767063068755221561296769468805213900014005910021487510023263479824298570171521 gp > m+s %5 = 79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143014656281293986085422447616048193476466358247318858203179152407921243360061125374826607259060650540627831264217954326876841746735963052061076691 The difference between N and the first square above N is a square, so Fermat works on the first try. Fermat will always work on the first try if N has a factor that is within N^(1/4) of sqrt(N).

Yes of course, silly of me not to check that before asking.
Thanks.

 2022-06-25, 00:12 #7 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,153 Posts So here is a follow-up question. Knowing that semiprimes with proximal factors can be easily factored, isn't there a potential method of multiplying a complimentary integer to N that would result in an integer with factors that are less than sqrt(sqrt(newN)) apart? Say repeatedly multiplying numbers of the form a*(a+1) with incrementing a-value at each iteration or something similar? Wouldn't the prohibitive(read-impractical) repeated squaring of N achieve the same? Thank you for your thoughts and insights.
2022-06-25, 01:24   #8
charybdis

Apr 2020

53×7 Posts

Quote:
 Originally Posted by a1call Well I tried the following calculators on a similar but much smaller and web-friendly integer without any success: ... PARI-GP: Code: factor(37598509921358937130067447226996383490394965883350770227491949626316296206227551680872850721799316915254863210166862451532957886446390226981) https://www.wolframalpha.com/input?i...86446390226981 http://www.socr.ucla.edu/Applets.dir...mposition.html Don't any of them use Fermat's factorization method at all?
Well apparently they don't. Yafu does:

Code:
\$ yafu "factor(37598509921358937130067447226996383490394965883350770227491949626316296206227551680872850721799316915254863210166862451532957886446390226981)"

fac: factoring 37598509921358937130067447226996383490394965883350770227491949626316296206227551680872850721799316915254863210166862451532957886446390226981
fac: using pretesting plan: custom
fac: custom pretest ratio is: 0.3200
fac: using specified qs/gnfs crossover of 98 digits
fac: using specified qs/snfs crossover of 75 digits
div: primes less than 10000
fmt: 1000000 iterations
Total factoring time = 0.1078 seconds

***factors found***

P70 = 6131762382982476362788562753503495138812658361807492968973779515889901
P70 = 6131762382982476362788562753503495060507087787406616806191258317645081
Quote:
 Originally Posted by a1call So here is a follow-up question. Knowing that semiprimes with proximal factors can be easily factored, isn't there a potential method of multiplying a complimentary integer to N that would result in an integer with factors that are less than sqrt(sqrt(newN)) apart? Say repeatedly multiplying numbers of the form a*(a+1) with incrementing a-value at each iteration or something similar? Wouldn't the prohibitive(read-impractical) repeated squaring of N achieve the same? Thank you for your thoughts and insights.
No, this won't work. You can certainly get a number that Fermat will factor, but of course that's easy: just multiply N by N+2 and Fermat will factor it into N and N+2 on the first attempt. As you can see, that does not help us factor N.

If n = pq, what we would need is to multiply N by some number a = bc such that bp and cq are very close together and so Fermat will work. But we can't do this without knowing what p and q are to start with.

 2022-06-25, 02:25 #9 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,153 Posts You are a very wise person charybdis. Thank you very much for your replies and nice to have you back.

 Similar Threads Thread Thread Starter Forum Replies Last Post mgb Computer Science & Computational Number Theory 45 2019-08-05 20:02 a1call Miscellaneous Math 63 2018-03-06 09:39 Alberico Lepore Alberico Lepore 43 2017-06-10 15:42 Hian Homework Help 15 2011-05-29 23:48 robert44444uk Math 34 2007-07-19 17:23

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

Thu Dec 1 13:17:21 UTC 2022 up 105 days, 10:45, 1 user, load averages: 1.52, 1.28, 1.15