Perfect square in Fermat

[al3ndaleeb]

Hi everybody,

First of all I'm beginner in Math and Factorization and I hope to reach to professionals level .

My question about a perfect square in Fermat method.

At beginning I calculated X0 & P0 values from N value where:
X0 = sqrt(N) + 1
P0 = X0² - N

If P0 is not a perfect square we will add 1 to X0 and calculate P1 and
check if P1 perfect square or not and so on until finding a perfect square value.

When I calculated alot of P values, I found a strange relation between the values.
It's like this:
P1 = P0 + 2*X0 + 1
P2 = P0 + 4*X0 + 4
P3 = P0 + 6*X0 + 9
P4 = P0 + 8*X0 + 16

When I looked to the result of this equations it was identical with the first equation of P's. ( P = (X0 + number)² - N )
As you see the numbers 1, 4, 9, 16 are perfect squares and it's values came from the numbers 2, 4, 6, 8
So I created a new equation from this sequence as:

Px = P0 + F*X0 + S ................................(1)

Where
F = even numbers starts from 2 ............(2)
S = (F/2)² ...........................................(3)

also you can calculate F and S by
F = ( Px - P0 ) / X0 .........................................(4)
S = ( Px - P0 ) % X0 .......................................(5)

Where x is the sequence number.

I continued in P's calculations depend on equation (1) until F has been equal to sqrt(X0)+1 and the S changed to

S = ( sqrt(X0) + 1 )² - X0 .................................(6)

After that I continued in calculations and I failed to reach to the perfect square equation and I think the S has been changed again.

I know there is global equation for perfect square depend on iteration value
Pc = C² + 2*C*X0 + P0
Where C is the iteration value,
but I want to reach to the perfect square equation without iteration value.
So Is it possible or not ?

I appreciate any suggestion and sorry for my bad English.
Thanks.

[science_man_88]

Originally Posted by al3ndaleeb

At beginning I calculated X0 & P0 values from N value where:
X0 = sqrt(N) + 1
P0 = X0² - N

ceil(sqrt(N)) is not equivalent to sqrt(N)+1 is the first thing looking up the method again that I come to as a possible error list:


Fermat's method

ceil(x) is basically like saying floor(x)+1 so the value ceil(sqrt(n)) described means floor(sqrt(n))+1

[al3ndaleeb]

Originally Posted by science_man_88

ceil(sqrt(N)) is not equivalent to sqrt(N)+1 is the first thing looking up the method again that I come to as a possible error list:


Fermat's method

ceil(x) is basically like saying floor(x)+1 so the value ceil(sqrt(n)) described means floor(sqrt(n))+1

Thanks for reply
Because I'm working with integer values I used to write it as sqrt(x)+1.

of course I mean floor(sqrt(x))+1

[science_man_88]

Originally Posted by al3ndaleeb

Thanks for reply
Because I'm working with integer values I used to write it as sqrt(x)+1.

of course I mean floor(sqrt(x))+1

integer x doesn't guarantee integer results for sqrt(x)+1 hence why most math people on here ( I'm not a mathematician almost as far from it as you can get it turns out) notation is probably key because the way you wrote it evaluated for x = 15 for example would be 4.87......... not 4 like intended.

[al3ndaleeb]

Originally Posted by science_man_88

integer x doesn't guarantee integer results for sqrt(x)+1 hence why most math people on here ( I'm not a mathematician almost as far from it as you can get it turns out) notation is probably key because the way you wrote it evaluated for x = 15 for example would be 4.87......... not 4 like intended.

good note but what about big numbers bigger than 100 digit?

[science_man_88]

Originally Posted by al3ndaleeb

good note but what about big numbers bigger than 100 digit?

still doesn't guarantee that how you noted it if done like written would be integer take 10^100+2*10^50-1 it's one less than a perfect square but the difference between it's square root and the next numbers is less than 1 so you pass it by adding the 1. I think the conversation should start with a simpler factorization method like trial division.

[al3ndaleeb]

Hi
Today I would like to share some information's about Perfect Square in Fermat Method may be useful for researchers.

I will start with example to make the information clear.

n = 24758167959654528007156374531915464081839760935532218683689708649238085888673119

x0 = ceil(sqrt(n)) = 4975758028647949436694003969298664117473

p0 = x0² - n = 3171681298218633703780106501840055232610

c = 255922253163331858162503119755373102567 ( the step to reach to perfect square )

pc = c² + 2*x0*c + p0 = 2612310611438439659791672532150021648996360624144029624901437099031565488928481 ( our perfect square )

instead of calculate (pc) depend on the previous equation I tried to calculate non-perfect squares from every digit in (c) starting from right of (c) for example:
1st = 7² + 2*7*x0 + p0 = 72832293699289925817496162072021352877281
2nd = 67² + 2*67*x0 + p0 = 669923257137043858220776638387861046978481
3rd = 567² + 2*567*x0 + p0 = 5645681285784993294914780607686525164768481
.
.
until end of (c).

after that I calculate the difference between these non-perfect squares. for example:
1st - p0 = 69660612401071292113716055570181297644671
2nd - 1st = 597090963437753932403280476315839694101200
3rd - 2nd = 4975758028647949436694003969298664117790000
.
.
in the end I got the next list:

69660612401071292113716055570181297644671
597090963437753932403280476315839694101200
4975758028647949436694003969298664117790000
19903032114591797746776015877194656476160000

0995151605729589887338800793859732834008000000
29854548171887696620164023815791994320240000000
696606124010712921137160555701818310805600000000
2985454817188769662016402381579332332024000000000
49757580286479494366940039693015372200400000000000
497575802864794943669400396932903722004000000000000
6966061240107129211371605557585652108056000000000000
89563644515663089860492071541972669960720000000000000
099515160572958988733880079681080744400800000000000000
0995151605729589887338800807810807444008000000000000000
29854548171887696620164033534324223320240000000000000000

4975758028647949436694257089054037220040000000000000000000
19903032114591797746782028356216148880160000000000000000000
597090963437753932407180850686484466404800000000000000000000
0995151605729589887361301417810807444008000000000000000000000
79612128458367191053704113424864595520640000000000000000000000
497575802864794946985650708905403722004000000000000000000000000
7961212845836719831770411342486459552064000000000000000000000000
09951516057295901589713014178108074440080000000000000000000000000
298545481718877977691390425343242233202400000000000000000000000000
2985454817188878776913904253432422332024000000000000000000000000000
29854548171898687769139042534324223320240000000000000000000000000000
597090963441753755382780850686484466404800000000000000000000000000000
0995151605752256258971301417810807444008000000000000000000000000000000
29854548181867687769139042534324223320240000000000000000000000000000000
497575805681128129485650708905403722004000000000000000000000000000000000
1990303272724512517942602835621614888016000000000000000000000000000000000
19903037127245125179426028356216148880160000000000000000000000000000000000
199030811272451251794260283562161488801600000000000000000000000000000000000
8957214507260306330741712760297266996072000000000000000000000000000000000000
49791802818112812948565070890540372200400000000000000000000000000000000000000
500668028181128129485650708905403722004000000000000000000000000000000000000000
2052672112724512517942602835621614888016000000000000000000000000000000000000000

if you calculated the sum of this list and add (p0) on the sum you will get the perfect square value (pc).

sum of diff + p0 = Pc = 2612310611438439659791672532150021648996360624144029624901437099031565488928481

So, I have question after this try:
If I know the first digit in (c) from the right like 7 in our example
Can I reach to the next digit depend on any relation ? I see all the differences values ends in even numbers.

I hope this information was useful and I appreciate any suggestion.

Thanks

[R.D. Silverman]

Originally Posted by al3ndaleeb

Hi
Today I would like to share some information's about Perfect Square in Fermat Method may be useful for researchers.

I will start with example to make the information clear.

n = 24758167959654528007156374531915464081839760935532218683689708649238085888673119

x0 = ceil(sqrt(n)) = 4975758028647949436694003969298664117473

p0 = x0² - n = 3171681298218633703780106501840055232610

c = 255922253163331858162503119755373102567 ( the step to reach to perfect square )

pc = c² + 2*x0*c + p0 = 2612310611438439659791672532150021648996360624144029624901437099031565488928481 ( our perfect square )

instead of calculate (pc) depend on the previous equation I tried to calculate non-perfect squares from every digit in (c) starting from right of (c) for example:
1st = 7² + 2*7*x0 + p0 = 72832293699289925817496162072021352877281
2nd = 67² + 2*67*x0 + p0 = 669923257137043858220776638387861046978481
3rd = 567² + 2*567*x0 + p0 = 5645681285784993294914780607686525164768481
.
.
until end of (c).

after that I calculate the difference between these non-perfect squares. for example:
1st - p0 = 69660612401071292113716055570181297644671
2nd - 1st = 597090963437753932403280476315839694101200
3rd - 2nd = 4975758028647949436694003969298664117790000
.
.
in the end I got the next list:

69660612401071292113716055570181297644671
597090963437753932403280476315839694101200
4975758028647949436694003969298664117790000
19903032114591797746776015877194656476160000

0995151605729589887338800793859732834008000000
29854548171887696620164023815791994320240000000
696606124010712921137160555701818310805600000000
2985454817188769662016402381579332332024000000000
49757580286479494366940039693015372200400000000000
497575802864794943669400396932903722004000000000000
6966061240107129211371605557585652108056000000000000
89563644515663089860492071541972669960720000000000000
099515160572958988733880079681080744400800000000000000
0995151605729589887338800807810807444008000000000000000
29854548171887696620164033534324223320240000000000000000

4975758028647949436694257089054037220040000000000000000000
19903032114591797746782028356216148880160000000000000000000
597090963437753932407180850686484466404800000000000000000000
0995151605729589887361301417810807444008000000000000000000000
79612128458367191053704113424864595520640000000000000000000000
497575802864794946985650708905403722004000000000000000000000000
7961212845836719831770411342486459552064000000000000000000000000
09951516057295901589713014178108074440080000000000000000000000000
298545481718877977691390425343242233202400000000000000000000000000
2985454817188878776913904253432422332024000000000000000000000000000
29854548171898687769139042534324223320240000000000000000000000000000
597090963441753755382780850686484466404800000000000000000000000000000
0995151605752256258971301417810807444008000000000000000000000000000000
29854548181867687769139042534324223320240000000000000000000000000000000
497575805681128129485650708905403722004000000000000000000000000000000000
1990303272724512517942602835621614888016000000000000000000000000000000000
19903037127245125179426028356216148880160000000000000000000000000000000000
199030811272451251794260283562161488801600000000000000000000000000000000000
8957214507260306330741712760297266996072000000000000000000000000000000000000
49791802818112812948565070890540372200400000000000000000000000000000000000000
500668028181128129485650708905403722004000000000000000000000000000000000000000
2052672112724512517942602835621614888016000000000000000000000000000000000000000

if you calculated the sum of this list and add (p0) on the sum you will get the perfect square value (pc).

sum of diff + p0 = Pc = 2612310611438439659791672532150021648996360624144029624901437099031565488928481

So, I have question after this try:
If I know the first digit in (c) from the right like 7 in our example
Can I reach to the next digit depend on any relation ? I see all the differences values ends in even numbers.

I hope this information was useful and I appreciate any suggestion.

Thanks

Look up "exclusion moduli".

[danaj]

I'm having a hard time trying to figure out what you're asking / telling, but if you're looking for some info on fast perfect square detection for large numbers, I really enjoyed this post and thread from years ago:

http://mersenneforum.org/showpost.php?p=110896

[al3ndaleeb]

Originally Posted by R.D. Silverman

Look up "exclusion moduli".

Thanks for reply
I will try to use it

Originally Posted by danaj

I'm having a hard time trying to figure out what you're asking / telling, but if you're looking for some info on fast perfect square detection for large numbers, I really enjoyed this post and thread from years ago:

http://mersenneforum.org/showpost.php?p=110896

First of all
I'm very sorry if my posts was not clear.
Simply I would like to find the iteration value or the step value in another expression if we used Fermat Method.
I believe there is a hidden secret in this method.
This is what I'm talking about in this thread and thanks for link I will try to read it.

[R.D. Silverman]

Originally Posted by al3ndaleeb

Thanks for reply
I will try to use it



First of all
I'm very sorry if my posts was not clear.
Simply I would like to find the iteration value

Define 'iteration value'. Use mathematical notation, not numerology.

or the step value

Define 'step value'

in another expression if we used Fermat Method.

What other expression?

I believe there is a hidden secret in this method.

Mathematics is not done by 'belief'. What you might believe is irrelevant.

Further, your knowledge of math is so weak that you are not entitled to have a 'belief'.
You don't know enough.

Fermat's method is very very elementary. There is nothing mysterious about it, despite
your nonsense about 'hidden secret'.

Stop blathering and start READING. Knuth Vol II has a superb exposition. It has everything
one needs to know.