Baby-step Giant-step


Brief description of how things work coming soon

This is a ruby script to accomplish the computation

#!/usr/bin/env ruby

n = 118
a = 5
b = 7

/ Baby step /
m = Math.sqrt(n.to_f).ceil
hashTable = {}
(0..m-1).each do |j|
    hashTable[j] = a**j % n
end

found = false
/ Giant step /
c = a ** (-m)
tmp = b
(0..m-1).each do |i|
    if hashTable.value?(tmp)
        j = hashTable.key(tmp)
        p '[+] Solution found: x = ' + (i*m + j).to_s
        found = true
        break
    end
    tmp *= c
end

if !found
    p '[-] Solution not found'
end