Fermats Factorizing method

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 n.
Fermat’s factorization methods look for integers x and y such that n=x^2-y^2. Then it can be represented as

 n=(x-y)(x+y)
(1)

and n is factored.

Every positive odd integer can be represented in the form n=x^2-y^2 by writing n=ab (with a>b) and noting that this gives

a = x+y
(2)
b = x-y.
(3)

Adding and subtracting,

a+b = 2x
(4)
a-b = 2y,
(5)

so solving for x and y gives

x = 1/2(a+b)
(6)
y = 1/2(a-b).
(7)

Therefore,

 x^2-y^2=1/4[(a+b)^2-(a-b)^2]=ab.

Consider an example:

Let, n=15
So, n can be represented as:

n=4^2 – 1^2

n=(4+1)(4-1) = 5*3
a=4+1
b=4-1
a+b=2*4
a-b=2*1
x=4
y=1
x=1/2(a+b) = 4
y=1/2(a-b) = 1
x^2 – y^2 = 16 – 1 = 15 = ab.

source: http://mathworld.wolfram.com/FermatsFactorizationMethod.html

Advertisements

Tagged:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s