15.3 Roots Modulo Integers

Jacobi returns the value of the Jacobi symbol of the integer n modulo the integer m.

Suppose that m = p₁ p₂ .. p_k is a product of primes, not necessarily distinct. Then for n coprime to m the Jacobi symbol is defined by J(n/m) = L(n/p₁) L(n/p₂) .. L(n/p_k), where L(n/p) is the Legendre symbol (see Legendre). By convention J(n/1) = 1. If the gcd of n and m is larger than 1 we define J(n/m) = 0.

If n is a quadratic residue modulo m, i.e., if there exists an r such that r² = n mod m then J(n/m) = 1. However J(n/m) = 1 implies the existence of such an r only if m is a prime.

Jacobi is very efficient, even for large values of n and m, it is about as fast as the Euclidean algorithm (see Gcd).

gap> Jacobi( 11, 35 );
1         # 9^2 = 11 mod 35
gap> Jacobi( 6, 35 );
-1        # thus there is no r such that r^2 = 6 mod 35
gap> Jacobi( 3, 35 );
1         # even though there is no r with r^2 = 3 mod 35

Legendre returns the value of the Legendre symbol of the integer n modulo the positive integer m.

The value of the Legendre symbol L(n/m) is 1 if n is a quadratic residue modulo m, i.e., if there exists an integer r such that r² = n mod m and -1 otherwise.

If a root of n exists it can be found by RootMod (see RootMod).

While the value of the Legendre symbol usually is only defined for m a prime, we have extended the definition to include composite moduli too. The Jacobi symbol (see Jacobi) is another generalization of the Legendre symbol for composite moduli that is much cheaper to compute, because it does not need the factorization of m (see FactorsInt).

A description of the Jacobi symbol, the Legendre symbol, and related topics can be found in: A. Baker, The theory of numbers, Cambridge University Press, 1984, 27-33

gap> Legendre( 5, 11 );
1         # 4^2 = 5 mod 11
gap> Legendre( 6, 11 );
-1        # thus there is no r such that r^2 = 6 mod 11
gap> Legendre( 3, 35 );
-1        # thus there is no r such that r^2 = 3 mod 35

RootMod computes a kth root of the integer n modulo the positive integer m, i.e., a r such that r^k = n mod m. If no such root exists RootMod returns fail. If only the arguments n and m are given, the default value for k is 2.

In the current implementation k must be a prime.

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

RootMod is efficient even for large values of m, in fact the 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

RootsMod computes the set of kth roots of the integer n modulo the positive integer m, ie. the r such that r^k = n mod m. If only the arguments n and m are given, the default value for k is 2.

In the current implementation k must be a prime.

gap> RootsMod( 1, 7*31 );   # the same as `RootsUnityMod( 7*31 )'
[ 1, 92, 125, 216 ]
gap> RootsMod( 7, 7*31 );
[ 21, 196 ]
gap> RootsMod( 5, 7*31 );
[  ]
gap> RootsMod( 1, 5, 7*31 );
[ 1, 8, 64, 78, 190 ]

RootsUnityMod returns the set of k-th roots of unity modulo the positive integer m, i.e., the list of all solutions r of r^k = 1 mod m. If only the argument m is given, the default value for k is 2.

In general there are kⁿ such roots if the modulus m has n different prime factors p such that p = 1 mod k. If k² divides m then there are kⁿ⁺¹ such roots; and especially if k = 2 and 8 divides m there are 2ⁿ⁺² such roots.

In the current implementation k must be a prime.

gap> RootsUnityMod( 7*31 );  RootsUnityMod( 3, 7*31 );
[ 1, 92, 125, 216 ]
[ 1, 25, 32, 36, 67, 149, 156, 191, 211 ]
gap> RootsUnityMod( 5, 7*31 );
[ 1, 8, 64, 78, 190 ]
gap> List( RootMod( 64, 1009 ) * RootsUnityMod( 1009 ),
>          x -> x mod 1009 );
[ 1001, 8 ]        # set of all square roots of 64 mod 1009

[Top] [Previous] [Up] [Next] [Index]