6
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ Thanks. This is the simplest of all the suggestions. Out of curiosity, do you know which of the suggestions is the most efficient? $\endgroup$ – M.S. Dousti Mar 12 '15 at 13:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Jens Mar 12 '15 at 16:02
  • $\begingroup$ @Sadeq And that is exactly why I prefer Jens' solution. :-) $\endgroup$ – Mr.Wizard Mar 12 '15 at 20:43
  • $\begingroup$ @Mr.Wizard: Yeah, it's very elegant in that it is both the simplest (IMHO) and the most efficient! $\endgroup$ – M.S. Dousti Mar 12 '15 at 20:55
5
$\begingroup$

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]]
$\endgroup$
  • 3
    $\begingroup$ That second one blew my mind a little bit! +1. $\endgroup$ – evanb Mar 12 '15 at 17:48

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.