This is a really nice algorithm to find out factors of an odd integer, which could be represented as the difference
between two squares. This algorithm works even when n is a large integer. So, this could be an easy way to determine p and q in RSA decryption when n is sufficiently large.
Method:
Given a number .
Fermat’s factorization methods look for integers and such that . Then it can be represented as
(1)

and is factored.
Every positive odd integer can be represented in the form by writing (with ) and noting that this gives
(2)


(3)

Adding and subtracting,
(4)


(5)

so solving for and gives
(6)


(7)

Therefore,
Consider an example:
Let, n=15
So, n can be represented as:n=4^2 – 1^2
n=(4+1)(41) = 5*3
a=4+1
b=41
a+b=2*4
ab=2*1
x=4
y=1
x=1/2(a+b) = 4
y=1/2(ab) = 1
x^2 – y^2 = 16 – 1 = 15 = ab.
source: http://mathworld.wolfram.com/FermatsFactorizationMethod.html
Tagged: math stuffs
Leave a Reply