0

In the discrete log problem we have to find the exponent, which is a hard problem but what if instead we wanted to find $a$ (the generator). I couldn't find it if there is already a question about it.

So, if we have:

$$b = a^x \mod n$$

where $n$ is a large prime number.

How would I find $a$ if I have the rest of the values?

So let's take an example (with a much smaller prime $n$):

$$54235492 = a^{83} \mod 90000083$$

How then can $a$ be found? If you can please use the example, I would be much obliged.

BlackAdder
  • 4,029
Rubenisme
  • 103
  • 3
    Since $83$ does not divide $90000083-1$, let $m$ be its modular inverse, and compute $54235492^m \pmod{90000083}$. It's not as easy if the exponent is not coprime to the totient of the modulus, but then $a$ is not unique (if it exists at all). – Daniel Fischer Jan 16 '14 at 23:56
  • @Rubenisme: $a = 56$. – Amzoti Jan 17 '14 at 00:06
  • Thnx @DanielFischer! In my example n is prime, what if it isn't? What can be done in this case? – Rubenisme Jan 18 '14 at 16:44
  • For prime powers, it is similar, since the multiplicative group of $\mathbb{Z}/(p^n)$ is also cyclic. For general composite moduli $m$, solve it modulo each prime power dividing $m$, and combine the solutions with the Chinese Remainder Theorem. – Daniel Fischer Jan 18 '14 at 18:21

1 Answers1

1

Find $x$ such that $83x\equiv 1\bmod 90000082$ by using the Extended Euclidean Algorithm.

This gives 86747067.

So $54235492^{86747067}\equiv(a^{83})^{86747067}\equiv a\bmod 90000083$, since we know that $a^{90000082}\equiv 1\bmod 90000083$.

You can calculate this by repeating squaring to get an answer of 56.

user11977
  • 1,416
  • Thanks, that really helped together with @Daniel-Fischer. I don't fully understand it all yet but at least I can compute it. In my example n is prime, what if it isn't? What can be done in this case? – Rubenisme Jan 17 '14 at 14:41