numbers (version 0.8-5)

primroot: Primitive Root

Description

Find the smallest primitive root modulo m, or find all primitive roots.

Usage

primroot(m, all = FALSE)

Value

A natural number if m is prime, else NA.

Arguments

m

A prime integer.

all

boolean; shall all primitive roots module p be found.

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, so 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)