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

OyBiYWJ5IHN0ZXBzLCBnaWFudCBzdGVwcwoKKGRlZmluZSAoZXhwbSBiIGUgbSkKICAoZGVmaW5lIChtKiB4IHkpIChtb2R1bG8gKCogeCB5KSBtKSkKICAoY29uZCAoKHplcm8/IGUpIDEpCiAgICAgICAgKChldmVuPyBlKSAoZXhwbSAobSogYiBiKSAoLyBlIDIpIG0pKQogICAgICAgIChlbHNlIChtKiBiIChleHBtIChtKiBiIGIpICgvICgtIGUgMSkgMikgbSkpKSkpCgooZGVmaW5lIChpbnZlcnNlIHggcCkgOyBpbnZlcnNlIG9mIHggbW9kIHByaW1lIHAKICAgIChleHBtIHggKC0gcCAyKSBwKSkgOyBieSBmZXJtYXQncyBsaXR0bGUgdGhlb3JlbQoKKGRlZmluZSAoYmFieS1zdGVwLWdpYW50LXN0ZXAgeCBuIG0pCiAgKGxldCogKChiIChpbmV4YWN0LT5leGFjdCAoY2VpbGluZyAoc3FydCBtKSkpKQogICAgICAgICAoaCAoZXhwbSAoaW52ZXJzZSB4IG0pIGIgbSkpCiAgICAgICAgIChhIChtYWtlLWhhc2gtdGFibGUpKSkKICAgIChkbyAoKGkgMCAoKyBpIDEpKSA7IGdpYW50IHN0ZXBzCiAgICAgICAgICh4aSAxIChtb2R1bG8gKCogeGkgeCkgbSkpKQogICAgICAgICgoPSBpIGIpKQogICAgICAoaGFzaC1zZXQhIGEgeGkgaSkpCiAgICAoZG8gKChqIDAgKCsgaiAxKSkgOyBiYWJ5IHN0ZXBzCiAgICAgICAgIChuaGogbiAobW9kdWxvICgqIG5oaiBoKSBtKSkpCiAgICAgICAgKChoYXNoLXJlZiBhIG5oaiAjZikKICAgICAgICAgICgrIChoYXNoLXJlZiBhIG5oaiAjZikgKCogaiBiKSkpKSkpCgooZGlzcGxheSAoYmFieS1zdGVwLWdpYW50LXN0ZXAgMyAxMyAxNykpIChuZXdsaW5lKQooZGlzcGxheSAoZXhwbSAzIDQgMTcpKSAobmV3bGluZSk=