Stereotyped Message

if we know $m=\overline{m}+x_0$ and $x_0\le N^{\frac{1}{e}}$, the cipher $c\equiv m^e\equiv (\overline{m}+x_0{)}^e(\mathrm{mod}N)$, then $x_0$ is the small root of $f(x)\equiv (\overline{m}+x{)}^e-c(\mathrm{mod}N)$

---

Code

def stereotyped_message(n: int, e: int, c: int, m0: int, epsilon=None):
    """
    - input : `n (int)`, `e (int)`, `c (int)`, `m0 (int)`, `epsilon (default=None)` , `0 < epsilon <= 1/7`
    - output : `m (int)` , `c`'s plain. if there's no solve, return `-1`
    """
    P = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
    x = P._first_ngens(1)[0]

    f = (m0 + x) ** e - c
    small_roots = f.small_roots(epsilon=epsilon)
    if len(small_roots) > 0:
        return int(small_roots[0]) + m0
    else:
        return -1