; baby steps, giant steps

(define (expm b e m)
  (define (m* x y) (modulo (* x y) m))
  (cond ((zero? e) 1)
        ((even? e) (expm (m* b b) (/ e 2) m))
        (else (m* b (expm (m* b b) (/ (- e 1) 2) m)))))

(define (inverse x p) ; inverse of x mod prime p
    (expm x (- p 2) p)) ; by fermat's little theorem

(define (baby-step-giant-step x n m)
  (let* ((b (inexact->exact (ceiling (sqrt m))))
         (h (expm (inverse x m) b m))
         (a (make-hash-table)))
    (do ((i 0 (+ i 1)) ; giant steps
         (xi 1 (modulo (* xi x) m)))
        ((= i b))
      (hash-set! a xi i))
    (do ((j 0 (+ j 1)) ; baby steps
         (nhj n (modulo (* nhj h) m)))
        ((hash-ref a nhj #f)
          (+ (hash-ref a nhj #f) (* j b))))))

(display (baby-step-giant-step 3 13 17)) (newline)
(display (expm 3 4 17)) (newline)