ヤコビ記号 (Jacobi symbol)
(include/emthrm/math/jacobi_symbol.hpp)
平方剰余 (quadratic residue)
$x^2 \equiv a \pmod{p}$ を満たす $x$ が存在すれば、$a \in \mathbb{Z}$ は法 $p$ の下で平方剰余であり、そうでなければ平方非剰余である。
ルジャンドル記号 (Legendre symbol)
整数 $a$、奇素数 $p$ に対して
\[\left(\dfrac{a}{p} \right) \mathrel{:=}
\begin{cases}
1 & (a \not\equiv 0 \pmod{p} \wedge a \text{ は法 } p \text{ の下で平方剰余}), \\
-1 & (a \text{ は法 } p \text{ の下で平方非剰余}), \\
0 & (a \equiv 0 \pmod{p})
\end{cases}\]
と定義する。
オイラーの基準 (Euler’s criterion)
整数 $a \neq 0$、奇素数 $p$ に対して $a \perp p$ ならば
\[\left(\dfrac{a}{p} \right) \equiv a^{\frac{p - 1}{2}} \pmod{p}\]
が成り立つ。
Tonelli–Shanks algorithm
整数 $a$、奇素数 $p$ に対して $x^2 \equiv a \pmod{p}$ が成り立つ $x$ ($0 \leq x < p$) を求めるアルゴリズムである。
以下では剰余演算のときに $p$ を法とする。
一般性を失わず $0 \leq a < p$ とできる。
$a = 0$ ならば $x = 0$ として終了する。
$a$ が平方非剰余ならば条件を満たす $x$ は存在しないとして終了する。
$p = q2^s + 1$ を満たす奇数 $q$、正整数 $s$ を求める。
$p$ は奇素数より $q, s$ は一意に決まる。
平方非剰余 $z$ を一つ求め、$m = s,\ c \equiv z^q,\ t \equiv a^q,\ r \equiv a^{\frac{q + 1}{2}}$ とする。このとき
$c^{2^{m - 1}} \equiv -1 \quad (\because z \text{ は平方非剰余} \wedge c^{2^{m - 1}} \equiv z^{q \cdot 2^{m - 1}} = z^{\frac{p - 1}{2}})$、
$t^{2^{m - 1}} \equiv 1 \quad (\because a \text{ は平方剰余} \wedge t^{2^{m - 1}} \equiv a^{q \cdot 2^{m - 1}} = a^{\frac{p - 1}{2}})$、
$r^2 \equiv at \quad (\because r^2 \equiv a^{q + 1})$
が成り立つ。この3式を成り立たせつつ $t \equiv 1$ となる $m, c, r$ を求めればよい。
$t \equiv 1$ ならば $x = r$ として終了する。
$t^{2^i} \equiv 1$ を満たす最小の正整数 $i$ を求める。
上の2式目より $i = m - 1$ はこれを満たすので $1 \leq i \leq m - 1$ を満たす。
$t \not\equiv 1$ より $t^{2^{i - 1}} \equiv -1$ が成り立つ。
$m \leftarrow i$、
$c \leftarrow c^{2^{m - i}} \quad (\because (c^{2^{m - i}})^{2^{i - 1}} = c^{2^{m - 1}} \equiv -1)$、
$t \leftarrow tc^{2^{m - i}} \quad (\because (tc^{2^{m - i}})^{2^{i - 1}} = t^{2^{i - 1}}c^{2^{m - 1}} \equiv -1 \cdot -1 \equiv 1)$、
$r \leftarrow rc^{2^{m - 1 - i}} \quad (\because (rc^{2^{m - 1 - i}})^2 \equiv r^2 c^{2^{m - i}} \equiv atc^{2^{m - i}})$
と更新しても3式は成り立つ。この操作で $m$ は減少している。$m = 1$ のとき2式目より $t \equiv 1$ が成り立つため、有限ステップで解は求まる。
4に戻る。
ヤコビ記号 (Jacobi symbol)
整数 $a$、正の奇数 $p$ に対して $p$ の素因数分解を $p = \prod_i p_i^{e_i}$ とすると
\[\left(\dfrac{a}{p} \right) \mathrel{:=} \prod_i \left(\dfrac{a}{p_i} \right)^{e_i}\]
と定義される。
時間計算量
時間計算量
平方剰余
ヤコビ記号
$O(\log{\max \lbrace A, P \rbrace})$ ?
仕様
平方剰余
名前
戻り値
要件
long long mod_sqrt(long long a, const int p);
$x^2 \equiv a \pmod{p}$ を満たす $x$。ただし存在しないときは $-1$ を返す。
$p \in \mathbb{P}$
ヤコビ記号
名前
戻り値
int jacobi_symbol(long long a, long long p);
$\left(\dfrac{a}{p} \right)$
参考文献
平方剰余
Carl Friedrich Gauss: Disquisitiones Arithmeticae (1801).
Daniel Shanks: Five number-theoretic algorithms, Proceedings of the second Manitoba conference on numerical mathematics , pp. 51–70 (1973).
https://lumakernel.github.io/ecasdqina/math/number-theory/Tonelli-Shanks
https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
http://sugarknri.hatenablog.com/entry/2018/02/16/115740
https://github.com/ei1333/library/blob/e24eaf375ae60018ba6af9079f690db319719e09/math/combinatorics/mod-sqrt.cpp
ルジャンドル記号
Adrien Marie Legendre: Essai sur la Théorie des Nombres (1798).
ヤコビ記号
Carl Gustav Jacob Jacobi: Über die Kreistheilung und ihre Anwendung auf die Zahlentheorie, Journal für die reine und angewandte Mathematik , Vol. 30, pp. 166–182 (1846).
https://en.wikipedia.org/wiki/Jacobi_symbol
https://judge.yosupo.jp/submission/300
TODO
$x^k \equiv a \pmod{p}$ ($a, k \in \mathbb{Z},\ k \geq 0,\ p \in \mathbb{P}$) を満たす $x$ を求める。
https://yukicoder.me/problems/3866
https://judge.yosupo.jp/problem/kth_root_mod
Cipolla’s algorithm
https://en.wikipedia.org/wiki/Cipolla%27s_algorithm
https://37zigen.com/cipolla-algorithm/
https://judge.yosupo.jp/submission/1843
https://judge.yosupo.jp/submission/1669
Submissons
Verified with
Code
#ifndef EMTHRM_MATH_JACOBI_SYMBOL_HPP_
#define EMTHRM_MATH_JACOBI_SYMBOL_HPP_
#include <bit>
#include <cassert>
#include <utility>
namespace emthrm {
int jacobi_symbol ( long long a , long long p ) {
assert ( p > 0 && p & 1 );
if ( p == 1 ) [[ unlikely ]] return 1 ;
if (( a %= p ) < 0 ) a += p ;
if ( a == 0 ) [[ unlikely ]] return 0 ;
int res = 1 ;
while ( a > 0 ) {
const int p2 = std :: countr_zero ( static_cast < unsigned long long > ( a ));
if (( p2 & 1 ) && (( p + 2 ) & 4 )) res = - res ;
a >>= p2 ;
if ( a & p & 2 ) res = - res ;
std :: swap ( a , p );
a %= p ;
}
return p == 1 ? res : 0 ;
}
} // namespace emthrm
#endif // EMTHRM_MATH_JACOBI_SYMBOL_HPP_
#line 1 "include/emthrm/math/jacobi_symbol.hpp"
#include <bit>
#include <cassert>
#include <utility>
namespace emthrm {
int jacobi_symbol ( long long a , long long p ) {
assert ( p > 0 && p & 1 );
if ( p == 1 ) [[ unlikely ]] return 1 ;
if (( a %= p ) < 0 ) a += p ;
if ( a == 0 ) [[ unlikely ]] return 0 ;
int res = 1 ;
while ( a > 0 ) {
const int p2 = std :: countr_zero ( static_cast < unsigned long long > ( a ));
if (( p2 & 1 ) && (( p + 2 ) & 4 )) res = - res ;
a >>= p2 ;
if ( a & p & 2 ) res = - res ;
std :: swap ( a , p );
a %= p ;
}
return p == 1 ? res : 0 ;
}
} // namespace emthrm
Back to top page