# 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](../../references.md#cite-ahohopcroftullman), Chap. 7], [[von zur Gathen and Gerhard, 1999](../../references.md#cite-gathengerhard), 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`

```magma
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](prime.md#rngint-primesfact) 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.

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

```

### `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$.