Question: Fermat Factorization in RSA

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




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"

                     "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 = 

 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

Please Wait...