commands → powmod

powmod(A,B,P)
powmod(A,B,C,X)
powmod(A,B,C,X,P)

The powmod command computes A^B modulo P efficiently. If B is negative, the inverse of A mod P is computed, and if this inverse does not exist null is returned. In the case of polynomials the fourth argument X specifies the variable and an optional fifth argument P specifies the modulus.

Examples 

# integers
powmod(2,500,11);
	1

# polynomials
powmod(x+1,10,2*x+1,x);
	1/1024

# polynomials mod p
powmod(x+1,10,2*x+1,x,11);
	1

Algorithm

The algorithm uses binary powering modulo P.

References

Gullberg, Jan. Mathematics: From the Birth of Numbers. Norton, 1996.