(49 50) Primitive Roots Modulo n

[John Keith]

Two programs regarding primitive roots. The programs require the libraries ListExt and IFACTOR, and Gerald H's ORD (multiplicative order, see also this post).

The first program 'NOPR' returns the number of primitive roots modulo n.

Code:


\<< I\->R \-> n
  \<< n 4.
    IF \<=
    THEN n 1. \>=              @ 1 <= n <= 4 have one primitive root
    ELSE n DUP 2. MOD NOT
      { 2 / } IFT              @ Divide by 2 if even
      IFACTOR DUP 2
      IF POS                   @ More than one factor of 2?
      THEN DROP 0.             @ Then no primitive roots
      ELSE LEQ                 @ Is a prime power if all factors equal
      END
      IF DUP                   @ Primitive roots exist?
      THEN DROP n EULER EULER  @ Number of primitive roots = Phi(Phi(n))
      END
    END
  \>>
\>>

The second program 'LOPR' returns a list of all primitive roots modulo n. If n has no primitive roots, the list will be empty, otherwise the size of the list will be Phi(Phi(n)). Equivalent to the Wolfram language (Mathematica) function PrimitiveRootList.
Execution time is roughly proportional to n.

Code:


\<< DUP I\->R DUP 4.
  IF \<=
  THEN 1. \>=
    { 1 - 1. \->LIST }
    { DROP { } } IFTE            @ Cheat for n <= 4.
  ELSE DUP EULER \-> n m         @ m = Phi(n)
    \<< 0 n 2 n 1 - LSEQR ORD +  @ Multiplicative order of n mod {2..n-1}
      m MPOS                     @ Positions of Phi(n)
      DUP SIZE :: R\->I IFT      @ Clean up list if non-empty
    \>>
  END
\>>