Fermat's Factorization Method

Date: 01/29/99 at 15:22:57
From: Karthick
Subject: Number theory, Fermat's factorisation methord.

I remember reading somewhere that Fermat devised a rule for 
factorising that works well if the factors are close. You take the 
integer part of the square root of the number to be factorised, form a 
series with it, and continue until some term becomes an integer.

All this happened when I was trying to factorise 99899. Can you help 
me with this? And provide the general method as well?

Thanks in advance.

Date: 01/29/99 at 17:04:59
From: Doctor Rob
Subject: Re: Number theory, Fermat's factorisation methord.

Thanks for writing to Ask Dr. Math!

You remember Fermat's Method well as far as you got. To factor N, start 
with the next integer a0 not smaller than its square root. Square that 
and subtract N, to give a0^2 - N. Take the square root of that number 
to give sqrt(a0^2-N). Since a0 >= sqrt(N), this is a real number. 

If it is an integer b, then 

   a0^2 - N = b^2, and 
   N = a0^2 - b^2 = (a0-b)*(a0+b), 

and you have factored the number N.

If it is not an integer, replace a0 by a1 = a0 + 1. That increases 
a0^2 - N by 2*a0 + 1 to give a1^2 - N. Again take the square root, and 
see if you get an integer b. If not, increase a1^2 - N by 2*a1 + 1, and 
take the square root again. Continue this until you have factored N, or 
until sqrt(ai^2-N) exceeds N/2.

As an example, let's factor N = 1037.

   i    ai   ai^2-N   2*ai+1   sqrt(ai^2-N)
  -----------------------------------------
   0    33       52     67       7.2111
   1    34      119     69      10.9087
   2    35      188     71      13.7113
   3    36      259     73      16.0935
   4    37      332     75      18.2209
   5    38      407     77      20.1742
   6    39      484     79      22.0000 = 22 = b

and so 1037 = (39-22)*(39+22) = 17*61.

Now you do N = 99899, with a0 = 317.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/