Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So far I got:

$7\alpha \equiv 1$ mod $\phi(6161)$

$\phi(6161) = \phi(61) \times \phi(101) = 6000$
$7\alpha \equiv 1$(mod $6000)$

At this point we are supposed to do euclid's algorithm and somehow arrive at:

$D: x\to x^{5143}$ mod $6161$

I don't understand the euclid step

share|improve this question
    
6161=61*101 does have a primitive root, you can not take Discrete Logarithm, right? For a number $m$ having primitive root $g$, Discrete Logarithm will lead to $ind_g(7\alpha)\equiv 0\pmod {\phi(m)}$ and $ind_g(7\alpha)=ind_g7+ind_g\alpha$ mathworld.wolfram.com/DiscreteLogarithm.html –  lab bhattacharjee Sep 22 '12 at 16:01

3 Answers 3

up vote 2 down vote accepted

Start the Euclidean Algorithm. So we divide $6000$ by $7$. The quotient is $857$ and the remainder is $1$, that is, $$6000=(7)(857)+1.$$ Now the Euclidean Algorithm is over! We have reached a remainder of $1$. Thus $$1=(7)(-857)+6000.$$ So we have expressed $1$ as an integer linear combination of $7$ and $6000$. But we want the decoding index to be positive. So we want to replace $-857$ by a positive number congruent to $-857$ modulo $6000$. We have $-857\equiv 6000-857\pmod{6000}$. But $6000-857=5143$, so $$(7)(5143)\equiv 1 \pmod{6000}.$$ We have found the modular inverse of $7$ modulo $6000$. This is the decoding index.

In general, the Euclidean Algorithm takes substantially longer, so the back substitution process is not properly illustrated by this example.

share|improve this answer
    
Thank you! This explains it quite well. I was a bit jaded by the minus sign and wasn't sure what to do with it. I see now! –  Arvin Sep 22 '12 at 16:15

If 7 is the exponent you use to encrypt, then $\alpha$ should decrypt. What is the inverse to 7 modulo 6000? This is where the Euclidean algorithm comes in.

share|improve this answer

Hint $\rm\ mod\ m = 1\!+\!7k\!:\,\ 1\equiv -7\,\color{#C00}k\ \Rightarrow\ \dfrac{1}7\,\equiv\, \dfrac{-7k}{\ 7}\, \equiv\, -\color{#C00}k$

Therefore $\rm\ m = 6000 = 1+ 7\cdot \color{#C00}{857}\ \Rightarrow\: \dfrac{1}{7}\,\equiv\, -\color{#C00}{857}\equiv 5143\pmod{6000}$

Generally one can employ the Extended Euclidean Algorithm to compute modular inverses. The above is an optimization for the frequent special case where the modulus is $\equiv \pm1\:$ modulo the number being inverted ($= 7$ above), so the algorithm terminates in a single step.

share|improve this answer

Your Answer

 
discard

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.