2
$\begingroup$

I am doing practice problems for my upcoming final exam, and am having trouble with this RSA encryption problem. If any one could check to see if i did these correctly, it would be greatly appreciated.

For (a) I got $\mathbb{Z}^*_8 = \{1,2,3,4,5,6,7\}$,

(b) i got $3*3 = 1 \text{ mod } 8 = 3^{-1} = 3$

(c) this one i am not sure how to do

(d) $M = N^d \text{ mod } 15$, i got $d = 3$, so $M = 4^3 \text{ mod } 15 = 4$

enter image description here

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ For (a), only elements co-prime to $n$ are in $\mathbb{Z}^*_n$, in other words $x \in \mathbb{Z}^*_n$ iff $gcd(x, n) = 1$. Therefore $Z^*_8 = \{1,3,5,7\}$. You can read more about multiplicative groups here. $\endgroup$
    – puzzlepalace
    May 9, 2016 at 23:17

1 Answer 1

Reset to default
1
$\begingroup$

(a) $\mathbb{Z}_8^* = \{1,3,5,7\}$.

(b) $x = 3$.

(c) Assuming $a \in \mathbb{Z}^*_{15}$: $a^8 \bmod 15 = 1$ and $a^9 \bmod 15 = a$.

(d) $M = 4$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ can you explain how a^9 mod 15 = a? $\endgroup$
    – spatel
    May 10, 2016 at 1:39
  • $\begingroup$ @spatel: Since $a^8 \equiv 1 \pmod{15}$, it follows that $a^9 \equiv a^8 \cdot a \equiv a \pmod{15}$ and $a \bmod 15 = a$ for $a \in \mathbb{Z}^*_{15}$. $\endgroup$
    – user94293
    May 10, 2016 at 2:13
  • $\begingroup$ @spatel: More generally, note that $a^9 \equiv a \pmod{15}$ for any $a \in \mathbb{Z}_{15}$ ---the relation $a^8 \equiv 1 \pmod {15}$ assumes $a \in \mathbb{Z}_{15}^*$. $\endgroup$
    – user94293
    May 10, 2016 at 2:24
  • $\begingroup$ This answer is not quite correct. Note that the question is not $a \in \mathbb{Z}^*_{15}$ but is rather $a \in \mathbb{Z}_{15}$. If we set $a = 5$ for instance we get $5^8 = 10 \text{ mod } 15,$ so not all $a \in \mathbb{Z}_{15}$ are congruent to 1 when raised to the 8th power. $\endgroup$
    – puzzlepalace
    May 10, 2016 at 2:31
  • $\begingroup$ @puzzlepalace: Corrected. Let $a \in \mathbb{Z}_{15}$. If $3$ divides $a$ then $a^8 \bmod 15 = 6$ and if $5$ divides $a$ then $a^8 \bmod 15 = 10$. $\endgroup$
    – user94293
    May 10, 2016 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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