mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2017-03-05, 19:48   #12
mahbel
 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario

6010 Posts
Default Simple things to make Fermat's method more efficient

Quote:
Originally Posted by a1call View Post
Perhaps you shouldn't dismiss mahbel's remarks so quickly. I can't quite follow what he is stating but he is telling you that rather than blindly searching for squares, you can narrow your search to relevant forms.
The only numbers worth factoring as those of the form (6k+1) or (6k-1). What's left is necessarily a multiple of 2, or 3 or both. So one can find a fast and efficient way ( or algorithm) to extract the factors or 2 and 3 from a number no matter how big and at the end you end up with either a (6k+1), (6k-1) number or only factors of 2 and 3.
Now for numbers of the form (6i-1)*(6j-1)=(6k+1), the equation for N is simply
$$N+9m^2=(8+3n)^2$$ If we know the form of the squares to add to N to get another square, then we should use that fact because we can immediately ignore any square that does not have the correct form. The only problem is that there is no test ( I haven't found one ) to differentiate between pure number of the form N=(6i+1)*(6j+1)=(6k+1) and N=(6i-1)*(6j-1)=(6k+1).
And of course one can derive the correct form of the squares for numbers of the form N=(6i+1)*(6j-1).
So why waste time looking for something when we know it's not there?
mahbel is offline   Reply With Quote
Old 2017-03-05, 19:57   #13
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by mahbel View Post
The only numbers worth factoring as those of the form (6k+1) or (6k-1). What's left is necessarily a multiple of 2, or 3 or both. So one can find a fast and efficient way ( or algorithm) to extract the factors or 2 and 3 from a number no matter how big and at the end you end up with either a (6k+1), (6k-1) number or only factors of 2 and 3.
Now for numbers of the form (6i-1)*(6j-1)=(6k+1), the equation for N is simply

N+9m^2=(8+3n)^2

If we know the form of the squares to add to N to get another square, then we should use that fact because we can immediately ignore any square that does not have the correct form. The only problem is that there is no test ( I haven't found one ) to differentiate between pure number of the form N=(6i+1)*(6j+1)=(6k+1) and N=(6i-1)*(6j-1)=(6k+1).
And of course one can derive the correct form of the squares for numbers of the form N=(6i+1)*(6j-1).
So why waste time looking for something when we know it's not there?
(6i+1)(6j+1) = 36ij+6i+6j+1 = 6*(6ij+i+j)+1
(6i+1)(6j-1)= 36ij+6j-6i-1 = 6(6ij+j-i)-1
(6i-1)(6j-1) = 36ij-6j-6i+1 = 6(6ij-j-i)+1

in theory you can equate the twin prime conjecture with there are infinitely many whole numbers not fitting one of the forms in parentheses ( at the end).

Last fiddled with by science_man_88 on 2017-03-05 at 20:01
science_man_88 is offline   Reply With Quote
Old 2017-03-06, 02:11   #14
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

32·5·72 Posts
Default

Despite the Superstar association to Fermat, and despite the related Wikipedia article describing how the factorisation method is useful if used in conjunction with trial division, it seems useless compared to other possible methods. I wrote a Pari gp code which with the Fermat factorization returns a factor in about 4 s for the OP composite, compared to 4 ms with my own method. Which is still orders of magnitude slower than the built in factor() function which is insanely quick. Would love to know what sort of algo is used in the built in function, if anyone can shed some light.

Last fiddled with by a1call on 2017-03-06 at 02:12
a1call is offline   Reply With Quote
Old 2017-03-06, 02:22   #15
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by a1call View Post
Despite the Superstar association to Fermat, and despite the related Wikipedia article describing how the factorisation method is useful if used in conjunction with trial division, it seems useless compared to other possible methods. I wrote a Pari gp code which with the Fermat factorization returns a factor in about 4 s for the OP composite, compared to 4 ms with my own method. Which is still orders of magnitude slower than the built in factor() function which is insanely quick. Would love to know what sort of algo is used in the built in function, if anyone can shed some light.
?? factor and ??factorint are your friends.
science_man_88 is offline   Reply With Quote
Old 2017-03-06, 02:27   #16
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

32×5×72 Posts
Default

Well I did better I read the online documentation very carefully, there doesn't seem any mention of the actual method(s) used. except that the larger primes returned are PRPs by default.
a1call is offline   Reply With Quote
Old 2017-03-06, 02:42   #17
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by a1call View Post
Well I did better I read the online documentation very carefully, there doesn't seem any mention of the actual method(s) used. except that the larger primes returned are PRPs by default.
Trial division, perfect power detection, Shanks SQUFOF, Pollard+Brent Rho, Lenstra+Montgomery ECM, and finally MPQS. You can find this in the User's Guide (sections 1.5.4 and 3.4.33 in my copy), interactively by typing ??factorint (as sm88 suggested), or looking at the source, especially ifactor_sign and ifac_crack.
CRGreathouse is offline   Reply With Quote
Old 2017-03-06, 02:54   #18
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

89D16 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Trial division, perfect power detection, Shanks SQUFOF, Pollard+Brent Rho, Lenstra+Montgomery ECM, and finally MPQS. You can find this in the User's Guide (sections 1.5.4 and 3.4.33 in my copy), interactively by typing ??factorint (as sm88 suggested), or looking at the source, especially ifactor_sign and ifac_crack.
Thank you Mr. Greathouse for delivering the goods as usual. That is a great list to research. Only the 1st two seem obvious.

ETA The 1st hit should help the OP.

Quote:
Shanks's square forms factorization is a method for integer factorization devised by Daniel Shanks as an improvement on Fermat's factorization method.
https://en.wikipedia.org/wiki/Shanks..._factorization

ETA II, Again related to OP.:


Quote:
The naive approach to finding a congruence of squares is to pick a random number, square it, and hope the least non-negative remainder modulo n is a perfect square (in the integers). For example, 802 mod 5959 is 441, which is 212. This approach finds a congruence of squares only rarely for large n, but when it does find one, more often than not, the congruence is nontrivial and the factorization is complete. This is roughly the basis of Fermat's factorization method.
The quadratic sieve is a modification of Dixon's factorization method.
https://en.wikipedia.org/wiki/Quadratic_sieve#Basic_aim

Last fiddled with by a1call on 2017-03-06 at 03:26
a1call is offline   Reply With Quote
Old 2017-03-06, 04:27   #19
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·32·233 Posts
Default

Thank you everyone! These are what I was looking for, but couldn't figure out how to ask, efficiently.

Much appreciated!
EdH is offline   Reply With Quote
Old 2017-03-06, 15:03   #20
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

The quadratic sieve is, as the article says, essentially an improvement on Dixon's method. MPQS, which PARI uses, is an improvement on the quadratic sieve. SIQS, which PARI does not have, is an improvement on MPQS. Because of this lack PARI is not competitive at factoring numbers around, say, 60 digits. If you're doing big factorizations you're better off with yafu or the like.
CRGreathouse is offline   Reply With Quote
Old 2017-03-12, 05:21   #21
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

32×5×72 Posts
Default

Catalan's conjecture, perhaps, gives an insight into the difficulty of finding factors using Fermat method. Although there are always squares whose difference, divides any composite which has 2 factors which are either both odd or both even (but not one odd and one even), there is not always squares whose difference equals some integers such as 6 and even then there is only a finite number of them.
https://en.m.wikipedia.org/wiki/Catalan%27s_conjecture

You can expand the Fermat method to 0.5 fractions to find factors of the form one odd and one even. For example:

(5.5)^2 - (1.5)^2 | 28n

This is only of a theoretical value since it is trivial to factor even integers.

Likewise 6 can be represented as:

(3.5)^2 - (2.5)^2 = 6

Last fiddled with by a1call on 2017-03-12 at 05:59
a1call is offline   Reply With Quote
Old 2017-03-12, 08:14   #22
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

32·5·72 Posts
Default

Quote:
Originally Posted by a1call View Post
Catalan's conjecture, perhaps, gives an insight into the difficulty of finding factors using Fermat method. Although there are always squares whose difference, divides any composite which has 2 factors which are either both odd or both even (but not one odd and one even), there is not always squares whose difference equals some integers such as 6 and even then there is only a finite number of them.
https://en.m.wikipedia.org/wiki/Catalan%27s_conjecture

You can expand the Fermat method to 0.5 fractions to find factors of the form one odd and one even. For example:

(5.5)^2 - (1.5)^2 | 28n

This is only of a theoretical value since it is trivial to factor even integers.

Likewise 6 can be represented as:

(3.5)^2 - (2.5)^2 = 6
A complete list for the missing integer items in the table in the above Wikipedia link:

6 = 2.50^2-0.500^2
14 = 4.50^2-2.50^2
34 = 9.50^2-7.50^2
42 = 11.5^2-9.50^2
50 = 13.5^2-11.5^2
58 = 15.5^2-13.5^2
62 = 16.5^2-14.5^2
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
radius of convergence of a complex power series wildrabbitt Math 3 2016-08-16 08:38
Modification of Fermat's method rdotson Miscellaneous Math 0 2007-07-27 10:32
Elliptic Curve Method factoring - Fermat numbers philmoore Math 131 2006-12-18 06:27
Fermat's factoring method with Gauss's inprovement Carlos Programming 0 2005-09-11 12:50
Convergence of infinite series LoKI.GuZ Math 10 2004-11-28 03:07

All times are UTC. The time now is 04:08.


Tue Jan 25 04:08:08 UTC 2022 up 185 days, 22:37, 0 users, load averages: 1.13, 1.25, 1.33

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.

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