0
$\begingroup$

For my upcoming exam in Algorithms, as part of Cryptography, we are supposed to be able to solve these types of questions. I don't have the notes from that lecture, so I'm finding it difficult to figure out on my own.

A commented solution or references to what to I should read would be great.

Here is a an example problem:

Knowing that $7919$ and $7907$ are prime, solve the following:

$892^{(7918)(7909)}\mod(7919\cdot7907)$.

I have found this video to be very helpful: YouTube

$\endgroup$
1
$\begingroup$

Noting that the power $7918$ is one less than the prime $7919$, look up Fermat's little theorem. This also helps for the power $7909$ which is just three greater than one less than $7907$ (if you get what I mean).

Using that theorem, we get

$$\begin{align} 892^{(7918)(7909)} &\equiv \left(892^{7918}\right)^{7909} \pmod{7919} \\ &\equiv 1^{7909} \pmod{7919} \\ &\equiv 1 \pmod{7919} \end{align}$$

For the modulus that is the product of two primes, look up the Chinese remainder theorem. Using that theorem, you can find the value of the expression modulo $7919$ (as I did above), find the value modulo $7907$ (for which I gave you a hint), then combine those two to get your final value.

If you are studying cryptography, you really need to understand those two concepts well. They are discussed in just about any number theory book as well as in many web sites. You can start with the links above and continue with your own search engine.

$\endgroup$
  • $\begingroup$ Thank you sir, you have been a great help. $\endgroup$ – Airwavezx Aug 1 '15 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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