coron.py

import logging
from math import gcd

from sage.all import ZZ

from shared import small_roots
from shared.polynomial import max_norm


def integer_bivariate(p, k, X, Y, roots_method="groebner"):
    """
    Computes small integer roots of a bivariate polynomial.
    More information: Coron J., "Finding Small Roots of Bivariate Integer Polynomial Equations Revisited"
    Note: integer_bivariate in the coron_direct will probably be more efficient.
    :param p: the polynomial
    :param k: the amount of shifts to use
    :param X: an approximate bound on the x roots
    :param Y: an approximate bound on the y roots
    :param roots_method: the method to use to find roots (default: "groebner")
    :return: a generator generating small roots (tuples of x and y roots) of the polynomial
    """
    pr = p.parent()
    x, y = pr.gens()
    delta = max(p.degrees())

    _, W = max_norm(p(x * X, y * Y))

    p00 = int(p.constant_coefficient())
    assert p00 != 0
    while gcd(p00, X) != 1:
        X += 1
    while gcd(p00, Y) != 1:
        Y += 1
    while gcd(p00, W) != 1:
        W += 1

    u = W + (1 - W) % abs(p00)
    n = u * (X * Y) ** k
    assert gcd(p00, n) == 1
    q = ((pow(p00, -1, n) * p) % n).change_ring(ZZ)

    logging.debug("Generating shifts...")

    shifts = []
    for i in range(k + delta + 1):
        for j in range(k + delta + 1):
            if i <= k and j <= k:
                shifts.append(x ** i * y ** j * X ** (k - i) * Y ** (k - j) * q)
            else:
                shifts.append(x ** i * y ** j * n)

    L, monomials = small_roots.create_lattice(pr, shifts, [X, Y])
    L = small_roots.reduce_lattice(L)
    polynomials = small_roots.reconstruct_polynomials(L, p, n, monomials, [X, Y])
    for roots in small_roots.find_roots(pr, [p] + polynomials, method=roots_method):
        yield roots[x], roots[y]