View Single Post
Old 2017-03-01, 04:39   #1
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

33×5×31 Posts
Default 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 clsq-comp
--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;
}
The result of the above code is:
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
The above works, but is obviously slow compared to other methods. Where I'm stuck is that there should be a way to calculate the convergence point of the progressions of the two series, instead of advancing the series and testing. That method is what I'm looking for and I'm sure someone has already worked this out, but I don't know where to look.

In my do-while 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
the lower series is:
Code:
clsq, clsq+lsqdiff, clsq+lsqdiff*2+2, clsq+lsqdiff*3+6, ...
152851285241, 152851286278, 152851287317, 152851288358, ..., 44264790806041
Knowing the starting values of hsq2 and clsq, and the element progression for each series, shouldn't I be able to calculate when/where they would be equal?

Thanks for all help...
EdH is offline   Reply With Quote