Modular Arithmetic

In this section we describe some functions that make it possible to perform modular arithmetic without conversions to residue class rings.

Arithmetic Operations

Modexp(n, k, m) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt

The modular power n^k mod m, where n is an integer, k is an integer and m is an integer greater than one. If k is negative, n must have an inverse i modulo m, and the result is then i ^{- k} mod m. The result is always an integer r with 0≤r< m.

n mod m : RngIntElt, RngIntElt -> RngIntElt

Remainder upon dividing the integer n by the integer m. The result always has the same sign as m. An error results if m is zero.

Modinv(n, m) : RngIntElt, RngIntElt -> RngIntElt

InverseMod(n, m) : RngIntElt, RngIntElt -> RngIntElt

Given an integer n and a positive integer m, such that n and m are coprime, return an inverse u of n modulo m, that is, return an integer 1≤u<m such that u.n ≡ 1 mod m.

Modsqrt(n, m) : RngIntElt, RngIntElt -> BoolElt, RngIntElt

Given an integer n and an integer m ≥2, this function returns an integer b such that 0 ≤b < m and b² ≡ n mod m if such b exists; an error results if no such root exists.

Modorder(n, m) : RngIntElt, RngIntElt -> RngIntElt

For integers n and m, m > 1, the function returns the least integer k ≥1 such that n^k ≡ 1 mod m, or zero if gcd(n, m) != 1.

IsPrimitive(n, m) : RngIntElt, RngIntElt -> BoolElt

Returns true if n is a primitive root for m, false otherwise (0 < n < m).

PrimitiveRoot(m) : RngIntElt -> RngIntElt

Given an integer m > 1, this function returns an integer value defined as follows: If Z/mZ has a primitive root and the function is successful in finding it, the root a is returned. If Z/mZ has a primitive root but the algorithm does not succeed in finding it, or Z/mZ does not possess a primitive root, then zero is returned.

The Solution of Modular Equations

The functions described here can be used if an occasional modular operation is required; the results are integers again. For more extensive modular arithmetic it is preferable to convert to residue class ring arithmetic. See section Residue Class Rings for details.

Solution(a, b, m) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt, RngIntElt

If a solution exists to the linear congruence ax ≡ b mod m, then returns x0, k such that x = x0 + i * k represents the complete set of solutions, where i can be any integer. Otherwise, returns -1.

ChineseRemainderTheorem(X, N) : [RngIntElt], [RngIntElt] -> RngIntElt

CRT(X, N) : [RngIntElt], [RngIntElt] -> RngIntElt

Apply the Chinese Remainder Theorem to the integer sequences X and N. The sequences must have the same length, k say. The function returns the unique integer x in the range 0 ≤x < LCM(N[1].... .N[k]) such that x ≡ X[i] mod N[i]. The elements of N must all be positive integers greater than one. If there is no solution, then -1 is returned.

Solution(A, B, N) : [RngIntElt], [RngIntElt],[RngIntElt] -> RngIntElt

Return a solution x to the system of simultaneous linear congruences defined by the integer sequences A, B and N. Each of these sequences must have the same number of terms, k say. The elements of N must all be positive integers greater than one. The i-th congruence is A[i] .x ≡ B[i] mod N[i]. The solution x will satisfy 0 ≤x < LCM(N[1].... .N[k]). If no solution exists, -1 is returned.

NormEquation(d, m) : RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt

NormEquation(d, m: parameters)) : RngIntElt, RngIntElt -> BoolElt, RngIntElt, RngIntElt

    Factorization: [<RngIntElt, RngIntElt>] Default: [ ]

Given a positive integer d and a non-negative integer m, return true and two non-negative integers x and y, such that x² + y²d = m, if such a solution exists. If such a solution does not exists only the value false is returned. If the factorization of m is known, it may be supplied as the value of the parameter Factorization to speed up the computation.

> d := 957440000095744000002277749760;
> m := 5102197760510219776012138128480644;
> time NormEquation(d, m);
true 98 73
Time: 2.990
> time f := Factorization(m);
Time: 4.670
> f;
[ <2, 2>, <19, 1>, <67134181059344997052791291164219, 1> ]
> time NormEquation(d, m: Factorization := f);
true 98 73
Time: 0.420