平方剰余 (Tonelli-Shanks)
(NumberTheory/ModularArithmetic/tonelli_shanks.py)

• View this file on GitHub
• Last update: 1970-01-01 00:00:00+00:00

概要

整数 $a$ と素数 $p$ が与えられたとき $x^2 \equiv a \pmod{p}$ を満たす $x$ を求めるアルゴリズム。

使い方

tonelli_shanks(a: int, p: int) -> int
$x^2 \equiv a \pmod{p}$ を満たす $x$ を返す。そのような $x$ が存在しない場合は -1 を返す。計算量 $O(\log^2 p)$

Code

from random import randint


def euler_criterion(a, p):
    res = pow(a, (p - 1) // 2, p)
    return 1 if res == 1 else res - p


def tonelli_shanks(a, p):
    a %= p
    if p == 2:
        return a
    if a == 0:
        return 0
    if euler_criterion(a, p) == -1:
        return -1

    z = randint(1, p - 1)
    while euler_criterion(z, p) == 1:
        z = randint(1, p - 1)

    # p - 1 = (2 ** m) * q
    q, m = p - 1, 0
    while q & 1 == 0:
        q //= 2
        m += 1

    c, t = pow(z, q, p), pow(a, q, p)
    res = pow(a, (q + 1) // 2, p)
    if t == 0:
        return 0

    m -= 2
    while t != 1:
        while pow(t, 2 ** m, p) == 1:
            c = c * c % p
            m -= 1
        res = res * c % p
        c = c * c % p
        t = t * c % p
        m -= 1
    return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page