✨ ベストアンサー ✨
中学生が普通にやるような話ではなさそうですが、結局は合同式の活用とかの話に帰着するようですね。
p=11, q=23が与えられているので、公開鍵(暗号鍵)nとeのうち、nはこれらの積
n=11×23=253
となり、eは
(p-1)(q-1)=10×22=220=2²×5×11
と互いに素な自然数のうちの一つとして、19にするよう問題が指示してきています。
さて、平文(ひらぶん)32を暗号文に変えるロジックは、
32を19乗し、253で割った余りが、32の暗号文
のようです。
普通にやるとしんどいので、工夫を試みます。
まず、32=2⁵なので、
32¹⁹=(2⁵)¹⁹=2⁹⁵
です。また、
2⁸=256=253+3となりますので、
2⁹⁵=(2⁸)¹¹×2⁷
と書いたとき、それを253で割った余りは、2⁸を3におきかえて
3¹¹×2⁷を253で割ったあまりに等しくなります。
ここで
3⁵=243=253-10なので
3¹⁰=(3⁵)²=(253-10)²=253²-253×10×2+10²
を253で割った余りは10²=100となります。
したがって、
3¹¹×2⁷=3¹⁰×3×2⁷を253で割った余りは
100×3×2⁷を253で割った余りに等しくなります。
ここまでいけば正攻法で良く、
100×3×2⁷=38400を253で割った余りは筆算でもして197となります。
この197が題意の暗号文のはずです。
なお、復号のほうはもっと厄介で、復号のための秘密鍵のひとつが139となり、エクセルを工夫して駆使して、197の139乗を253で割った余りが32に戻ることは確認できました。