単純な素因数分解アルゴリズムを実装してみる - ももいろテクノロジー

「OpenSSLとPythonでRSA暗号の原理を知る」で書いたように、RSA暗号は公開鍵である整数modulusを二つの素数に素因数分解することができれば破ることができる。 ここでは、いくつかの単純な素因数分解アルゴリズムをPythonで実装し、一般的なPCで解くことができるbit数などを調べてみる。 なお、正確には素因数分解ではなく、因数をひとつ見つけるアルゴリズムについて考えるものとする。 環境 Ubuntu 14.04.3 LTS 64bit版、Intel Core i5-4200U (1.6GHz * 2 * 2) $ uname -a Linux vm-ubuntu64 3.19.0-25-generic #26~14.04.1-Ubuntu SMP Fri Jul 24 21:16:20 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux $ ls