pracma (version 0.3-0)

modpower: Power Function modulo m

Description

Calculates powers and orders modulo m.

Usage

modpower(n, k, m)
modorder(n, m)

Arguments

n, k, m

Natural numbers, m >= 1.

Value

• Natural number.

Details

modpower calculates n to the power of k modulo m.

modorder calculates the order of n in the multiplicative group module m. n and m must be coprime.

Uses brute force, trick to use binary expansion and square is not more efficient in an R implementation.

See Also

primroot

Examples

modpower(2, 100, 7)  #=> 2
modpower(3, 100, 7)  #=> 4
modorder(7, 17)      #=> 16, i.e. 7 is a primitive root mod 17

#Gauss' table of primitive roots modulo prime numbers < 100
proots <- c(2,  2,  3,  2,  2,  6,  5, 10, 10, 10, 2,  2, 10, 17,  5,  5,
            6, 28, 10, 10, 26, 10, 10,  5, 12, 62, 5, 29, 11, 50, 30, 10)
P <- primes(100)
for (i in seq(along=P)) {
    cat(P[i], "t", modorder(proots[i], P[i]), proots[i], "t", "")
}