Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- computeLog: g base: h modulo: p
- "DiscreteLogarithm problem1"
- "compute the discrete logarithm of g to the base b"
- | lookup lhs rhs B result ginv |
- B := 2 raisedTo: 20.
- ginv := g raisedTo: (p - 2) modulo: p.
- lookup := Dictionary new.
- "1. First build a dictionary of all the possible values of the left hand size of the equation h/g^x_1"
- 0 to: B do: [:x1 |
- lhs := (h * (ginv raisedTo: x1 modulo: p)) \\ p.
- lookup at: lhs put: x1].
- "2. Then, for each value x_0 = 0, 1, 2, ..., 2^20 check if the right hand side (g^B)^x_0 is in the hash table"
- result := 0 to: B do: [:x0 |
- rhs := (g raisedTo: B modulo: p) raisedTo: x0 modulo: p.
- lookup at: rhs ifPresent: [:x1 | ^x0 * B + x1]].
- ^result
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement