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