Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

1 Answer 1

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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.