20170305, 19:48  #12  
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario
60_{10} Posts 
Simple things to make Fermat's method more efficient
Quote:
Now for numbers of the form (6i1)*(6j1)=(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=(6i1)*(6j1)=(6k+1). And of course one can derive the correct form of the squares for numbers of the form N=(6i+1)*(6j1). So why waste time looking for something when we know it's not there? 

20170305, 19:57  #13  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
(6i+1)(6j1)= 36ij+6j6i1 = 6(6ij+ji)1 (6i1)(6j1) = 36ij6j6i+1 = 6(6ijji)+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 20170305 at 20:01 

20170306, 02:11  #14 
"Rashid Naimi"
Oct 2015
Remote to Here/There
3^{2}·5·7^{2} 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 20170306 at 02:12 
20170306, 02:22  #15  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:


20170306, 02:27  #16 
"Rashid Naimi"
Oct 2015
Remote to Here/There
3^{2}×5×7^{2} 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.

20170306, 02:42  #17  
Aug 2006
3×1,993 Posts 
Quote:


20170306, 02:54  #18  
"Rashid Naimi"
Oct 2015
Remote to Here/There
89D_{16} Posts 
Quote:
ETA The 1st hit should help the OP. Quote:
ETA II, Again related to OP.: Quote:
Last fiddled with by a1call on 20170306 at 03:26 

20170306, 04:27  #19 
"Ed Hall"
Dec 2009
Adirondack Mtns
2·3^{2}·233 Posts 
Thank you everyone! These are what I was looking for, but couldn't figure out how to ask, efficiently.
Much appreciated! 
20170306, 15:03  #20 
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.

20170312, 05:21  #21 
"Rashid Naimi"
Oct 2015
Remote to Here/There
3^{2}×5×7^{2} 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 20170312 at 05:59 
20170312, 08:14  #22  
"Rashid Naimi"
Oct 2015
Remote to Here/There
3^{2}·5·7^{2} Posts 
Quote:
6 = 2.50^20.500^2 14 = 4.50^22.50^2 34 = 9.50^27.50^2 42 = 11.5^29.50^2 50 = 13.5^211.5^2 58 = 15.5^213.5^2 62 = 16.5^214.5^2 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
radius of convergence of a complex power series  wildrabbitt  Math  3  20160816 08:38 
Modification of Fermat's method  rdotson  Miscellaneous Math  0  20070727 10:32 
Elliptic Curve Method factoring  Fermat numbers  philmoore  Math  131  20061218 06:27 
Fermat's factoring method with Gauss's inprovement  Carlos  Programming  0  20050911 12:50 
Convergence of infinite series  LoKI.GuZ  Math  10  20041128 03:07 