New answers tagged

1

If $n$ is prime, $\mathbb{Z}_n^{*}$ has a primitive root $g$ and order $n-1$. So if $e$ divides $n-1$ you have $(g^{\frac{n-1}{e}})^e=1$. For $n=11$ you have e.g. the primitive root $g=2$ and therefore with $$b\equiv 2^{10/5}\equiv 2^2 \equiv 4 \pmod {11}$$ you compute $$b^5 \equiv 4^5 \equiv 1024 \equiv 1 \pmod {11}.$$ With the remaining primitive roots $...


7

Claim: If $A$ and $B$ are coprime, the map $$\begin{align*} \{0,\dots,B-1\}\ &\to\ \{0,\dots,B-1\} ,\\ x \ &\mapsto\ A\cdot x\bmod B \end{align*}$$ is a well-defined bijection. It is clear directly from the definition of $\bmod$ that $A\cdot x\bmod B$ is indeed between $0$ and $B-1$. Surjectivity follows, e.g., from Bézout's lemma. Any surjection ...


6

When choosing the public exponent $e$, if the value chosen is the first coprime after $\phi(n)/2$ then the resulting public and private exponents are equal. Well, yeah, that'll always be true. Why does this happen? We have $e=d$ whenever we have both of the following true: $$e^2 \equiv 1 \pmod{p-1}$$ $$e^2 \equiv 1 \pmod{q-1}$$ Now, if $e = (...



Top 50 recent answers are included