In this section we describe a few functions that make it possible to do modular arithmetic without conversions to residue class rings.
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.
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.
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.
Given an integer n and an integer m >= 2, this function returns an integer b such that 0 <= b < m and b^2 = n mod m if such b exists; an error results if no such root exists.
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.
True if n is a primitive root for m, false otherwise (0 < n < m).
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 functions descibed 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.
ChineseRemainderTheorem(a, b, m) : RngIntElt, RngIntElt, RngIntElt -> RngIntElt
Given integers a and b, return a solution x to the linear congruence a.x = b mod m, if it exists, where m is an integer greater than one. An error results if no such solution exists.
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 terms of N must all be positive integers greater than one, and they must be pairwise coprime. The i-th congruence is A[i] * x = B[i] mod N[i]. The solution x will satisfy 0 <= x <= N[1] * ... * N[k]. If no solution exists, an error results.
Factorization: [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.
> 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