RSA暗号化ソフト

RSA暗号で使う２つの素数はそれぞれ50桁を超える莫大な数がベストだということをwebサイトなどで知ったのですが、市販のPCではint型でも43億ぐらいの数までしか扱えないので、自作のRSA暗号化ソフトといったものを作ることは不可能なのでしょうか？

No.2 ベストアンサー 回答者： kmee 回答日時： 2015/11/27 07:09

例えば。

10進数の数字って、0〜9 しかありません。
で、9までの数しか扱えないか、と言えばそうではなく、組合せて大きな数値も表現できますよね?


123 × 45 を筆算で求める時は

3 × 5 = 15 の 5
2 × 5 = 10 の 0 に繰り上がりの1 を足して 1
1 × 5 = 5 の 5 に繰り上がりの1 を足して 6
3 × 4 = 12 の 2
2 × 4 = ...
...
1の位 は 5
10の位は 1 + 2 = 3
100の位は 6 + ...

と、部分部分では、1桁(繰り上げも含めて2桁)の計算しかしていません。



同じように考えて、intを「1桁」と考えれば 組み合わせて50桁でも扱うことができます。(メモリに余裕があれば)
32bit × 32bit で64bit必要、ということなら、 16bitを「1桁」とすれば32bitに収まります。

※ そもそも intが32bitというのは、特定の言語、実行環境に依存する話です。
RubyやPython3のintは「無限」ですし、C言語でも組込みマイコン用等では16bitになっているものもあります。


https://ja.wikipedia.org/wiki/%E4%BB%BB%E6%84%8F …

No.1 回答者： Tacosan 回答日時： 2015/11/27 02:01

あなたが作れるかどうかはさておき, 一般論としては可能です.