Know High Bits Of p

if $p=\overline{p}+x_0$ and we know $\overline{p}$, $|x_0|<N^{\frac{1}{4}}$, then $x_0$ is $f(x)\equiv \overline{p}+x(\mathrm{mod}p)$’s small root (assume that $p<q$)

---

Code

def known_high_bits_of_p(n: int, p0: int, epsilon=None):
    """
    - input : `n (int)`, `p0 (int)`, `epsilon (default=None)` , `0 < epsilon <= 0.5/7`
    - output : `(p, q) (int, int)`
    """
    P = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
    x = P._first_ngens(1)[0]

    f = p0 + x
    small_roots = f.small_roots(beta=0.5, epsilon=epsilon)
    if len(small_roots) > 0:
        p = p0 + int(small_roots[0])
        q = n // p
        assert p * q == n
        return p, q
    else:
        return -1