Element Operations

Arithmetic Operations

Magma includes both the Karatsuba algorithm and the Schönhage-Strassen FFT-based algorithm for the multiplication of integers ([AHU74, Chap. 7], [vzGG99, 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: Primes Congruent to 3 Modulo 4 (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 (opens in a new tab)

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\).

Element Operations#

Arithmetic Operations#

Bit Operations#

Bitwise Operations#

Equality and Membership#

Parent and Category#

Predicates on Ring Elements#

Comparison of Ring Elements#

Conjugates, Norm, and Trace#

Other Elementary Functions#