並列Lispによる素因数分解

素因数分解の難しさ

RSA暗号は素因数分解の困難さを応用しています。N=P*Q （P,Qは素数）は大きな桁数になると計算に時間がかかります。現在のコンピューターでは611桁の素因数分解には膨大な時間がかかることを応用したものがRSA暗号です。いろいろと数学を応用したアルゴリズムが考案されているそうです。ここでは単純な試し割によるアルゴリズムを並列で計算することによりどの程度、計算時間を短縮できるのかを試してみました。

アイディア

試し割をするアルゴリズムでは√Nまでを奇数で割り算をしていきます。この区間にかならず１つの素数が見つかるはずです。これを並列により分割した区間を調べます。ここでは５つのプロセスに分割してマルチコアCPUで計算することにします。

並列構文の拡張

以前の記事で(mp-part)という並列構文を用いました。これは複数の計算のうちのいずれか１つがnilを返したきたときに残りのプロセスを中断して結果を返すというものでした。

今回はいずれか１つのプロセスがnil以外の値を返したときに残りのプロセスを中断して結果を返す機能が必要です。(mp-part)にモードを追加しました。

(mp-part mode (foo1) (foo2) (foo3) (foo4) (foo5))

modeにnilあるいはtを与えることで動作を変えます。tを与えるといずれかのプロセスがnil以外の値を返したときにその値を返します。

コード

このmp-partを利用して並列計算で素因数分解をするコードを書いてみました。比較のために逐次で書いたコードもあわせて示します。

;;parallel
(defun factors* (n)
    (let* ((limit (isqrt n))
           (span (+ (div limit 5) 1))
           (p (mp-part t (cofactor n 3 span)
                         (cofactor n (near-odd span) (* 2 span))
                         (cofactor n (near-odd (* 2 span)) (* 3 span))
                         (cofactor n (near-odd (* 3 span)) (* 4 span))
                         (cofactor n (near-odd (* 4 span)) (* 5 span)))))
                (list p (div n p))))

(defun cofactor (n s e)
    (cond ((> s e) nil)
          ((= (mod n s) 0) s)
          (t (cofactor n (+ s 2) e))))

(defun near-odd (n)
    (if (= (mod n 2) 0)
        (- n 1)
        n))


;; sequence
(defun factors (n)
    (let ((p (cofactor n 3 (isqrt n))))
        (list p (div n p))))

計算結果

素数P,Qが大きく、近い数になっている場合には並列計算の効果が表れています。Pが小さいときには逐次の方が高速になります。並列計算によるオーバーヘッドがあるためでしょう。

Easy-ISLisp

オープンソースソフトウェアです。githubにて公開しています。
https://github.com/sasagawa888/eisl