Deriving formula for function F(g,h,n) such that (g^a)%N = h%N

Question

I have a maths / coding assignment in which I am required to write a code to find the value of a for given values of g,h and N such that:

(g^a)%N = h%N

where % operator returns the remainder after dividing the 2 numbers (example: 5%2 = 1)

Since there is no other information given,I can't convert the equation to g^a = N.m + h%N where m is another integer used to reverse the modulus process.

How can I derive a formula for a?

Answer 1

Your equation (g^a)%N = h%N is equivalent to

$$g^a \equiv h \pmod N$$

The problem of finding $a$ is known as the discrete logarithm, and no efficient algorithm is known. The simplest way to find the smallest solution is to write a loop checking each (g^a)%N until it is equal to h%N.

However $g^a$ gets large quite quickly. You can use the fact that (g*((g^a)%N))%N = g^(a+1)%N to make the numbers involved smaller.