- 888 名前：Kummer ◆g2BU0D6YN2 [2007/03/11(日) 02:07:07 ]
- p を奇素数とし gcd(a, p) = 1 のとき
x^2 ≡ a (mod p) に解があるかどうかを決定するには、
Legendre の記号(前スレ３の746) (a/p) を計算すればよい。
(a/p) を計算する一つの方法は、
(a/p) ≡ a^((p - 1)/2) (mod p) (前スレ３の747)
を使う。
p が大きいとき、この方法は効率が悪いように見えるが
実はそうでもない。
後で述べるが a^((p - 1)/2) を計算機で計算するのに効率のよい
アルゴリズムがある。
(a/p) を計算する別の方法としては、a の素因数分解と
平方剰余の相互律(前スレ３の751)を使うものがある。
この方法は具体例で示したほうが分かりやすい。
p = 997 として (588/997) を計算してみよう。
588 = (7^2)・3・2^2 だから
(588/997) = (7^2/997)(3/997)(2^2/997) = (3/997)
997 ≡ 1 (mod 4) だから平方剰余の相互律より
(3/997) = (997/3) = (1/3) = 1 である。
よって (588/997) = 1
実際 183^2 ≡ 588 (mod 997)
しかし、この方法は a の素因数分解が必要なので、大きい数の
計算には不向きである。
この不都合は次にのべる Jacobi の記号により解消される。
|
 |
