Hello,
If the question of the subject of this message is too vague, in order
to have something more specific to talk about I have written a function
that computes g^n mod m.
There I would like to know if you think the test at the end of the loop
is worth doing: would you check for bignums if you had written that
function?
Thanks,
-- Shin
(defparameter *isqrt-most-positive-fixnum*
(isqrt most-positive-fixnum))
;;;
;;; This is an implementation of the algorithm explained in
;;; H. Cohen, "A course in Computational Number Theory"
;;; Springer�Verlag, 1995.
;;;
;;; The idea is to represent n in radix 2 but, anyway, what
;;; happens is that Y is at least squared every time so it
;;; is likely to become a bignum sooner or later.
;;; Would you avoid this somehow or wouldn't you mind?
;;;
(defun expt-mod (g n m)
"(expt-mod g n m) returns g^n mod m, where n is non-negative."
(when (zerop n)
(return-from expt-mod 1))
(loop with z = (mod g m)
for f from (- (integer-length n) 2) downto 0
for y = (* z z) then (* y y)
when (logbitp f n)
do (setq y (* y z))
when (< *isqrt-most-positive-fixnum* y)
do (setq y (mod y m))
finally (return (mod y m))))
On Mon, 17 Jan 2000 12:27:23 +0100, Shin <···@retemail.es> wrote:
: (defun expt-mod (g n m)
: "(expt-mod g n m) returns g^n mod m, where n is non-negative."
: (when (zerop n)
: (return-from expt-mod 1))
: (loop with z = (mod g m)
: for f from (- (integer-length n) 2) downto 0
: for y = (* z z) then (* y y)
: when (logbitp f n)
: do (setq y (* y z))
: when (< *isqrt-most-positive-fixnum* y)
: do (setq y (mod y m))
: finally (return (mod y m))))
Excuse me, this doesn't work if n = 1. The next version does.
(defun expt-mod (g n m)
"(expt-mod g n m) returns g^n mod m."
(when (zerop n)
(return-from expt-mod 1))
(loop with z = (mod g m)
with y = z
for f from (- (integer-length n) 2) downto 0
do (setq y (* y y))
when (logbitp f n)
do (setq y (* y z))
when (< *isqrt-most-positive-fixnum* y)
do (setq y (mod y m))
finally (return (mod y m))))