Prime Factorization By Parallel Lisp

The Difficulty of Prime Factorization

RSA encryption leverages the difficulty of prime factorization. Given 𝑁=𝑃×𝑄 (where P and Q are prime numbers), the calculation becomes increasingly time-consuming as the number of digits increases. RSA encryption is based on the fact that current computers require an enormous amount of time to factorize a 611-digit number. Various algorithms utilizing mathematical techniques have been proposed. Here, we attempt to see how much we can reduce the computation time by performing a simple trial division algorithm in parallel.

Idea

In the trial division algorithm, we divide by odd numbers up to root 𝑁​. At least one prime number should be found within this range. We investigate this divided range in parallel. Here, we will divide the task into five processes and perform the calculation using a multi-core CPU.

Extension of Parallel Constructs

In a previous article, we used a parallel construct called (mp-part). This construct returns the result and interrupts the remaining processes when any one of multiple calculations returns nil.

This time, we need a feature that interrupts the remaining processes and returns the result when any one of the processes returns a non-nil value. A mode has been added to (mp-part).

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

By giving nil or t to the mode, the behavior changes. When t is given, it returns the value when any one of the processes returns a non-nil value.

Code

Using this mp-part, I wrote the code for prime factorization using parallel computation. For comparison, I also show the code written sequentially.

;;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))))

Calculation Results

When the prime numbers 𝑃 and 𝑄 are large and close to each other, the effect of parallel computation is evident. When 𝑃 is small, the sequential method is faster. This is likely due to the overhead associated with parallel computation.

Easy-ISLisp

This is open-source software. It is available on GitHub.

sasagawa888/eisl: ISLisp interpreter/compiler (github.com)