Skip to content

ojoaosoares/Fermat-Factorization

Repository files navigation

Fermat's Factorization Algorithm

Fermat's factorization method is an integer factorization algorithm that relies on the representation of an odd integer as the difference of two squares. It's particularly effective for numbers that are the product of two factors that are close to each other.

Algorithm Overview

Given an odd integer N , Fermat's factorization method expresses N as:

N = a 2 b 2 = ( a b ) ( a + b )

Where:

  • a and b are integers.
  • a is slightly larger than the square root of N .
  • b is found iteratively.

The factorization then gives us:

N = ( a b ) × ( a + b )

Steps

  1. Initialization:

    • Compute a as the ceiling of N , i.e., a = N .
    • Set b 2 = a 2 N .
  2. Iteration:

    • While b 2 is not a perfect square:
      • Increment a by 1.
      • Recompute b 2 = a 2 N .
  3. Factorization:

    • Once b 2 is a perfect square, compute b = b 2 .
    • The factors of N are ( a b ) and ( a + b ) .

Example

Let's factorize N = 5959 using Fermat's method.

  1. Initialization:

    • a = 5959 = 78 .
    • b 2 = 78 2 5959 = 6084 5959 = 125 , which is not a perfect square.
  2. Iteration:

    • Increment a to 79.
    • b 2 = 79 2 5959 = 6241 5959 = 282 , which is still not a perfect square.
    • Increment a to 80.
    • b 2 = 80 2 5959 = 6400 5959 = 441 , which is a perfect square.
  3. Factorization:

    • b = 441 = 21 .
    • The factors of 5959 are 80 21 = 59 and 80 + 21 = 101 .

Thus, 5959 = 59 × 101 .

Main Program Usage

The main program implementing Fermat's factorization method takes an odd integer N as input and outputs the factor ( a + b ) . This factor is one of the two factors of N , the other being ( a b ) .

  • Input: An odd integer N .
  • Output: The factor ( a + b ) , where N = ( a b ) × ( a + b ) .

For instance, given the input N = 5959 , the program would output 101 .

Applications and Limitations

Fermat's factorization method is most efficient when the factors of N are close together. If the factors are far apart, the method becomes inefficient compared to other factorization algorithms, like the Pollard rho algorithm or the quadratic sieve.

References

  • Wikipedia: Fermat's factorization method
  • Números Inteiros e Criptografia RSA.
  • Other books and research papers on integer factorization and number theory.