+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (49 50) Primitive Roots Modulo n (/thread-22782.html)
(49 50) Primitive Roots Modulo n - John Keith - 11-28-2024 12:44 PM
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
\>>