EXPT-MOD

One of the proposed Common Lisp utilities, modular exponentiation is important for many algorithms like Miller-Rabin and RSA. Although it can be implemented portably (see below), it would benefit from implementation-specific (i.e. fast) implementations.

Here is an example by Jochen Schmidt of how EXPT-MOD can be implemented in portable Common Lisp:

(defun expt-mod (n exponent modulus)
  "As (mod (expt n exponent) modulus), but more efficient."
  (declare (optimize (speed 3) (safety 0) (space 0) (debug 0)))  
  (loop with result = 1
        for i of-type fixnum from 0 below (integer-length exponent)
        for sqr = n then (mod (* sqr sqr) modulus)
        when (logbitp i exponent) do
        (setf result (mod (* result sqr) modulus))
        finally (return result)))

Q: Why standardize an interface (well, a function name)? Lisp implementations that want to provide an accelerated (expt (mod ...)) can do that with a compiler macro, right? A: Yes, but if you rely on that compiler macro as programmer you will get horrible performance, if your implementation does not have an optimized algorithm for (expt (mod ...))

This page is linked from: Common Lisp Utilities

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively