Fermat's Factorization MethodDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/