# 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://mathematica.stackexchange.com/questions/77087/generating-mathbbz-n", "fetch_time": 1723681334000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-33/segments/1722641137585.92/warc/CC-MAIN-20240814221537-20240815011537-00769.warc.gz", "warc_record_offset": 294704198, "warc_record_length": 42479, "token_count": 1076, "char_count": 3473, "score": 3.53125, "int_score": 4, "crawl": "CC-MAIN-2024-33", "snapshot_type": "latest", "language": "en", "language_score": 0.8100615739822388, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00038-of-00064.parquet"}