Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Number Theory
Middle School Factoring Numbers

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/