Integers

The default integer type in Nemo is provided by Flint. The associated ring of integers is represented by the constant parent object called FlintZZ.

For convenience we define

ZZ = FlintZZ

so that integers can be constructed using ZZ instead of FlintZZ. Note that this is the name of a specific parent object, not the name of its type.

The types of the integer ring parent objects and elements of the associated rings of integers are given in the following table according to the library provding them.

Library	Element type	Parent type
Flint	`fmpz`	`FlintIntegerRing`

All integer element types belong directly to the abstract type RingElem and all the integer ring parent object types belong to the abstract type Ring.

Integer functionality

Nemo integers implement the whole of the ring and Euclidean ring interfaces of AbstractAlgebra.jl.

https://nemocas.github.io/AbstractAlgebra.jl/rings.html

https://nemocas.github.io/AbstractAlgebra.jl/euclidean.html

Below, we describe the functionality that is specific to the Nemo/Flint integer ring.

Constructors

ZZ(n::Integer)

Coerce a Julia integer value into the integer ring.

ZZ(n::String)

Parse the given string as an integer.

ZZ(n::Float64)
ZZ(n::Float32)
ZZ(n::Float16)
ZZ(n::BigFloat)

Coerce the given floating point number into the integer ring, assuming that it can be exactly represented as an integer.

Basic manipulation

AbstractAlgebra.Generic.isunit — Method.

isunit(a::fmpz)

Return true if the given integer is a unit, i.e. $\pm 1$, otherwise return false.

Base.sign — Method.

sign(a::fmpz)

Returns the sign of $a$, i.e. $+1$, $0$ or $-1$.

Base.size — Method.

size(a::fmpz)

Returns the number of limbs required to store the absolute value of $a$.

Nemo.fits — Method.

fits(::Type{UInt}, a::fmpz)

Returns true if the given integer fits into a UInt, otherwise returns false.

Nemo.fits — Method.

fits(::Type{Int}, a::fmpz)

Returns true if the given integer fits into an Int, otherwise returns false.

Base.denominator — Method.

denominator(a::fmpz)

Returns the denominator of $a$ thought of as a rational. Always returns $1$.

Base.numerator — Method.

numerator(a::fmpz)

Returns the numerator of $a$ thought of as a rational. Always returns $a$.

Examples

a = ZZ(12)

isunit(a)
sign(a)
s = size(a)
fits(Int, a)
n = numerator(a)
d = denominator(a)

Nemo also provides a large number of Euclidean division operations. Recall that for a dividend $a$ and divisor $b$, we can write $a = bq + r$ with $0 \leq |r| < |b|$. We call $q$ the quotient and $r$ the remainder.

We distinguish three cases. If $q$ is rounded towards zero, $r$ will have the same sign as $a$. If $q$ is rounded towards plus infinity, $r$ will have the opposite sign to $b$. Finally, if $q$ is rounded towards minus infinity, $r$ will have the same sign as $b$.

In the following table we list the division functions and their rounding behaviour. We also give the return value of the function, with $q$ representing return of the quotient and $r$ representing return of the remainder.

Function	Return	Rounding
`divrem(a::fmpz, b::fmpz)`	q, r	towards zero
`tdivrem(a::fmpz, b::fmpz)`	q, r	towards zero
`fdivrem(a::fmpz, b::fmpz)`	q, r	towards minus infinity

Nemo also offers the following ad hoc division operators. The notation and description is as for the other Euclidean division functions.

Function	Return	Rounding
`rem(a::fmpz, b::Int)`	r	towards zero
`div(a::fmpz, b::Int)`	q	towards zero
`tdiv(a::fmpz, b::Int)`	q	towards zero
`fdiv(a::fmpz, b::Int)`	q	towards minus infinity
`cdiv(a::fmpz, b::Int)`	q	towards plus infinity

The following functions are also available, for the case where one is dividing by a power of $2$. In other words, for Euclidean division of the form $a = b2^{d} + r$. These are useful for bit twiddling.

Function	Return	Rounding
`tdivpow2(a::fmpz, d::Int)`	q	towards zero
`fdivpow2(a::fmpz, d::Int)`	q	towards minus infinity
`fmodpow2(a::fmpz, d::Int)`	r	towards minus infinity
`cdivpow2(a::fmpz, d::Int)`	q	towards plus infinity

Examples

a = fmpz(12)
b = fmpz(5)

q, r = divrem(a, b)
c = cdiv(a, b)
d = fdiv(a, b)
f = tdivpow2(a, 2)
g = fmodpow2(a, 3)

Comparison

Instead of isless we implement a function cmp(a, b) which returns a positive value if $a > b$, zero if $a == b$ and a negative value if $a < b$. We then implement all the other operators, including == in terms of cmp.

For convenience we also implement a cmpabs(a, b) function which returns a positive value if $|a| > |b|$, zero if $|a| == |b|$ and a negative value if $|a| < |b|$. This can be slightly faster than a call to cmp or one of the comparison operators when comparing nonnegative values for example.

Here is a list of the comparison functions implemented, with the understanding that cmp provides all of the comparison operators listed above.

Function
`cmp(a::fmpz, b::fmpz)`
`cmpabs(a::fmpz, b::fmpz)`

We also provide the following ad hoc comparisons which again provide all of the comparison operators mentioned above.

Function
`cmp(a::fmpz, b::Int)`
`cmp(a::Int, b::fmpz)`
`cmp(a::fmpz, b::UInt)`
`cmp(a::UInt, b::fmpz)`

Examples

a = ZZ(12)
b = ZZ(3)

a < b
a != b
a > 4
5 <= b
cmpabs(a, b)

Shifting

Base.:<< — Method.

<<(x::fmpz, c::Int)

Return $2^cx$ where $c \geq 0$.

Base.:>> — Method.

>>(x::fmpz, c::Int)

Return $x/2^c$, discarding any remainder, where $c \geq 0$.

Examples

a = fmpz(12)

a << 3
a >> 5

Modular arithmetic

Nemo.sqrtmod — Method.

sqrtmod(x::fmpz, m::fmpz)

Return a square root of $x (\mod m)$ if one exists. The remainder will be in the range $[0, m)$. We require that $m$ is prime, otherwise the algorithm may not terminate.

AbstractAlgebra.crt — Method.

crt(r1::fmpz, m1::fmpz, r2::fmpz, m2::fmpz, signed=false)

Find $r$ such that $r \equiv r_1 (\mod m_1)$ and $r \equiv r_2 (\mod m_2)$. If signed = true, $r$ will be in the range $-m_1m_2/2 < r \leq m_1m_2/2$. If signed = false the value will be in the range $0 \leq r < m_1m_2$.

AbstractAlgebra.crt — Method.

crt(r1::fmpz, m1::fmpz, r2::Int, m2::Int, signed=false)

Find $r$ such that $r \equiv r_1 (\mod m_1)$ and $r \equiv r_2 (\mod m_2)$. If signed = true, $r$ will be in the range $-m_1m_2/2 < r \leq m_1m_2/2$. If signed = false the value will be in the range $0 \leq r < m_1m_2$.

Examples

c = sqrtmod(ZZ(12), ZZ(13))
d = crt(ZZ(5), ZZ(13), ZZ(7), ZZ(37), true)

Integer logarithm

Nemo.flog — Method.

flog(x::fmpz, c::fmpz)

Return the floor of the logarithm of $x$ to base $c$.

Nemo.flog — Method.

flog(x::fmpz, c::Int)

Return the floor of the logarithm of $x$ to base $c$.

Nemo.clog — Method.

clog(x::fmpz, c::fmpz)

Return the ceiling of the logarithm of $x$ to base $c$.

Nemo.clog — Method.

clog(x::fmpz, c::Int)

Return the ceiling of the logarithm of $x$ to base $c$.

Examples

a = fmpz(12)
b = fmpz(2)

c = flog(a, b)
d = clog(a, 3)

Integer roots

Base.isqrt — Method.

isqrt(x::fmpz)

Return the floor of the square root of $x$.

Nemo.isqrtrem — Method.

isqrtrem(x::fmpz)

Return a tuple $s, r$ consisting of the floor $s$ of the square root of $x$ and the remainder $r$, i.e. such that $x = s^2 + r$. We require $x \geq 0$.

Nemo.root — Method.

root(x::fmpz, n::Int)

Return the floor of the $n$-the root of $x$. We require $n > 0$ and that $x \geq 0$ if $n$ is even.

Examples

a = ZZ(13)

b = sqrt(a)
s, r = sqrtrem(a)
c = root(a, 3)

Number theoretic functionality

Nemo.divisible — Method.

divisible(x::fmpz, y::Int)

Return true if $x$ is divisible by $y$, otherwise return false. We require $x \neq 0$.

Nemo.divisible — Method.

divisible(x::fmpz, y::fmpz)

Return true if $x$ is divisible by $y$, otherwise return false. We require $x \neq 0$.

AbstractAlgebra.Generic.issquare — Method.

issquare(x::fmpz)

Return true if $x$ is a square, otherwise return false.

Nemo.isprime — Method.

isprime(x::fmpz)

Return true if $x$ is a prime number, otherwise return false.

Nemo.isprobabprime — Method.

isprobabprime(x::fmpz)

Return true if $x$ is very probably a prime number, otherwise return false. No counterexamples are known to this test, but it is conjectured that infinitely many exist.

Nemo.factor — Method.

factor(a::fmpz)

Return a factorisation of $a$ using a Fac struct (see the documentation on factorisation in Nemo).

Nemo.divisor_lenstra — Method.

divisor_lenstra(n::fmpz, r::fmpz, m::fmpz)

If $n$ has a factor which lies in the residue class $r (\mod m)$ for $0 < r < m < n$, this function returns such a factor. Otherwise it returns $0$. This is only efficient if $m$ is at least the cube root of $n$. We require gcd$(r, m) = 1$ and this condition is not checked.

Nemo.fac — Method.

fac(x::Int)

Return the factorial of $x$, i.e. $x! = 1.2.3\ldots x$. We require $x \geq 0$.

Nemo.risingfac — Method.

risingfac(x::fmpz, y::Int)

Return the rising factorial of $x$, i.e. $x(x + 1)(x + 2)\ldots (x + n - 1)$. If $n < 0$ we throw a DomainError().

Nemo.risingfac — Method.

risingfac(x::Int, y::Int)

Return the rising factorial of $x$, i.e. $x(x + 1)(x + 2)\ldots (x + n - 1)$. If $n < 0$ we throw a DomainError().

Nemo.primorial — Method.

primorial(x::Int)

Return the primorial of $x$, i.e. the product of all primes less than or equal to $x$. If $x < 0$ we throw a DomainError().

Nemo.fib — Method.

fib(x::Int)

Return the $x$-th Fibonacci number $F_x$. We define $F_1 = 1$, $F_2 = 1$ and $F_{i + 1} = F_i + F_{i - 1}$ for all $i > 2$. We require $n \geq 0$. For convenience, we define $F_0 = 0$.

Nemo.bell — Method.

bell(x::Int)

Return the Bell number $B_x$.

Nemo.binom — Method.

binom(n::Int, k::Int)

Return the binomial coefficient $\frac{n!}{(n - k)!k!}$. If $n, k < 0$ or $k > n$ we return $0$.

Nemo.moebiusmu — Method.

moebiusmu(x::fmpz)

Returns the Moebius mu function of $x$ as an Int. The value returned is either $-1$, $0$ or $1$. If $x < 0$ we throw a DomainError().

Nemo.jacobi — Method.

jacobi(x::fmpz, y::fmpz)

Return the value of the Jacobi symbol $\left(\frac{x}{y}\right)$. If $y \leq x$ or $x < 0$, we throw a DomainError().

Nemo.sigma — Method.

sigma(x::fmpz, y::Int)

Return the value of the sigma function, i.e. $\sum_{0 < d \;| x} d^y$. If $y < 0$ we throw a DomainError().

Nemo.eulerphi — Method.

eulerphi(x::fmpz)

Return the value of the Euler phi function at $x$, i.e. the number of positive integers less than $x$ that are coprime with $x$.

Nemo.numpart — Method.

numpart(x::Int)

Return the number of partitions of $x$. This function is not available on Windows 64.

Nemo.numpart — Method.

numpart(x::fmpz)

Return the number of partitions of $x$. This function is not available on Windows 64.

Examples

isprime(ZZ(13))
n = fac(100)
s = sigma(ZZ(128), 10)
a = eulerphi(ZZ(12480))
p = numpart(1000)
f = factor(ZZ(12))

Digits and bases

Base.bin — Method.

bin(n::fmpz)

Return $n$ as a binary string.

Base.oct — Method.

oct(n::fmpz)

Return $n$ as a octal string.

Base.dec — Method.

dec(n::fmpz)

Return $n$ as a decimal string.

Base.hex — Method.

hex(n::fmpz) = base(n, 16)

Return $n$ as a hexadecimal string.

Nemo.base — Method.

base(n::fmpz, b::Integer)

Return $n$ as a string in base $b$. We require $2 \leq b \leq 62$.

Base.ndigits — Method.

ndigits(x::fmpz, b::Integer = 10)

Return the number of digits of $x$ in the base $b$ (default is $b = 10$).

Nemo.nbits — Method.

nbits(x::fmpz)

Return the number of binary bits of $x$. We return zero if $x = 0$.

Examples

a = fmpz(12)

s1 = bin(a)
s2 = base(a, 13)
n1 = nbits(a)
n2 = ndigits(a, 3)

Bit twiddling

Nemo.popcount — Method.

popcount(x::fmpz)

Return the number of ones in the binary representation of $x$.

Nemo.prevpow2 — Method.

prevpow2(x::fmpz)

Return the previous power of $2$ up to including $x$.

Nemo.nextpow2 — Method.

nextpow2(x::fmpz)

Return the next power of $2$ that is at least $x$.

Base.trailing_zeros — Method.

trailing_zeros(x::fmpz)

Count the trailing zeros in the binary representation of $x$.

Nemo.clrbit! — Method.

clrbit!(x::fmpz, c::Int)

Clear bit $c$ of $x$, where the least significant bit is the $0$-th bit. Note that this function modifies its input in-place.

Nemo.setbit! — Method.

setbit!(x::fmpz, c::Int)

Set bit $c$ of $x$, where the least significant bit is the $0$-th bit. Note that this function modifies its input in-place.

Nemo.combit! — Method.

combit!(x::fmpz, c::Int)

Complement bit $c$ of $x$, where the least significant bit is the $0$-th bit. Note that this function modifies its input in-place.

Examples

a = fmpz(12)

p = popcount(a)
b = nextpow2(a)
combit!(a, 2)