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

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

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
```
a
```
```
q
```
(the encrypted message) and
```
q
```
(your public key).
So, to answer your question:
```
a
```
```
q
```
= 1 mod
```
p
```
This means
```
a
```
```
q
```
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:
```
a
```
```
q
```
/
```
p
```
=
```
n
```
+ 1/
```
p
```
for
any integer value of
```
n
```
.  If we multiply both sides of the equation by
```
p
```
, we have:
```
a
```
```
q
```
=
```
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.