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\bmod 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}\bmod m\). The result is always an integer \(r\) with \(0\leq 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\leq u<m\) such that \(u\cdot n\equiv 1\bmod m\).

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

Given an integer \(n\) and an integer \(m \geq 2\), this function returns an integer \(b\) such that \(0 \leq b < m\) and \(b^2\equiv n\bmod 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 \geq 1\) such that \(n^k \equiv 1 \bmod m\), or zero if \(\gcd(n, m) \neq 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 \({\mathbb{Z}}/m{\mathbb{Z}}\) has a primitive root and the function is successful in finding it, the root \(a\) is returned. If \({\mathbb{Z}}/m{\mathbb{Z}}\) has a primitive root but the algorithm does not succeed in finding it, or \({\mathbb{Z}}/m{\mathbb{Z}}\) 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\equiv b \bmod 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 \leq x < LCM(N[1]\cdot\ldots\cdot N[k])\) such that \(x \equiv X[i] \bmod 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] \cdot x \equiv B[i] \bmod N[i]\). The solution \(x\) will satisfy \(0 \leq x < LCM(N[1]\cdot\ldots\cdot 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^2+y^2d = 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.

Example: Norm Equation (ex-a39523)

> 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

Run in calculatorCopy input