5.25 PowerMod

PowerMod( r, e, m )
PowerMod( R, r, e, m )

In the first form PowerMod returns the e-th power of the ring element r modulo the ring element m in their default ring (see DefaultRing). In the second form PowerMod returns the e-th power of the ring element r modulo the ring element m in the ring R. e must be an integer. R must be a Euclidean ring (see IsEuclideanRing) so that EuclideanRemainder (see EuclideanRemainder) can be applied to its elements.

If e is positive the result is r^e modulo m. If e is negative then PowerMod first tries to find the inverse of r modulo m, i.e., i such that i r = 1 modulo m. If the inverse does not exist an error is signalled. If the inverse does exist PowerMod returns PowerMod( R, i, -e, m ).

PowerMod reduces the intermediate values modulo m, improving performance drastically when e is large and m small.

    gap> PowerMod( Integers, 2, 20, 100 );
    76        # $2^{20} = 1048576$
    gap> PowerMod( Integers, 3, 2^32, 2^32+1 );
    3029026160        # which proves that $2^{32}+1$ is not a prime
    gap> PowerMod( Integers, 3, -1, 22 );
    15        # 3\*15 = 45 = 1 modulo 22 

PowerMod calls R.operations.PowerMod( R, r, e, m ) and returns the value.

The default function called this way is RingOps.PowerMod, which uses QuotientMod (see QuotientMod) if necessary to invert r, and then uses a right-to-left repeated squaring, reducing the intermediate results modulo m in each step. This function is seldom overlaid, because there is seldom a better way of computing the power.

Previous Up Top Next
Index