RSA 暗号の、最も簡単な破り方は、これですね？

質問

RSA 暗号の、最も簡単な破り方は、これですね？：
暗号文中の自然数をNとする。
１．ルートN 未満の全ての奇数ｎについて、ｎが素数か否か、ＡＫＳ素数判定法で判定する。
https://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
２．ｎが素数ならば、Ｎをｎで割る。

回答No.1

_kappe_ · ベストアンサー

いいえ、「暗号文中の自然数をNとする」というのは話の出発点が違っています。
RSA暗号の解読が難しいのは桁数の大きな数Nの素因数分解には時間がかかる（と考えられている）からですが、そのNは暗号文中ではなくて公開鍵に含まれます。暗号文中の自然数を素因数分解してもRSA暗号は破れません。

また、アルゴリズムの簡単さで言うなら試し割り法（√Nまでの値で順番に割ってみる）のほうがはるかに簡単ですし、実用上の処理速度の観点では”まだ「一般数体篩法」で因数分解した方がよい”とWikipediaのAKS素数判定法のページに書かれています。

お礼

誠に有難う御座います！

補足

ウィキペディアによりますと、AKS は低速すぎるそうですので、以下に集成しました高速の諸・素数判定法で以て公開鍵中の n が素数か否かを判定してから・・・、という方法に訂正いたします。
https://www.google.com/search?q=okwave+%E7%B4%A0%E6%95%B0%E3%80%80%E7%94%9F%E6%88%90%E3%80%80%E5%A4%9A%E9%A0%85%E5%BC%8F%E6%99%82%E9%96%93&hl=ja&sxsrf=APwXEdfUsrQN-iqAbr3mLMk4B0O6XqwZ7Q:1684731844698&filter=0&biw=1096&bih=486&dpr=1.25