mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-06-24, 20:18   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·11·103 Posts
Default 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.
a1call is offline   Reply With Quote
Old 2022-06-24, 21:39   #2
charybdis
 
charybdis's Avatar
 
Apr 2020

14358 Posts
Default

Quote:
Originally Posted by a1call View Post
What method would be ideal for factoring say:

Code:
6281316756600375138979450760417229861125568223203259505512810775373873695935867806186889688171270951007172871039770744372957515829909725294130442497572043506353805580320667681464965319713467399242353302628481120519996693477157642385509498655453869505337844554641216204374957680552415362421838944208142335431588371274692587373543194663115987968177705112806593810425091226345543119831729026254522772400547525984518164758938560208388817668492083225434164484920438568881134231643421126924977098576842117761359812889876973212540837879373073066027458947148176704199805117011
=
79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143014656281293986085422447616048193476466358247318858203179152407921243360061125374826607259060650540627831264217954326876841746735963052061076691
*
79254758573857097700478009025030817882051675212183337150958069783000695646635088221089422593502252435333422573966318781905393111546629162143005753767122480538321576709096742366054307138157365525349302375042767063068755221561296769468805213900014005910021487510023263479824298570171521
Fermat's method. It works on the first try.
charybdis is offline   Reply With Quote
Old 2022-06-24, 21:48   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×11×103 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2022-06-24, 23:19   #4
charybdis
 
charybdis's Avatar
 
Apr 2020

31D16 Posts
Default

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).
charybdis is offline   Reply With Quote
Old 2022-06-24, 23:25   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·11·103 Posts
Default

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?
a1call is offline   Reply With Quote
Old 2022-06-24, 23:29   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·11·103 Posts
Default

Quote:
Originally Posted by charybdis View Post
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.
a1call is offline   Reply With Quote
Old 2022-06-25, 00:12   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×11×103 Posts
Default

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.
a1call is offline   Reply With Quote
Old 2022-06-25, 01:24   #8
charybdis
 
charybdis's Avatar
 
Apr 2020

79710 Posts
Default

Quote:
Originally Posted by a1call View Post
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 View Post
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.
charybdis is offline   Reply With Quote
Old 2022-06-25, 02:25   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·11·103 Posts
Default

You are a very wise person charybdis.

Thank you very much for your replies and nice to have you back.
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring semiprimes with restricted Rho method mgb Computer Science & Computational Number Theory 45 2019-08-05 20:02
Factoring n via factors of n-1 or n+1 a1call Miscellaneous Math 63 2018-03-06 09:39
Semiprimes factoring. Is deterministic? What is computational complexity? Alberico Lepore Alberico Lepore 43 2017-06-10 15:42
Semiprimes Hian Homework Help 15 2011-05-29 23:48
Factoring semiprimes robert44444uk Math 34 2007-07-19 17:23

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


Fri Aug 12 00:19:00 UTC 2022 up 35 days, 19:06, 2 users, load averages: 1.39, 1.50, 1.28

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔