mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Other Mathematical Topics (https://www.mersenneforum.org/forumdisplay.php?f=117)
-   -   Help with series convergence in Fermat method of factoring (https://www.mersenneforum.org/showthread.php?t=22093)

 EdH 2017-03-01 04:39

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:

-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)

{start of loop}
-compare clsq with hsq2 (check)

--if check == 0, the two squares are hsq2 and clsq-comp
--break loop

--if check >0
---go back to start of loop

--if check <0
---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_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_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);

gmp_printf("clsq is: %Zd\n", clsq);

do{
//compare sum of lsq2 and comp with hsq2
check=mpz_cmp(clsq, hsq2);

if (check>0){
}
if (check<0){
}
}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_sub(factor2, sqrt2, sqrt);
gmp_printf("The factors are %Zd and %Zd\n", factor1, factor2);

return 0;
}
[/code]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
[/code]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
[/code]the lower series is:
[code]
clsq, clsq+lsqdiff, clsq+lsqdiff*2+2, clsq+lsqdiff*3+6, ...
152851285241, 152851286278, 152851287317, 152851288358, ..., 44264790806041
[/code]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...

 mahbel 2017-03-01 19:20

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.

 EdH 2017-03-01 23:09

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.

 fivemack 2017-03-02 18:05

[QUOTE=EdH;454019]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[/quote]

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 possible-square-mod-p 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.

 EdH 2017-03-02 23:58

[QUOTE=fivemack;454125]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 possible-square-mod-p 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.[/QUOTE]
Thanks fivemack, but I realize that I can do addition/testing for a long time to find the right lower square. I'm looking for a way to calculate the coincidence rather than stepping to it, which would take a thousand years for some of the larger composites. I've been trying to see if I can find a way via modular means, but I'm too darn rusty with any background in math I may have had long ago. Maybe there isn't a way to do what I'm looking for and that's why I can't find it.

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.

 fivemack 2017-03-03 07:58

[QUOTE=EdH;454149]Thanks fivemack, but I realize that I can do addition/testing for a long time to find the right lower square. I'm looking for a way to calculate the coincidence rather than stepping to it, which would take a thousand years for some of the larger composites.[/quote]

If you were stepping along the two sequences in perfect sequence, it's just a problem in quadratic equations; but the variable stepping rates make it much more difficult.

You're looking for a point on the conic Y^2-N=X^2, and there are good ways to do this iff you know the factorisation of N :)

 EdH 2017-03-03 14:32

[QUOTE=fivemack;454167]If you were stepping along the two sequences in perfect sequence, it's just a problem in quadratic equations; but the variable stepping rates make it much more difficult.

You're looking for a point on the conic Y^2-N=X^2, and there are good ways to do this iff you know the factorisation of N :)[/QUOTE]
Thanks fivemack! This gives me an area for my next study...

 a1call 2017-03-05 16:31

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,
5-2 | 21=5^2-2^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^5-m^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 sub-power factors that can be built as intelligence into the search.

The Mersenne numbers are a subset of this rule of the form:

2^n-1^m | 2^(nj)-1^(mj)

 EdH 2017-03-05 16:46

[QUOTE=a1call;454290]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,
5-2 | 21=5^2-2^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^5-m^3 | n^(5j)-m(3j)
3 and 5 are arbitrary and can be replaced by any integers.
But generally there is a commonality to the form of the composite candidate and it's sub-power factors that can be built as intelligence into the search.

The Mersenne numbers are a subset of this rule of the form:

2^n-1^m | 2^(nj)-1^(mj)[/QUOTE]Thank you for your post. I'm not tossing everything aside, but I am trying to find something that doesn't really involve filtering search criteria, per se. It would seem that even though he shows a way to reduce the search squares, there will still be too many to effectively test each one for larger composites. As for size issues, I'm currently playing with a grid of numbers based from 0 through 1600 and am learning some very interesting (to me) things.

Thank you very much for your post.

 science_man_88 2017-03-05 17:14

[QUOTE=EdH;454292]Thank you for your post. I'm not tossing everything aside, but I am trying to find something that doesn't really involve filtering search criteria, per se. It would seem that even though he shows a way to reduce the search squares, there will still be too many to effectively test each one for larger composites. As for size issues, I'm currently playing with a grid of numbers based from 0 through 1600 and am learning some very interesting (to me) things.

Thank you very much for your post.[/QUOTE]

at least fermat's idea isn't brute forcing the values such that 2kj+k+j = l such that 2l+1 = N like an inverse to the sieve of sundaram.

 science_man_88 2017-03-05 19:46

if N=p*q then N= ((p+q)/2)^2-((p-q)/2)^2 of course but without p and q these formulae are pointless.

All times are UTC. The time now is 19:48.