20170301, 04:39  #1 
"Ed Hall"
Dec 2009
Adirondack Mtns
FA1_{16} Posts 
Help with series convergence in Fermat method of factoring
First my apologies for not having the background to point to the previous works, which would allow me to find what I'm searching for a bit easier. I'm using a procedure based on Fermat's factorization method, but I'm searching for the squares by using the sums of the intervals of squares. Anyway, this is a little different look at the difference of two squares and I'm stuck.
I know that If I take a composite that is made up of two primes I can find those primes using the two squares which differ by the composite. However, finding the two squares is the difficult part as the numbers get larger. I have an example C++ program further on. The variables in parentheses refer to the variables in the later program. By using the following method, the appropriate squares can be found: start with a composite (comp) find the closest squares below and above comp (hsq1 and hsq2, respectively) find the difference between hsq1 and hsq2 (hsqdiff) find the difference between hsq2 and comp (cdiff) find the closest two squares below and above cdiff (lsq1 and lsq2, respectively) find the difference between lsq1 and lsq2 (lsqdiff) add comp to lsq1 (clsq) {start of loop} compare clsq with hsq2 (check) if check == 0, the two squares are hsq2 and clsqcomp break loop if check >0 add 2 to hsqdiff (hsqdiff) add hsqdiff to hsq2 go back to start of loop if check <0 add lsqdiff to clsq add 2 to lsqdiff (lsqdiff) go back to start of loop {end of loop} A working c++ example: Code:
#include <iostream> #include <gmp.h> using namespace std; int main() { mpz_t one, two, comp, hsq1, hsq2, hsqdiff, cdiff, lsq1, lsq2, lsqdiff, clsq, sqrt, sqrt2, factor1, factor2; mpz_inits(one, two, comp, hsq1, hsq2, hsqdiff, cdiff, lsq1, lsq2, lsqdiff, clsq, sqrt, sqrt2, factor1, factor2, NULL); int check; //initialize comp and two static variables mpz_set_str(comp, "152851016917", 10); mpz_set_str(one, "1", 10); mpz_set_str(two, "2", 10); gmp_printf("comp is: %Zd\n", comp); //find closest squares below and above comp mpz_sqrt(sqrt, comp); mpz_mul(hsq1, sqrt, sqrt); mpz_add(sqrt, sqrt, one); mpz_mul(hsq2, sqrt, sqrt); gmp_printf("hsq1 is: %Zd and hsq2 is: %Zd\n", hsq1, hsq2); //find difference between hsq1 and hsq2 mpz_sub(hsqdiff, hsq2, hsq1); gmp_printf("The difference between hsq2 and hsq1 is: %Zd\n", hsqdiff); //find difference between hsq2 and comp mpz_sub(cdiff, hsq2, comp); gmp_printf("The difference between hsq2 and comp is: %Zd\n", cdiff); //find closest squares below and above cdiff mpz_sqrt(sqrt, cdiff); mpz_mul(lsq1, sqrt, sqrt); mpz_add(sqrt, sqrt, one); mpz_mul(lsq2, sqrt, sqrt); gmp_printf("lsq1 is: %Zd and lsq2 is: %Zd\n", lsq1, lsq2); //find difference between lsq1 and lsq2 mpz_sub(lsqdiff, lsq2, lsq1); gmp_printf("The difference between lsq2 and lsq1 is: %Zd\n", lsqdiff); //add comp to lsq1 mpz_add(clsq, comp, lsq1); gmp_printf("clsq is: %Zd\n", clsq); //loop to advance squares do{ //compare sum of lsq2 and comp with hsq2 check=mpz_cmp(clsq, hsq2); if (check>0){ mpz_add(hsqdiff, hsqdiff, two); mpz_add(hsq2, hsq2, hsqdiff); } if (check<0){ mpz_add(clsq, clsq, lsqdiff); mpz_add(lsqdiff, lsqdiff, two); } }while (check!=0); //retrieve low square mpz_sub(lsq2, clsq, comp); gmp_printf("The high square is: %Zd and the low square is: %Zd\n", hsq2, lsq2); //get square roots mpz_sqrt(sqrt2, hsq2); mpz_sqrt(sqrt, lsq2); gmp_printf("The square roots are %Zd and %Zd\n", sqrt, sqrt2); //calculate factors mpz_add(factor1, sqrt2, sqrt); mpz_sub(factor2, sqrt2, sqrt); gmp_printf("The factors are %Zd and %Zd\n", factor1, factor2); return 0; } Code:
comp is: 152851016917 hsq1 is: 152850503521 and hsq2 is: 152851285444 The difference between hsq2 and hsq1 is: 781923 The difference between hsq2 and comp is: 268527 lsq1 is: 268324 and lsq2 is: 269361 The difference between lsq2 and lsq1 is: 1037 clsq is: 152851285241 The high square is: 44264790806041 and the low square is: 44111939789124 The square roots are 6641682 and 6653179 The factors are 13294861 and 11497 In my dowhile loop, I'm simply advancing the lower series by square differences and once the value has surpassed the high square, I advance the high square to the next square. The difference swings above and below 0, until at some point it equals 0. This zero point is what I'm looking for, but instead of stepping to that point, I'd like to calculate that point based on the series' intervals. The reason I'm having trouble is that the intervals increase by 2 for each step and the smaller series is increasing by smaller, more frequent steps. In practice, using the above example, the higher series is: Code:
hsq2, hsq2+hsqdiff+2, hsq2+hsqdiff*2+6, hsq2+hsqdiff*3+12, ... 152851285444, 152852067369, 152852849296, 152853631225, ..., 44264790806041 Code:
clsq, clsq+lsqdiff, clsq+lsqdiff*2+2, clsq+lsqdiff*3+6, ... 152851285241, 152851286278, 152851287317, 152851288358, ..., 44264790806041 Thanks for all help... 
20170301, 19:20  #2 
"mahfoud belhadj"
Feb 2017
Kitchener, Ontario
2^{2}·3·5 Posts 
I don't know how helpful the following is but your number N=152851016917 is a (6k+1) type of number. So the squares in N + n^2 = m^2 must be of the following form: n=3k and m=10+3j. Then your number becomes N + 9k^2 = (10+3j)^2. You obviously don't need to start with m=10. You get the starting point from the sqrt(N). That is if your number is 217=7*31, your starting point is m=10+3=13 because 13^2 is the first square of the correct from below 217. This will allow you to discard a lot of squares that do not have the right form. The other simple trick is the fact that N and m^2 must have have the same sum of digits. In the case of N=217, you can jump straight to m^2=19^2 since 13^2 and 16^2 do not have the same sum of digits. Good luck to you.

20170301, 23:09  #3 
"Ed Hall"
Dec 2009
Adirondack Mtns
4,001 Posts 
Thanks for the reply. I'm more interested in the general concept than specific forms of composites right now. The number chosen was simply a composite that only had two primes and was handy. But, thank you for the effort in responding.

20170302, 18:05  #4 
(loop (#_fork))
Feb 2006
Cambridge, England
1100100101001_{2} Posts 
You don't need the lower series  you just need to advance the high series until the difference is _some_ square, and checking whether a number is a square isn't too difficult. If a number is a possiblesquaremodp for lots of p, it's pretty likely to be square, and each p rules out about half the numbers ... you can keep track of the values of the high series modulo lots of p quite efficiently since you're only doing addition.

20170302, 23:58  #5  
"Ed Hall"
Dec 2009
Adirondack Mtns
4,001 Posts 
Quote:
In a way, I'm picturing two graphs converging to the crossover, but the two series are really just two sections of the same graph, without the composite offset. If I can "visualize" a way to work this, maybe a function can be derived. I suspect, that function already is known by everyone, but I don't know enough to describe it properly or recognize it, yet. Thank you very much for all your help. 

20170303, 07:58  #6  
(loop (#_fork))
Feb 2006
Cambridge, England
3×19×113 Posts 
Quote:
You're looking for a point on the conic Y^2N=X^2, and there are good ways to do this iff you know the factorisation of N :) 

20170303, 14:32  #7  
"Ed Hall"
Dec 2009
Adirondack Mtns
4,001 Posts 
Quote:


20170305, 16:31  #8 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·5^{2}·43 Posts 
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.
It also helps to analyze routines with small numeric examples instead of astronomically large ones. Suppose you want to factor 21, 52  21=5^22^2 You could build some intelligence into your search by knowing effective ranges and rules. You could also extend your search to powers other than 2. For example: n^5m^3  n^(5j)m(3j) 3 and 5 are arbitrary and can be replaced by any integers (or primes if you prefer). But generally there is a commonality to the form of the composite candidate and it's subpower factors that can be built as intelligence into the search. The Mersenne numbers are a subset of this rule of the form: 2^n1^m  2^(nj)1^(mj) Last fiddled with by a1call on 20170305 at 16:37 
20170305, 16:46  #9  
"Ed Hall"
Dec 2009
Adirondack Mtns
4,001 Posts 
Quote:
Thank you very much for your post. 

20170305, 17:14  #10  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:


20170305, 19:46  #11 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
if N=p*q then N= ((p+q)/2)^2((pq)/2)^2 of course but without p and q these formulae are pointless.

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 