# Question:Fermat Factorization in RSA

## Question:Fermat Factorization in RSA

Maple

Suppose you know that a person's public key modulus m is the following 200 digit number :

"166571820085905498772938593207359906487315774156514145089564134\

67009247675308229223573508773729914408724747749233779284765414\

62530835296763930087228227919982503096221081674037688617693027\

1167988018683"

Factor m and check your factorization after the factors are found.  Use the following Fermat factorization method:  Note that if
"m = x^2 - y^2"

then
"m = (x - y)*(x + y)"

. So if
"1 < x - y"

we have a non-trivial factorization of m. If m is a product of just two primes then one will be
"x - y"

and the other will be x + y.  This is the basis of the Fermat factorization method. Note that
"m = x^2 - y^2"

is equivalent to
"x^2 - m = y^2"

.  So if for some number x we have type(sqrt(x^2 - m),integer) = true then we can set y = sqrt(x^2 - m) and using the above idea we may factor m.  Fermat's method is to take x =
"ceil(sqrt(m))"

and keep incrementing x by 1 till an x is found such that
"x^2 - m"

is a square.   [Note that you may need to use ceil(evalf(sqrt(m),200)).]

If the number m is a product of two primes that are relatively close together then this method will factor m quickly. If you do not find the factors in just a few seconds, you probably have a bug in your program. For some reason Maple does not have this method builtin.

[N.B. This exercise shows that if care is not taken in choosing the primes p and q used in the RSA system, than the system can be easily broken

﻿