ヤコビ記号
{\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つの計算の違いは、ルジャンドル記号を使用する場合、記号を反転する前に「分子」を素数冪に因数分解する必要があることである。これにより、整数を因数分解するための既知の多項式時間アルゴリズムがないため、ルジャンドル記号を使用した計算はヤコビ記号を使用した計算よりも大幅に遅くなる。実際、これがヤコビがこの記号を導入した理由である。