pracma (version 1.1.6)

primroot: Primitive Root

Description

Find the smallest primitive root modulo m.

Usage

primroot(m)

Arguments

m

A prime integer.

Value

• A natural number if m is prime, else NA.

Details

For every prime number $m$ there exists a natural number $n$ that generates the field $F_m$, i.e. $n, n^2, ..., n^{m-1} mod (m)$ are all different.

The computation here is all brute force. As most primitive roots are relatively small, it is still reasonable fast.

One trick is to factorize $m-1$ and test only for those prime factors. In R this is not more efficient as factorization also takes some time.

References

Arndt, J. (2010). Matters Computational: Ideas, Algorithms, Source Code. Springer-Verlag, Berlin Heidelberg Dordrecht.

See Also

modpower, modorder

Examples

P <- primes(100)
R <- c()
for (p in P) {
    R <- c(R, primroot(p))
}
cbind(P, R)  # 7 is the biggest prime root here (for p=71)