(b) Show that the function $$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [2]^n&\mapsto n\end{align}$$ is well-defined and has the property that $\log(xy)=\log x+\log y,\log(x/y)=\log x-\log y$ and $\log x^r=r\log x$ for all $x,y\in \Bbb Z_{19}^\times$ and all $r\in \Bbb Z$.
(c) List the values of this function and use them to determine $30^{14}\;\text{mod}\;19$ and $25^{11}\;\text{mod}\;19$.
Food for thought:
Intuition for (a)? Is it related to period?
Why choose $2$ in particular? Will other numbers work? [Yes! Read till the end.]
Any applications in modular exponentiation? [Yes, discrete logarithms are used in cryptography!]
I only worked on (a) and (c).
(a) My failed attempts: I expressed $x$ as $x=2^n+19y\;\exists\; y\in \Bbb Z$ and tried to use the fact that $(2,19)=1$, which didn't work. The next day I thought of proving $$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [2]^n&\mapsto n\end{align}$$ is surjective, but I can't find $n$ in terms of $x$ explicitly. A simple proof is to prove that $\Bbb Z_{19}$ is a cyclic group with generator $2$, which follows from the results in (c).
This problem is actually related to primitive roots. If $a$ is a primitive root modulo $n$, then every element of $\Bbb Z_n$ is a power of $a$. Or in the language of group theory: $a$ is a primitive root modulo $n$ if $a$ is a generator of the multiplicative group on non-zero objects modulo $n$. Here we state without proof a handy result for proving (a): $a$ is a primitive root modulo $p$ if it has order $p-1$. [To be proved later]
Recall Fermat's little theorem: if $p$ is a prime, $x\in \Bbb Z$ and $p\not\mid a$, then $a^{p-1}\equiv_p 1$. Recall also the definition of order of $a$ modulo $n$, $\text{ord}_n a$, for positive integer $n>1$ and integer $x$, if there exists a least positive integer $k$ s.t. $a^k\equiv_n 1$, then $\text{ord}_n a=k$ is the order. When we have $\text{ord}_p a=p-1$, $a$ is a primitive root modulo $p$.
Therefore, to prove (a), we need to prove that $2$ is a primitive root modulo $19$, which is true because $2^{18}\equiv_{19}1$.
| 2^0 = 1 (mod 19) 2^1 = 2 (mod 19) 2^2 = 4 (mod 19) 2^3 = 8 (mod 19) 2^4 = 16 (mod 19) 2^5 = 13 (mod 19) 2^6 = 7 (mod 19) | 2^7 = 14 (mod 19) 2^8 = 9 (mod 19) 2^9 = 18 (mod 19) 2^10 = 17 (mod 19) 2^11 = 15 (mod 19) 2^12 = 11 (mod 19) 2^13 = 3 (mod 19) | 2^14 = 6 (mod 19) 2^15 = 12 (mod 19) 2^16 = 5 (mod 19) 2^17 = 10 (mod 19) 2^18 = 1 (mod 19) 2^19 = 2 (mod 19) 2^20 = 4 (mod 19) |
'Logarithm table' form:
n: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
log(2^n): 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10
We now find $30^{14}\;\text{mod}\;19$ and $25^{11}\;\text{mod}\;19$: $$\begin{align}30^{14}&\equiv_{19}2^{14}\;15^{14}\\
&\equiv_{19}2^{14}\;34^{14}\\
&\equiv_{19}2^{14}\;2^{14}\;17^{14}\\
&\equiv_{19}2^{14}\;2^{14}\;(-2)^{14}\\
&\equiv_{19}2^{6}\quad \qquad [2^{18}=1]\\
&\equiv_{19}7\;\;\Box
\end{align}$$
$$\begin{align}25^{11}&\equiv_{19}6^{11}\\
&\equiv_{19}2^{11}\;3^{11}\\
&\equiv_{19}2^{11}\;22^{11}\\
&\equiv_{19}2^{11}\;2^{11}\;(-8)^{11}\\
&\equiv_{19}2^4\;(-2^{33})\\
&\equiv_{19}-2\\
&\equiv_{19}17\;\;\Box
\end{align}$$
Lessons learnt:
At first I thought $[2]^n\mapsto n$ means $n$ is one value, namely, $[2]^1\mapsto 1$, but later I realised it doesn't make sense! The values of the range are just the values of $2^n\;\text{mod}\;19$, which are $1,2,3,\cdots,18$. This makes sense because there are $\phi(19)=19-1=18$ elements in $\Bbb Z_{19}^\times$, which explains why the range is $\Bbb Z_{18}$.
Also, I should rely on my brain rather than matlab: $\text{mod}(30^{14},19)$ in matlab gives $0$ but the answer is really $7$. ($\text{mod}(11^{14},19)$ in matlab gives $7$ though...)
Extensions:
| 3^0 = 1 (mod 19) 3^1 = 3 (mod 19) 3^2 = 9 (mod 19) 3^3 = 8 (mod 19) 3^4 = 5 (mod 19) 3^5 = 15 (mod 19) 3^6 = 7 (mod 19) | 3^7 = 2 (mod 19) 3^8 = 6 (mod 19) 3^9 = 18 (mod 19) 3^10 = 16 (mod 19) 3^11 = 10 (mod 19) 3^12 = 11 (mod 19) 3^13 = 14 (mod 19) | 3^14 = 4 (mod 19) 3^15 = 12 (mod 19) 3^16 = 17 (mod 19) 3^17 = 13 (mod 19) 3^18 = 1 (mod 19) 3^19 = 3 (mod 19) 3^20 = 9 (mod 19) |
Replacing $2$ by $3$ works.
$$\log:\begin{align}\Bbb Z_{19}^\times&\to \Bbb Z_{18}\\ [3]^n&\mapsto n\end{align}\\ 30^{14}\equiv_{19}3^{14}\;(-3)^{28}\equiv_{19}3^6\equiv_{19}7\\ 25^{11}\equiv_{19}6^{11}\equiv_{19}2^{11}3^{11}\equiv_{19}15\cdot 10\equiv_{19}17$$ In fact, $10,13,14,15$ also work because they are also primitive roots. (Question: How to find all primitive roots modulo a number?)
More to learn:
cryptography
an advanced proof that $\Bbb Z_p^\times \cong \Bbb Z_{p-1}$
cyclicity of $\Bbb Z_p^\times$
using primitive roots to solve problems
No comments:
Post a Comment