Fermat Factorization Method

Pierre de Fermat

Before Fermat introduced his factorization method, the classical method was to divide n by all prime numbers not exceeding √n.

In his method, Fermat assumes that n is odd and observed that the search for factors of n is equivalent to obtaining the integral solutions of x and y of the equation n = (x^2) – (y^2) = (x – y) (x + y)

If n has a factorization n = ab, a ≥ b ≥ 1
We may write n = ((a+b)/2)^2 – ((a-b)/2)^2 ; (a+b)/2 > 0 and (a-b)/2 > 0

We then determine the smallest integer k for which k^2 ≥ n, k^2 – n, (k+1)^2 – n, (k+2)^2 – n, … until a value of m ≥ √n is found making m^2 – n a square.

We know that this process cannot go on indefinitely, we know we will eventually arrive at ((n+1)/2)^2 – n = ((n-1)/2)^2, the representation of n corresponding to the trivial factorization n = n ∙ 1. Meaning that n is a prime.

Examples:
1. n = 2027651281, k= 45030
45030^2 – 2027651281 = 49619
45031^2 – 2027651281 = 139680
45032^2 – 2027651281 = 229743
45033^2 – 2027651281 = 319808
45034^2 – 2027651281 = 409875
45035^2 – 2027651281 = 499944
45036^2 – 2027651281 = 590015
45037^2 – 2027651281 = 680088
45038^2 – 2027651281 = 770163
45039^2 – 2027651281 = 860240
45040^2 – 2027651281 = 950319
45041^2 – 2027651281 = 1040400 = 1020^2
=> 2027651281 = 45041^2 – 1020^2
=> 2027651281 = (45041+1020)(45041–1020)
=> 2027651281 = (46061)(44021)

---

2. n = 17, k = 5
5^2 – 17 = 8
6^2 – 17 = 19
7^2 – 17 = 32
8^2 – 17 = 47
9^2 – 17 = 64 = 8^2
=> 17 = 9^2 – 8^2
=> 17 = (9 + 8)(9 – 8)
=> 17 = (17)(1)

NOTE:
Squares must end in 0, 1, 4, 5, 6, and 9
And from 0-99 (mod 100) ends in 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96

See How it Works HERE!

Download Now

Daghang salamat sa pagbasa!!!