What is the computational cost of the Cornacchia's algorithm?

edit

If we need to factor a number N

Given the Pythagorean quadruple (with n and m in Z)

d=36m^2+18m+4n^2+2n+3

a=24mn+6m+6n+1

b=2(3m+n+1)(6m-2*n+1)

c=2(3m+n+1)

a^2+b^2+c^2=d^2

then if:

1) N=d^2-c^2=a^2+b^2

2) N=d^2-b^2=a^2+c^2

3) N=d^2-a^2=b^2+c^2 (case N is even)

The factorization of N can be obtained using the Cornacchia's Algorithm.

What is the computational cost of the Cornacchia's algorithm?

def cornacchia(p, d):
    # Verifica se -d è un quadrato modulo p
    if not is_square(Mod(-d, p)):
        return None

    # Trova una radice quadrata di -d mod p
    r = sqrt(Mod(-d, p))

    # Algoritmo di Euclide esteso
    a, b = p, int(r)
    while b*b > p:
        a, b = b, a % b

    # Verifica se esiste soluzione
    x = b
    y2 = (p - x^2) // d
    if y2 >= 0 and is_square(y2):
        y = sqrt(y2)
        return (x, int(y))
    else:
        return None

# Esegui per p = 65, d = 1
cornacchia(725, 1)

(23, 14)

d=36m^2+18m+4n^2+2n+3 , a=24mn+6m+6n+1=-23 , b=2(3m+n+1)(6m-2n+1)=14 , c=2(3*m+n+1)

->

d-c=a=29

d+c=b=25

ab=2925=725