projectpn
projectpn

平方剰余記号と平方剰余の相互法則

平方剰余記号は整数aと奇素数pに対して次のように定義される。
\left( \frac{a}{p} \right)= \begin{cases}0 & a\equiv 0 \pmod p \\ 1 & a \not \equiv 0 \pmod p \ and \ x^2 \equiv a \pmod p \ {\rm for \ some} \ x \\ -1 & a \not \equiv 0 \pmod p \ and \ x^2 \not \equiv a \pmod p \ {\rm for \ all} \ x \\ \end{cases}
次のことが成り立つ。(平方剰余の相互法則)
互いに異なる奇素数p,qに対して
\left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}
また、
\left( \frac{-1}{q} \right) = (-1)^{\frac{p-1}{2}}
(第一補充法則)
\left( \frac{2}{q} \right) = (-1)^{\frac{p^2-1}{8}}
(第二補充法則)
p,a,bが互いに素であるとき、
\left( \frac{a}{p} \right) \left( \frac{b}{p} \right) = \left( \frac{ab}{p} \right)

ヤコビ記号

\scriptstyle{\left( \frac{a}{n} \right)}のnの条件を奇数を許すように緩めたものをヤコビ記号という。ヤコビ記号は、平方剰余の相互法則を適用でき、nが奇素数のときヤコビ記号は平方剰余記号と一致する。(証明略)
ヤコビ記号は簡単に計算できるため、平方剰余記号を計算する際に役立つ。

ヤコビ記号の計算

(未完成)

オイラーの基準

整数aと奇素数pに対して次の等式が成り立つ。
\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod p

Solovay-Strassen素数判定法

オイラーの基準の対偶をとって、

\left( \frac{a}{n} \right) \not \equiv a^{\frac{n-1}{2}} \pmod n
であるとき、nは合成数である。
フェルマーテストと同じように、nが合成数であってもそれを判別できない場合が存在するが、たくさんのaで調べることによって精度を上げることができる。また、フェルマーテストと異なりカーマイケル数のようなどんなaを用いても合成数であると判別できないような合成数は存在しない。
このアルゴリズムでk個のaに対し合成数であるのにそれを判別できない確率は最大でも\scriptstyle{2^{-k}}である。
「Solovay-Strassen素数判定法」をウィキ内検索
最終更新：2012年06月30日 17:21