fermat-factorization-algorithm

#!/usr/bin/python3
# original: https://github.com/murtaza-u/zet/tree/main/20220808171808
# gmpy2 is a C-coded Python extension module that supports
# multiple-precision arithmetic.
#
# pip install gmpy2
from gmpy2 import isqrt

from math import lcm

def factorize(n):
    # since even nos. are always divisible by 2, one of the factors will
    # always be 2
    if (n & 1) == 0:
        return (n/2, 2)

    # isqrt returns the integer square root of n
    a = isqrt(n)

    # if n is a perfect square the factors will be ( sqrt(n), sqrt(n) )
    if a * a == n:
        return a, a

    while True:
        a = a + 1
        bsq = a * a - n
        b = isqrt(bsq)
        if b * b == bsq:
            break

    return a + b, a - b

#print(factorize(105327569))

# print p, q and their diffrences:

p, q = factorize(105327569)
print(f"p: {p}")
print(f"q: {q}")
print(f"Difference (p - q): {p - q}")