# Generating $\mathbb{Z}^*_n$

I'm using Mathematica to illustrate basic number theory concepts in a graduate cryptography class. To generate elements of the multiplicative group of integers modulo $n$, i.e. $\mathbb{Z}^*_n$, I can use the following code:

Z[n_] := Table[If[GCD[i, n] == 1, i, ## &[]], {i, n}];


Example:

In: Z[21]
Out: {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}


The notation ## &[] used in defining Z[n_] will certainly raise questions for students who have no prior exposure to Mathematica. Is there a simpler way of generating elements of $\mathbb{Z}^*_n$?

PS: I can use:

Z[n_] := DeleteCases[Table[If[GCD[i, n] == 1, i], {i, n}], Null];


but that's not elegant either.

• How about a Select over a simple range? Commented Mar 11, 2015 at 23:39
• Z[n_] := Select[CoprimeQ[#, n] &]@Range[1, n] Commented Mar 11, 2015 at 23:45
• @evanb I just posted something very similar - simultaneously with your comment...
– Jens
Commented Mar 11, 2015 at 23:47
• Position[MultiplicativeOrder[21, #] & /@ Range@20, _?IntegerQ, 1] Commented Mar 12, 2015 at 0:08
• Select[Range[21], NumericQ@MultiplicativeOrder[21, #] &] Commented Mar 12, 2015 at 0:13

There is a simpler function instead of GCD that allows you to skip the comparison with 1: CoprimeQ. Using it, we can do this:

Z[n_] := With[{i = Range[n]}, Pick[i, CoprimeQ[i, n]]]

Z[21]

(* ==> {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20} *)


Here I deliberately tried to avoid any cryptic symbols (although perhaps that should be par for the course in a cryptography class)...

Edit speed

Considering the comment, I looked at the timings and found that my solution is also about twice as fast as the ones posted by Mr. Wizard:

AbsoluteTiming@Do[
Select[Range[n], CoprimeQ[#, n] &],
{n, 200, 3000}]

(* ==> {3.102409, Null} *)

AbsoluteTiming@Do[
Join @@ Position[Range[n]/n, _[_, n]],
{n, 200, 3000}]

(* ==> {3.367569, Null} *)

AbsoluteTiming@Do[
With[{i = Range[n]}, Pick[i, CoprimeQ[i, n]]],
{n, 200, 3000}]

(* ==> {1.692815, Null} *)


The general rule is that you get more speed if you use the listability of built-in functions, instead of doing explicit looping (or Table, or Map operations). Listability here means that you can feed a whole List into the argument of CoprimeQ, and the looping will be done at a lower level internally.

• Thanks. This is the simplest of all the suggestions. Out of curiosity, do you know which of the suggestions is the most efficient? Commented Mar 12, 2015 at 13:00
• Without doing any testing, the general rule is that you get more speed if you use the listability of built-in functions, instead of doing explicit looping (or Table, or Map operations). Listability here means that you can feed a whole List into the argument of CoprimeQ, and the looping will be done at a lower level internally. That's why I think my solution will also be efficient: it works with lists as a whole, never breaking it up into its elements.
– Jens
Commented Mar 12, 2015 at 16:02
• @Sadeq And that is exactly why I prefer Jens' solution. :-) Commented Mar 12, 2015 at 20:43
• @Mr.Wizard: Yeah, it's very elegant in that it is both the simplest (IMHO) and the most efficient! Commented Mar 12, 2015 at 20:55

I prefer Jens' solution but here is another simple formation:

z1[n_] := Select[Range[n], CoprimeQ[#, n] &]


And one for just for fun:

z2[n_] := Join @@ Position[Range[n]/n, _[_, n]]

• That second one blew my mind a little bit! +1. Commented Mar 12, 2015 at 17:48