Any odd integer $n$ can be represented as the difference of two squares. Given two factors $a$ and $b$ such that $n = ab$, we can define:

$$n = ab = (x+y)(x-y) = x^2 - y^2$$

Consequently, the factors relate to the squares as $a = x+y$ and $b = x-y$. Solving for $x$ and $y$ yields $x = (a+b)/2$ and $y = (a-b)/2$. Since $n$ is odd, its factors $a$ and $b$ must also be odd, ensuring that $a+b$ and $a-b$ are even, and thus $x$ and $y$ are integers. For instance, $15 = 5 \times 3 = 4^2 - 1^2$.

Basic Algorithm Implementation

To find the factors, we iterate through potential values of $x$. Since $x^2 - n = y^2 \ge 0$, it follows that $x \ge \sqrt{n}$. The algroithm initializes $x$ at $\lceil\sqrt{n}\rceil$ and increments it until $x^2 - n$ becomes a perfect square.

import math

def fermat_factor_basic(n):
    x = math.isqrt(n)
    if x * x < n:
        x += 1
    
    while True:
        y_squared = x * x - n
        y = math.isqrt(y_squared)
        if y * y == y_squared:
            return [x + y, x - y]
        x += 1

Optimization Using Quadratic Residues

Calculating the integer square root for every iteration is computationally expensive. We can optimize the process by observing the properties of the last two decimal digits of a perfect square. A perfect square can only end in specific pairs of digits: 00, e1, e4, 25, o6, e9 (where 'e' denotes an even tens digit and 'o' denotes a odd tens digit). By checking these trailing digits, we can quickly discard non-square candidates before performing the full square root calculation.

def has_square_tail(number):
    # Mapping of unit digits to required tens digit parity or value
    # 0 -> tens 0 (00)
    # 1 -> tens even (e1)
    # 4 -> tens even (e4)
    # 5 -> tens 2 (25)
    # 6 -> tens odd (o6)
    # 9 -> tens even (e9)
    
    unit = number % 10
    tens = (number % 100) // 10
    
    if unit == 0:
        return tens == 0
    if unit == 5:
        return tens == 2
    if unit in {1, 4, 9}:
        return tens % 2 == 0 # Even tens
    if unit == 6:
        return tens % 2 == 1 # Odd tens
    return False

def fermat_factor_optimized(n):
    x = math.isqrt(n)
    if x * x < n:
        x += 1
    
    while True:
        y_squared = x * x - n
        if has_square_tail(y_squared):
            y = math.isqrt(y_squared)
            if y * y == y_squared:
                return [x + y, x - y]
        x += 1

This filter significantly reduces the number of square root operations, improving execution speed.

Worst-Case Iteration Analysis

The number of iterations depends on the value of $x$. If we assume $a \ge b$, then $a^2 \ge n$. Let $f(a) = a + n/a$. We observe that $f(a)$ is monotonically increasing for $a > \sqrt{n}$. The maximum value of $x$ occurs when $a$ reaches its maximum possible value, wich is $n$ (corresponding to the trivial factorization $n \times 1$).

$$x_{max} = \frac{n + n/n}{2} = \frac{n+1}{2}$$

Therefore, the maximum number of iterations is bounded by: $$x_{max} - \sqrt{n} \approx \frac{n}{2} - \sqrt{n}$$

Application in Primality Testing

The worst-case scenario occurs when the algorithm runs the maximum number of iterations, finding the factors $n$ and $1$ (where $x = (n+1)/2$ and $y = (n-1)/2$). This behavior implies that no other factors exist for $n$.

Conversely, if $n$ is composite, say $n = ab$ with $a < n$, the monotonicity of $f(a)$ guarantees that $x(a) < x(n) = (n+1)/2$. Thus, the algorithm will find a factor before reaching the worst-case bound. This property allows the Fermat factorization algorithm to serve as a primality test: if the only factors found are $n$ and $1$, the number is prime.

if __name__ == "__main__":
    try:
        user_input = int(input("Enter an odd integer: "))
        if user_input % 2 != 0:
            factors = fermat_factor_optimized(user_input)
            print(f"{user_input} = {factors[0]} * {factors[1]}")
            if factors[1] == 1:
                print(f"Result: {user_input} is a prime number.")
    except ValueError:
        print("Invalid input.")