COP4342 - FALL 2016

Using GMP

Objectives: Learn how to use the GMP math package.

Instructions: Your assignment is modify a C program called fermat.c so that it computes a non-trivial factorization (if it exists) of an arbitrarily large composite odd number using Fermat's method. The C program fermat.c provided only computes factorizations for small odd numbers where the components stay under MAXINT.

You are to modify this program so that it uses the GMP library to compute the same factorization for arbitrarily large inputs.

To review, Fermat's method is based on the observation that an odd number N can be factored simply by observing that:

N = (x - y)(x + y)
N = x2 - y2
x2 - N = y2

This suggests that you all might have to do in an algorithm is set some variable x to the first square above N, and then iterate over increasing squares until you find an x2 - N that is a perfect square:

subroutine factor(N)
{
  x = ceiling(sqrt(N))^2
  while(!perfect_square(x^2 - N))
  {
    // try next
    x = x + 1
  }
}
return(x + sqrt(x^2 - N), x - sqrt(x^2 - N))

Your task is to convert fermat.c to a program that uses GMP for all of its calculations, and should be able to factor such numbers as

    1 69036 16637 97588 93752 56792 74360 99199 38989 63263 20951

(The above 51 digit number looks formidable, but it is a "special" number that is actually quite amenable to factorization methods based on Fermat's algorithm.)

Your work product should be a file called "fermat-new.c".