HesapHanem

Fermat Factorization Calculator

Enter an odd number to factor it with Fermat's method.

Result

59
101
3

How it is calculated

Fermat's method writes an odd number as a difference of two squares, N = a² − b² = (a − b)(a + b). The tool starts at a = ⌈√N⌉ and, for each a, tests whether a² − N is a perfect square b². The first a that works gives the factors a − b and a + b; the number of values of a tried is reported as steps. It returns one pair of factors, not a full prime factorization, so a pair such as 7 × 15 may still contain composites. Even numbers are not searched: they return 2 × N/2 with 0 steps. A prime comes back as 1 × N, after about N ÷ 2 steps. The loop stops after 2,000,000 steps, so very large primes or numbers with far-apart factors may give no result.

Worked example

Factor N = 5959. √5959 ≈ 77.2, so start at a = 78. Step 1: 78² − 5959 = 125, not a square. Step 2: 79² − 5959 = 282, not a square. Step 3: 80² − 5959 = 6400 − 5959 = 441 = 21², a perfect square, so b = 21. The factors are 80 − 21 = 59 and 80 + 21 = 101, found in 3 steps. Check: 59 × 101 = 5,959.

Try this example →

Common mistakes

  • Entering an even number and expecting Fermat's search. The tool just splits off a 2 with zero steps; divide out the powers of 2 first if you want the method to work on the rest.
  • Reading 1 × N as a failure. It means no other pair of factors exists, so N is prime (or 1).
  • Assuming the two factors shown are always prime. The pair multiplies to N, but either factor can be composite and need further splitting.
  • Trying numbers whose two factors are far apart, such as 3 × a large prime. Fermat's method then needs hundreds of thousands of steps, and the tool gives up at 2,000,000.
  • Entering a decimal. The input is rounded to the nearest whole number.

About this calculator

Fermat's factorization method exploits the fact that any odd integer N can be written as a difference of two squares, N = a² − b² = (a−b)(a+b). The algorithm starts at a = ⌈√N⌉ and increases a by 1 each step, checking whether a² − N is itself a perfect square (b²); the moment it is, N factors immediately into (a−b)(a+b). This calculator runs that loop and shows the two factors it found and how many steps it took to find them.

The method converges in very few steps when N's two factors are close together — its main weakness is also its most important real-world use: cryptography students and security researchers use Fermat factorization to demonstrate why RSA moduli must be built from primes that are far apart, since primes chosen too close together make the modulus trivially breakable. It's also a standard exercise in number theory coursework for illustrating difference-of-squares reasoning.

Was this helpful?

You can pick up to 3 reactions.

Comments (1)

  • Editorial team

    The step count is the interesting output. Compare 5959, which is 59 times 101 and falls out in 3 steps, with 1000003, a prime, where the search runs for 499,002 steps before reporting 1 times 1,000,003. Close factors are cheap, far-apart factors and primes are expensive, and the loop gives up after 2,000,000 steps. The tool reports how many steps it took, not each step. Which numbers did you try, and how many steps did they take?

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators