ヤコビ記号を使用する
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/31 00:03 UTC 版)
( 1001 9907 ) = ( 9907 1001 ) = ( 898 1001 ) = ( 2 1001 ) ( 449 1001 ) = ( 449 1001 ) = ( 1001 449 ) = ( 103 449 ) = ( 449 103 ) = ( 37 103 ) = ( 103 37 ) = ( 29 37 ) = ( 37 29 ) = ( 8 29 ) = ( 2 29 ) 3 = − 1. {\displaystyle {\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)\\&=\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)\\&=\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.\end{aligned}}} 2つの計算の違いは、ルジャンドル記号を使用する場合、記号を反転する前に「分子」を素数冪に因数分解する必要があることである。これにより、整数を因数分解するための既知の多項式時間アルゴリズムがないため、ルジャンドル記号を使用した計算はヤコビ記号を使用した計算よりも大幅に遅くなる。実際、これがヤコビがこの記号を導入した理由である。
※この「ヤコビ記号を使用する」の解説は、「ヤコビ記号」の解説の一部です。
「ヤコビ記号を使用する」を含む「ヤコビ記号」の記事については、「ヤコビ記号」の概要を参照ください。
- ヤコビ記号を使用するのページへのリンク
