11.9 RootMod

RootMod( n, m )
RootMod( n, k, m )

In the first form RootMod computes a square root of the integer n modulo the positive integer m, i.e., an integer r such that r^2 = n mod m. If no such root exists RootMod returns false.

A root of n exists only if Legendre(n,m) = 1 (see Legendre). If m has k different prime factors then there are 2^k different roots of n mod m. It is unspecified which one RootMod returns. You can, however, use RootsUnityMod (see RootsUnityMod) to compute the full set of roots.

In the second form RootMod computes a kth root of the integer n modulo the positive integer m, i.e., an integer r such that r^k = n mod m. If no such root exists RootMod returns false.

In the current implementation k must be a prime.

RootMod is efficient even for large values of m, actually most time is usually spent factoring m (see FactorsInt).

    gap> RootMod( 64, 1009 );
    1001        # note 'RootMod' does not return 8 in this case but -8
    gap> RootMod( 64, 3, 1009 );
    518
    gap> RootMod( 64, 5, 1009 );
    656
    gap> List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ),
    >          x -> x mod 1009 );
    [ 1001, 8 ]        # set of all square roots of 64 mod 1009 

Previous Up Top Next
Index