ヤコビ記号の計算
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/31 00:03 UTC 版)
上記の式は、2つの数のgcdを見つけるためにユークリッドの互除法に似た、ヤコビ記号を計算するための効率的なO(log a log b) につながる（これは規則2に照らすと驚くべきことはない）。 規則2を使用して「分母」を法として「分子」を減らす。 規則9を使用して、偶数の「分子」を抽出する。 「分子」が1の場合、規則3と4の結果は1になる。「分子」と「分母」が互いに素でない場合、規則3の結果は0になる。 それ以外の場合、「分子」と「分母」は互いに素な奇数の正整数であるため、規則6を使用して記号を反転し、手順1に戻ることができる。
※この「ヤコビ記号の計算」の解説は、「ヤコビ記号」の解説の一部です。
「ヤコビ記号の計算」を含む「ヤコビ記号」の記事については、「ヤコビ記号」の概要を参照ください。
ウィキペディア小見出し辞書の「ヤコビ記号の計算」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ヤコビ記号の計算のページへのリンク
