> For the complete documentation index, see [llms.txt](https://alham-rizvi.gitbook.io/alhamrizvi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alham-rizvi.gitbook.io/alhamrizvi/cryptography/rsa/05.-fermat-factorization-attack.md).

# Fermat Factorization Attack (Close Primes)

## Overview

The Fermat Factorization Attack is a method used to break RSA when the two prime numbers used to generate the modulus are **close to each other**.

In RSA, the modulus is defined as:

```
n = p × q
```

If the primes `p` and `q` are very close, then `n` can be rewritten using a mathematical identity:

```
n = a² − b²
```

This comes from the difference of squares:

```
a² − b² = (a − b)(a + b)
```

By comparing:

```
n = (a − b)(a + b)
```

we get:

```
p = a − b
q = a + b
```

So instead of directly factoring `n`, we search for two numbers `a` and `b` such that:

```
b² = a² − n
```

If `b²` is a perfect square, we can recover `p` and `q`.

## Mathematical Intuition

The key idea is that if `p` and `q` are close, then:

```
a ≈ √n
```

So we start searching from:

```
a = ceil(√n)
```

Then we repeatedly check:

```
b² = a² − n
```

If `b²` is a perfect square, we have found valid values of `a` and `b`, and we can compute:

```
p = a − b
q = a + b
```

***

## Step-by-Step Example

Let:

```
n = 5959
```

First compute:

```
a = ceil(√5959) = 78
```

Now we test values:

For `a = 78`:

```
b² = 78² − 5959 = 6084 − 5959 = 125
```

Not a perfect square.

For `a = 79`:

```
b² = 79² − 5959 = 6241 − 5959 = 282
```

Not a perfect square.

For `a = 80`:

```
b² = 80² − 5959 = 6400 − 5959 = 441
```

```
b = √441 = 21
```

Now we compute:

```
p = 80 − 21 = 59
q = 80 + 21 = 101
```

Thus:

```
5959 = 59 × 101
```

***

## Python Implementation

```python
import math

def fermat_factor(n):
    # Step 1: Start from ceil(sqrt(n))
    a = math.isqrt(n)
    if a * a < n:
        a += 1

    # Step 2: Search for perfect square
    while True:
        b2 = a*a - n
        b = math.isqrt(b2)

        if b*b == b2:
            break

        a += 1

    # Step 3: Compute factors
    p = a - b
    q = a + b

    return p, q


n = 5959
p, q = fermat_factor(n)

print("p =", p)
print("q =", q)
```

***

## Line-by-Line Explanation

```python
a = math.isqrt(n)
```

This computes the integer square root of `n`, i.e., the largest integer ≤ √n.

```python
if a * a < n:
    a += 1
```

This ensures that `a = ceil(√n)`, which is required for Fermat’s method.

***

```python
b2 = a*a - n
```

This computes:

```
b² = a² − n
```

***

```python
b = math.isqrt(b2)
```

This computes:

```
b = ⌊√(b²)⌋
```

***

```python
if b*b == b2:
```

This checks whether `b²` is a perfect square.

If true:

```
b² = a² − n
```

and we can proceed to recover factors.

***

```python
a += 1
```

If not a perfect square, increment `a` and repeat the process.

***

```python
p = a - b
q = a + b
```

Using:

```
n = (a − b)(a + b)
```

we recover the prime factors.

***

## When This Attack Works

* When `p` and `q` are close to each other
* When `n` can be expressed as a difference of two squares quickly

***

## When This Attack Fails

* When `p` and `q` are far apart
* When primes are generated securely (random, large difference)

***

## Key Takeaway

Fermat’s method transforms factoring into a search for a perfect square:

```
b² = a² − n
```

If the primes are close, this search completes very quickly, making RSA vulnerable.

<img src="https://github.com/user-attachments/assets/b9a25fb5-d3a4-46c7-882c-cc4ab3a41fbe" alt="image" height="702" width="793">

## Summary

```
Start from a ≈ √n
Compute b² = a² − n
Check if b² is a perfect square
If yes → recover p and q
```

<img src="https://github.com/user-attachments/assets/963becfb-2539-4ee7-bad5-09f3dc12bb6f" alt="image" height="743" width="793">


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://alham-rizvi.gitbook.io/alhamrizvi/cryptography/rsa/05.-fermat-factorization-attack.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.