Element Operations#

Arithmetic Operations#

Magma includes both the Karatsuba algorithm and the Schönhage-Strassen FFT-based algorithm for the multiplication of integers ([Aho et al., 1974, Chap. 7], [von zur Gathen and Gerhard, 1999, Sec. 8.3]). The crossover point (where the FFT method beats the Karatsuba method) is currently \(2^{15}\) bits (approx. 10000 decimal digits) on Sun SPARC workstations and \(2^{17}\) bits (approx. 40000 decimal digits) on Digital Alpha workstations. Assembler macros are used for critical operations and 64-bit operations are used on DEC-Alpha machines.

Magma also contains an asymptotically-fast integer (and polynomial) division algorithm which reduces division to multiplication with a constant scale factor that is in the practical range. Thus division of integers and polynomials are based on the Karatsuba and Schönhage-Strassen (FFT) methods when applicable. The crossover point for integer division (when the new method outperforms the classical method) is currently at the point of dividing a \(2^{12}\) bit (approx. 1200 decimal digit) integer by a \(2^{11}\) (approx. 600 decimal digit) integer on Sun SPARC workstations.

+ n: RngIntElt -> RngIntElt#
- n: RngIntElt -> RngIntElt#
m + n: RngIntElt, RngIntElt -> RngIntElt#
m - n: RngIntElt, RngIntElt -> RngIntElt#
m * n: RngIntElt, RngIntElt -> RngIntElt#
n ^ k: RngIntElt, RngIntElt -> RngIntElt#
m / n: RngIntElt, RngIntElt -> RngIntElt#
m +:= n: RngIntElt, RngIntElt -> RngIntElt#
m -:= n: RngIntElt, RngIntElt -> RngIntElt#
m *:= n: RngIntElt, RngIntElt -> RngIntElt#
m /:= n: RngIntElt, RngIntElt -> RngIntElt#
m ^:= k: RngIntElt, RngIntElt -> RngIntElt#
n div m: RngIntElt, RngIntElt -> RngIntElt#: The quotient \(q\) of the division with remainder \(n=qm+r\), where \(0\leq r<m\) or \(m<r\leq 0\) (depending on the sign of \(m\)), for integers \(n\) and \(m\neq 0\).

n mod m: RngIntElt, RngIntElt -> RngIntElt#: The remainder \(r\) of the division with remainder \(n=qm+r\), where \(0\leq r<m\) or \(m<r\leq 0\) (depending on the sign of \(m\)), for integers \(n\) and \(m\neq 0\).

ExactQuotient(n, d): RngIntElt, RngIntElt -> RngIntElt#: Assuming that the integer \(n\) is exactly divisible by the integer \(d\), return the exact quotient of \(n\) by \(d\) (as an integer). An error results if \(d\) does not divide \(n\) exactly.

n div:= m: RngIntElt, RngIntElt -> RngIntElt#

n mod:= m: RngIntElt, RngIntElt -> RngIntElt#

Bit Operations#

The following functions use bit operations on the internal representation, so are in general quicker than using the usual arithmetic operators.

ShiftLeft(n, b): RngIntElt, RngIntElt -> RngIntElt#: Given integers \(n\) and \(b\), with \(b\ge 0\), return \(n \times 2^b\).

ShiftRight(n, b): RngIntElt, RngIntElt -> RngIntElt#: Given integers \(n\) and \(b\), with \(b\ge 0\), return \(n\) div \(2^b\).

ModByPowerOf2(n, b): RngIntElt, RngIntElt -> RngIntElt#: Given integers \(n\) and \(b\), with \(b\ge 0\), return \(n \bmod 2^b\) (so the result is always non-negative).

Bitwise Operations#

The following functions apply logical operators to integers by interpreting them as sequences of bits. Note that the (implicitly infinite) 2-adic expansion of these integers is used, which enables consistent handling of negative integers. In particular, the BitwiseNot of a non-negative integer will be negative, and vice versa.

BitwiseNot(x): RngIntElt -> RngIntElt#: The integer whose 2-adic representation is the bitwise ‘not’ of the 2-adic representation of \(x\).

BitwiseAnd(x, y): RngIntElt, RngIntElt -> RngIntElt#: The integer whose 2-adic representation is the bitwise ‘and’ of the 2-adic representations of \(x\) and \(y\).

BitwiseOr(x, y): RngIntElt, RngIntElt -> RngIntElt#: The integer whose 2-adic representation is the bitwise ‘or’ of the 2-adic representations of \(x\) and \(y\).

BitwiseXor(x, y): RngIntElt, RngIntElt -> RngIntElt#: The integer whose 2-adic representation is the bitwise ‘xor’ of the 2-adic representations of \(x\) and \(y\).

Equality and Membership#

m eq n: RngIntElt, RngIntElt -> BoolElt#

m ne n: RngIntElt, RngIntElt -> BoolElt#

n in R: RngIntElt, Rng -> BoolElt#

n notin R: RngIntElt, Rng -> BoolElt#

Parent and Category#

Parent(n): RngIntElt -> RngInt#

Category(n): RngIntElt -> Cat#

Predicates on Ring Elements#

IsEven(n): RngIntElt -> BoolElt#: Returns true if the integer \(n\) is even, otherwise false.

IsOdd(n): RngIntElt -> BoolElt#: Returns true if the integer \(n\) is odd, otherwise false.

IsDivisibleBy(n, d): RngIntElt, RngIntElt -> BoolElt, RngIntElt#: Returns true if and only if the integer \(n\) is divisible by the integer \(d\); if true, the quotient of \(n\) by \(d\) is also returned.

IsSquare(n): RngIntElt -> BoolElt, RngIntElt#: Returns true if the non-negative integer \(n\) is the square of an integer, false otherwise. If \(n\) is a square, its positive square root is also returned.

IsSquarefree(n): RngIntElt -> BoolElt#: Returns true if the non-zero integer \(n\) is not divisible by the square of any prime, false otherwise.

IsPower(n): RngIntElt -> BoolElt#: If the integer \(n>1\) is a power \(n=b^k\) of an integer \(b\), with \(k>1\), this function returns true, the minimal positive \(b\) and its associated \(k\); if it is not such integer power the function returns false.

IsPower(n, k): RngIntElt, RngIntElt -> BoolElt#: If the integer \(n>1\) is \(k\)-th power, with \(k>1\), of some integer \(b\), so that \(n=b^k\), this function returns true, and \(b\); if it is not a \(k\)-th integer power the function returns false.

IsPrime(n): RngIntElt -> BoolElt#

Proof: BoolElt                    Default: true

Returns true if and only if the integer \(n\) is a prime. A rigorous primality test which returns a proven result will be used unless the parameter Proof is false. The reader is referred to Section Primes and Primality Testing for a complete description of this function.

Example: Is Prime (ex-687a13)#

In this example we find some 10-digit primes that are congruent to 3 modulo 4 such that \((p-1)/2\) is also prime.

> { p : p in [10^10+3..10^10+1000 by 4] |
>        IsPrime(p) and IsPrime((p-1) div 2)};
{ 10000000259, 10000000643 }

Run in calculator

IsIntegral(n): RngIntElt -> BoolElt#: Returns true if and only if \(a\) is integral, which is of course true for every integer \(n\).

IsSinglePrecision(n): RngIntElt -> BoolElt#: Returns true if \(n\) fits in a single word in the internal representation of integers in Magma, that is, if \(\vert n\vert<2^{30}\), false otherwise.

IsZero(n): RngIntElt -> BoolElt#

IsOne(n): RngIntElt -> BoolElt#

IsMinusOne(n): RngIntElt -> BoolElt#

IsNilpotent(n): RngIntElt -> BoolElt#

IsIdempotent(n): RngIntElt -> BoolElt#

IsUnit(n): RngIntElt -> BoolElt#

IsZeroDivisor(n): RngIntElt -> BoolElt#

IsRegular(n): RngInt -> BoolElt#

IsIrreducible(n): RngIntElt -> BoolElt#

IsPrime(n): RngIntElt -> BoolElt#

Comparison of Ring Elements#

m gt n: RngIntElt, RngIntElt -> BoolElt#

m ge n: RngIntElt, RngIntElt -> BoolElt#

m lt n: RngIntElt, RngIntElt -> BoolElt#

m le n: RngIntElt, RngIntElt -> BoolElt#

Maximum(m, n): RngIntElt, RngIntElt -> RngIntElt#

Maximum(Q): [RngIntElt] -> RngIntElt#

Minimum(m, n): RngIntElt, RngIntElt -> RngIntElt#

Minimum(Q): [RngIntElt] -> RngIntElt#

Conjugates, Norm and Trace#

ComplexConjugate(n): RngIntElt -> RngIntElt#: The complex conjugate of \(n\), which will be the integer \(n\) itself.

Conjugate(n): RngIntElt -> RngIntElt#: The conjugate of \(n\), which will be the integer \(n\) itself.

Norm(n): RngIntElt -> RngIntElt#: The norm in \({\mathbb{Q}}\) of \(n\), which will be the integer \(n\) itself.

EuclideanNorm(n): RngIntElt -> RngIntElt#: The Euclidean norm (length) of \(n\), which will equal the absolute value of \(n\).

Trace(n): RngIntElt -> RngIntElt#: The trace (in \({\mathbb{Q}}\)) of \(n\), which will be the integer \(n\) itself.

MinimalPolynomial(n): RngIntElt -> RngUPolElt#: Returns the minimal polynomial of the integer \(n\), which is the monic linear polynomial with constant coefficient \(n\) in a univariate polynomial ring \(R\) over the integers.

Other Elementary Functions#

AbsoluteValue(n): RngIntElt -> RngIntElt#
Abs(n): RngIntElt -> RngIntElt#: Absolute value of the integer \(n\).

Ilog2(n): RngIntElt -> RngIntElt#: The integral part of the logarithm to the base two of the positive integer \(n\).

Ilog(b, n): RngIntElt, RngIntElt -> RngIntElt#: The integral part of the logarithm to the base \(b\) of the positive integer \(n\) i.e., the largest integer \(k\) such that \(b^k \leq n\). The integer \(b\) must be greater than or equal to two.

Quotrem(m, n): RngIntElt, RngIntElt -> RngIntElt, RngIntElt#: Returns both the quotient \(q\) and remainder \(r\) obtained upon dividing the integer \(m\) by the integer \(n\), that is, \(m = q\cdot n+r\), where \(0 \leq r < n\) if \(n>0\) and \(n<r\leq 0\) if \(n<0\).

Valuation(x, p): RngIntElt, RngIntElt -> RngIntElt, RngIntElt#: The valuation of the integer \(x\) at the prime \(p\). This is the largest integer \(v\) for which \(p^v\) divides \(x\). If \(x = 0\) then \(v = \infty\). The optional second return value is the integer \(u\) such that \(x = p^v u\).

Iroot(a, n): RngIntElt, RngIntElt -> RngIntElt#: Given a positive integer \(a\), return the integer \(b= \lfloor\root n \of a\rfloor\), i.e. the integral part of the \(n\)-th root of \(a\). To obtain the actual root (as a real number), \(a\) must e coerced into a real field and the function Root applied.

Sign(n): RngIntElt -> RngIntElt#: Returns \(-1\), \(0\) or \(1\) depending upon whether the integer \(n\) is negative, zero or positive, respectively.

Ceiling(n): RngIntElt -> RngIntElt#: The ceiling of the integer \(n\), that is, \(n\) itself.

Floor(n): RngIntElt -> RngIntElt#: The floor of the integer \(n\), that is, \(n\) itself.

Round(n): RngIntElt -> RngIntElt#: This function rounds the integer \(n\) to itself.

Truncate(n): RngIntElt -> RngIntElt#: This function returns the integer truncation of the integer \(n\), that is, \(n\) itself.

SquarefreeFactorization(n): RngIntElt -> RngIntElt, RngIntElt#: Given a non-negative integer \(n\), return a squarefree integer \(x\) as well as a positive integer \(y\), such that \(n=xy^2\).

Isqrt(n): RngIntElt -> RngIntElt#: Given a positive integer \(n\), return the integer \(\lfloor\sqrt n\rfloor\), i.e., the integral part of the square root of the integer \(n\).