

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

I'm studying UProve, and one of the fundamental components of this technology is based upon the relationship between

i^Q mod P = 1

Lacking a specific name I can call this mathematical relationship, where can I learn more about this equation?

I've heard that not only will the equation equal one, but there are instances it may equal P.

PS - I'm not sure how to tag this so your feedback is welcome, or let me know if this is better on the math.SE

share|improve this question
"the relationship between" that equality and what? $\:$ – Ricky Demer Mar 13 '13 at 23:57
@RickyDemer Just as there is something called the Discreet Logarithm problem that's used in crypto, I think this has a name in the crypto world. I'm short on meaningful vocabulary but think this has 1) a name, 2) a context it's considered useful , 3) Other proofs that may make it useful in various applications. – LamonteCristo Mar 14 '13 at 0:01
It is useful, but I don't think it has a name. $\;\;$ If $Q$ is prime and $\: \text{mod}(i,P) \neq 1 \:$ and your equality holds, then "$i$ generates a subgroup of $\mathbb{Z}_P^*$ with order $Q$". $\;\;\;\;$ – Ricky Demer Mar 14 '13 at 0:08
Thank you @RickyDemer . I'm not familiar with the symbols ℤ∗P let alone how to type it correctly in Markup. Rather than bore this forum with these questions (unless it's on-topic), what should I learn (where should I learn it) to speak this language? – LamonteCristo Mar 14 '13 at 14:24
You should learn group theory and read $\:$ – Ricky Demer Mar 15 '13 at 17:49

A special case of the relation you've found is called Fermat's little theorem.
In a more "mathy" way this looks like:

$i^Q\equiv 1 \pmod p$

which will always hold for $Q=p-1$ and for any $Q|p-1$.

The use of this theorem is limited in cryptography, however the problem of determining $Q$, if only $i$ and $p$ are known, this problem is called "discrete logarithm problem" (assuming there isn't a "1" on the right side but rather some random number).

If $p=r*s$ and you're given $Q$ then this is called the RSA-problem (the problem if finding the Q-th root modulo p), again assuming the right side isn't 1 but rather some random number.

share|improve this answer

Your Answer


