primroot {numbers}

Primitive Root

Description

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

Usage

primroot(m, all = FALSE)

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.

Value

A natural number if m is prime, else NA.

Note

This function is not vectorized.

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)