1
$\begingroup$

I am teaching elementary number theory to first year undergraduate students. How do introduce the order of an integer modulo n and primitive roots? How do I make this a motivating topic and are there any applications of this area? I am looking at something which will have an impact.

$\endgroup$
  • 1
    $\begingroup$ How about Diffie-Hellman key exchange? $\endgroup$ – Lord Shark the Unknown Jun 15 '18 at 4:11
  • 1
    $\begingroup$ I have used Diffie-Hellman key exchange for motivation as follows. I lead up to it by designing a homework assignment where the students were asked to solve a discrete logarithm problem modulo a prime like $p=107$ (large enough, but not too large). As an aid I gave them key pieces of a homomorphism from $\Bbb{Z}_{107}^*$ to $\Bbb{Z}_{106}$ (most students, not unpredictably, didn't see how to use the homomorphism, but brute forced the solution instead). Then, in the problem session, after this problem I took the stage and outlined Diffie-Hellman. I did get positive feedback for this in the end. $\endgroup$ – Jyrki Lahtonen Jun 15 '18 at 5:34
  • $\begingroup$ I like the approach of @JyrkiLahtonen. Giving them a challenge, something to work on without extended knowledge, will make them think about the problem. After the deadline, show them the internals of the algorithm including math concepts. Also a good example for teaching can be a basic implementation, so they can rework on properties. $\endgroup$ – kub0x Jun 15 '18 at 5:42
1
$\begingroup$

Take a cyclic group of prime order minus one this is $C_{p-1}$. Then the cyclic group $C_{p-1}$ is isomorphic to the group of integers mod p. This is $C_{p-1} \cong (\mathbb{Z}/\mathbb{pZ})^{x}$. Other notations include $\mathbb{F_p}$ and $\mathbb{Z}_p^{*}$.

A primitive root $g \in \mathbb{Z_p^*}$ is an element (generator) that generates the whole group thus its order is the order of the group. Since the order of $G$ is $p-1$, we say that the order of $g$ in the group $G$ must be $p-1$ too. It results that there are $\varphi(\varphi(p))$ of them.

The concept of order can be described as:

$Ord_G(g) = n$ and is read as: the order of element $g$ in $G$ is $n$. This means that the element $g$ will generate a subgroup $H \leqslant G$ of order $n$. This is the subgroup $H = <g>$.

A further explanation on Cryptography as noted in comments can be useful to understand the role of Number Theory and Group Theory on Computer Security, concretely on Cryptosystems.

On Diffie-Hellman the modulus is prime, and the generator $g$ generates a large subgroup of order $q$ where $q$ is large enough, giving a sufficient size of residues mod p. As seen above, these concepts work well with my explanation.

After explaining Diffie-Hellman key exchange you can show how to encipher or compute digital signatures with a slight change on the scheme (Elgamal).

As for me I got interested on these branches since Crypto. Making it easy to other people may raise the chance to bring them to the field.

$\endgroup$

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.