Modular arithmetic

Question

I'm new to cryptography and modular arithmetic. So, I'm sure it's a silly question, but I can't help it.

How do I calculate a from
     pow(a,q) = 1 (mod p),
where p and q are known? I don't get the "1 (mod p)" part, it equals to 1, doesn't it? If so, than what is "mod p" about?
Is this the same as
     pow(a,-q) (mod p) = 1?

Answer 1

Not silly at all, as this is the basis for public-key encryption. You can find an excellent discussion on this at http://home.scarlet.be/~ping1339/congr.htm#The-equation-a%3Csup%3Ex.

PKI works by choosing p and q that are large and relatively prime. One (say p) becomes your private key and the other (q) is your public key. The encryption is "broken" if an attacker guesses p, given aq (the encrypted message) and q (your public key).

So, to answer your question:

aq = 1 mod p

This means aq is a number that leaves a remainder of 1 when divided by p. We don't care about the integer portion of the quotient, so we can write:

aq / p = n + 1/p

for any integer value of n. If we multiply both sides of the equation by p, we have:

aq = np + 1

Solving for a we have:

a = (np+1)^1/q

The final step is to find a value of n that generates the original value of a. I don't know of any way to do this other than trial and error -- which equates to a "brute force" attempt to break the encryption.