mersenneforum.org Help with series convergence in Fermat method of factoring
 Register FAQ Search Today's Posts Mark Forums Read

2017-03-05, 19:48   #12
mahbel

Feb 2017
Kitchener, Ontario

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

Quote:
 Originally Posted by a1call 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?

2017-03-05, 19:57   #13
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by mahbel 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

 2017-03-06, 02:11 #14 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 32·5·72 Posts 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
2017-03-06, 02:22   #15
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by a1call 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.

 2017-03-06, 02:27 #16 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 32×5×72 Posts 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.
2017-03-06, 02:42   #17
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by a1call 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.

2017-03-06, 02:54   #18
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

89D16 Posts

Quote:
 Originally Posted by CRGreathouse 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.

Last fiddled with by a1call on 2017-03-06 at 03:26

 2017-03-06, 04:27 #19 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 2·32·233 Posts Thank you everyone! These are what I was looking for, but couldn't figure out how to ask, efficiently. Much appreciated!
 2017-03-06, 15:03 #20 CRGreathouse     Aug 2006 3×1,993 Posts 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.
 2017-03-12, 05:21 #21 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 32×5×72 Posts 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
2017-03-12, 08:14   #22
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

32·5·72 Posts

Quote:
 Originally Posted by a1call 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

 Similar Threads Thread Thread Starter Forum Replies Last Post wildrabbitt Math 3 2016-08-16 08:38 rdotson Miscellaneous Math 0 2007-07-27 10:32 philmoore Math 131 2006-12-18 06:27 Carlos Programming 0 2005-09-11 12:50 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