numbers (version 0.6-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

# NOT RUN {
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)
# }