Integers

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

For convenience we define

ZZ = ZZ

so that integers can be constructed using ZZ instead of ZZ. 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 providing them.

Library	Element type	Parent type
Flint	`ZZRingElem`	`ZZRing`

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.

A lot of code will want to accept both ZZRingElem integers and Julia integers, that is, subtypes of Base.Integer. Thus for convenience we define

IntegerUnion = Union{Integer,ZZRingElem}

Integer functionality

Nemo integers provide all of the ring and Euclidean ring functionality of AbstractAlgebra.jl.

https://nemocas.github.io/AbstractAlgebra.jl/stable/ring

https://nemocas.github.io/AbstractAlgebra.jl/stable/euclidean_interface

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

sign — Method

sign(a::ZZRingElem)

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

sign(g::Perm)

Return the sign of a permutation.

sign returns $1$ if g is even and $-1$ if g is odd. sign represents the homomorphism from the permutation group to the unit group of $\mathbb{Z}$ whose kernel is the alternating group.

Examples

julia> g = Perm([3,4,1,2,5])
(1,3)(2,4)

julia> sign(g)
1

julia> g = Perm([3,4,5,2,1,6])
(1,3,5)(2,4)

julia> sign(g)
-1

size — Method

size(a::ZZRingElem)

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

fits — Method

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

Return true if $a$ fits into a UInt, otherwise return false.

fits — Method

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

Return true if $a$ fits into an Int, otherwise return false.

denominator — Method

denominator(a::ZZRingElem)

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

numerator — Method

numerator(a::ZZRingElem)

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

Examples

julia> a = ZZ(12)
12

julia> is_unit(a)
false

julia> sign(a)
1

julia> s = size(a)
1

julia> fits(Int, a)
true

julia> n = numerator(a)
12

julia> d = denominator(a)
1

Euclidean division

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 of the quotient
`mod`	r	towards minus infinity
`rem`	r	towards zero
`div`	q	towards minus infinity
`divrem(a::ZZRingElem, b::ZZRingElem)`	q, r	towards minus infinity
`tdivrem(a::ZZRingElem, b::ZZRingElem)`	q, r	towards zero
`fdivrem(a::ZZRingElem, b::ZZRingElem)`	q, r	towards minus infinity
`cdivrem(a::ZZRingElem, b::ZZRingElem)`	q, r	towards plus infinity
`ntdivrem(a::ZZRingElem, b::ZZRingElem)`	q, r	nearest integer, ties toward zero
`nfdivrem(a::ZZRingElem, b::ZZRingElem)`	q, r	nearest integer, ties toward minus infinity
`ncdivrem(a::ZZRingElem, b::ZZRingElem)`	q, r	nearest integer, ties toward plus infinity

N.B: the internal definition of Nemo.div and Nemo.divrem are the same as fdiv and fdivrem. The definitions in the table are of Base.div and Base.divrem which agree with Julia's definitions of div and divrem.

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

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

N.B: the internal definition of Nemo.div is the same as fdiv. The definition in the table is Base.div which agrees with Julia's definition of div.

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::ZZRingElem, d::Int)`	q	towards zero
`fdivpow2(a::ZZRingElem, d::Int)`	q	towards minus infinity
`fmodpow2(a::ZZRingElem, d::Int)`	r	towards minus infinity
`cdivpow2(a::ZZRingElem, d::Int)`	q	towards plus infinity

Examples

julia> a = ZZ(12)
12

julia> b = ZZ(5)
5

julia> q, r = divrem(a, b)
(2, 2)

julia> c = cdiv(a, b)
3

julia> d = fdiv(a, b)
2

julia> f = tdivpow2(a, 2)
3

julia> g = fmodpow2(a, 3)
4

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 non-negative 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::ZZRingElem, b::ZZRingElem)`
`cmpabs(a::ZZRingElem, b::ZZRingElem)`

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

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

Examples

julia> a = ZZ(12)
12

julia> b = ZZ(3)
3

julia> a < b
false

julia> a != b
true

julia> a > 4
true

julia> 5 <= b
false

julia> cmpabs(a, b)
1

Shifting

<< — Method

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

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

>> — Method

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

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

Examples

julia> a = ZZ(12)
12

julia> a << 3
96

julia> a >> 5
0

Modular arithmetic

sqrtmod — Method

sqrtmod(x::ZZRingElem, m::ZZRingElem)

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.

Examples

julia> sqrtmod(ZZ(12), ZZ(13))
5

crt — Function

crt(r1::ZZRingElem, m1::ZZRingElem, r2::ZZRingElem, m2::ZZRingElem, signed=false; check::Bool=true)
crt(r1::ZZRingElem, m1::ZZRingElem, r2::Union{Int, UInt}, m2::Union{Int, UInt}, signed=false; check::Bool=true)
crt(r::Vector{ZZRingElem}, m::Vector{ZZRingElem}, signed=false; check::Bool=true)
crt_with_lcm(r1::ZZRingElem, m1::ZZRingElem, r2::ZZRingElem, m2::ZZRingElem, signed=false; check::Bool=true)
crt_with_lcm(r1::ZZRingElem, m1::ZZRingElem, r2::Union{Int, UInt}, m2::Union{Int, UInt}, signed=false; check::Bool=true)
crt_with_lcm(r::Vector{ZZRingElem}, m::Vector{ZZRingElem}, signed=false; check::Bool=true)

As per the AbstractAlgebra crt interface, with the following option. If signed = true, the solution is the range $(-m/2, m/2]$, otherwise it is in the range $[0,m)$, where $m$ is the least common multiple of the moduli.

Examples

julia> crt(ZZ(5), ZZ(13), ZZ(7), ZZ(37), true)
44

julia> crt(ZZ(5), ZZ(13), 7, 37, true)
44

Integer logarithm

flog — Method

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

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

Examples

julia> flog(ZZ(12), ZZ(2))
3

julia> flog(ZZ(12), 3)
2

clog — Method

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

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

Examples

julia> clog(ZZ(12), ZZ(2))
4

julia> clog(ZZ(12), 3)
3

Integer roots

isqrt — Method

isqrt(x::ZZRingElem)

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

Examples

julia> isqrt(ZZ(13))
3

isqrtrem — Method

isqrtrem(x::ZZRingElem)

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

Examples

julia> isqrtrem(ZZ(13))
(3, 4)

root — Method

root(x::ZZRingElem, n::Int; check::Bool=true)

Return the $n$-the root of $x$. We require $n > 0$ and that $x \geq 0$ if $n$ is even. By default the function tests whether the input was a perfect $n$-th power and if not raises an exception. If check=false this check is omitted.

Examples

julia> root(ZZ(27), 3; check=true)
3

iroot — Method

iroot(x::ZZRingElem, n::Int)

Return the integer truncation of the $n$-the root of $x$ (round towards zero). We require $n > 0$ and that $x \geq 0$ if $n$ is even.

Examples

julia> iroot(ZZ(13), 3)
2

Number theoretic functionality

is_divisible_by — Method

is_divisible_by(x::ZZRingElem, y::ZZRingElem)

Return true if $x$ is divisible by $y$, otherwise return false.

is_divisible_by — Method

is_divisible_by(x::ZZRingElem, y::ZZRingElem)

Return true if $x$ is divisible by $y$, otherwise return false.

is_square — Method

is_square(f::PolyRingElem{T}) where T <: RingElement

Return true if $f$ is a perfect square.

is_square(a::FracElem{T}) where T <: RingElem

Return true if $a$ is a square.

is_prime — Method

is_prime(x::ZZRingElem)
is_prime(x::Int)

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

Examples

julia> is_prime(ZZ(13))
true

is_probable_prime — Method

is_probable_prime(x::ZZRingElem)

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.

factor — Method

factor(a::T) where T <: RingElement -> Fac{T}

Return a factorization of $a$ into irreducible elements, as a Fac{T}. The irreducible elements in the factorization are pairwise coprime.

divisor_lenstra — Method

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

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.

factorial — Method

factorial(x::ZZRingElem)

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

Examples

julia> factorial(ZZ(100))
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

rising_factorial — Method

rising_factorial(x::ZZRingElem, n::ZZRingElem)

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

rising_factorial — Method

rising_factorial(x::ZZRingElem, n::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().

rising_factorial — Method

rising_factorial(x::RingElement, n::Integer)

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

Examples

julia> R, x = ZZ[:x];

julia> rising_factorial(x, 1)
x

julia> rising_factorial(x, 2)
x^2 + x

julia> rising_factorial(4, 2)
20

primorial — Method

primorial(x::ZZRingElem)

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

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

fibonacci — Method

fibonacci(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 integers $i$.

fibonacci — Method

fibonacci(x::ZZRingElem)

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 integers $i$.

bell — Method

bell(x::ZZRingElem)

Return the Bell number $B_x$.

bell — Method

bell(x::Int)

Return the Bell number $B_x$.

binomial — Method

binomial(n::ZZRingElem, k::ZZRingElem)

Return the binomial coefficient $\frac{n (n-1) \cdots (n-k+1)}{k!}$. If $k < 0$ we return $0$, and the identity binomial(n, k) == binomial(n - 1, k - 1) + binomial(n - 1, k) always holds for integers n and k.

binomial — Method

binomial(n::UInt, k::UInt, ::ZZRing)

Return the binomial coefficient $\frac{n!}{(n - k)!k!}$ as an ZZRingElem.

moebius_mu — Method

moebius_mu(x::Int)

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

moebius_mu — Method

moebius_mu(x::ZZRingElem)

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

jacobi_symbol — Method

jacobi_symbol(x::Int, y::Int)

Return the value of the Jacobi symbol $\left(\frac{x}{y}\right)$. The modulus $y$ must be odd and positive, otherwise a DomainError is thrown.

jacobi_symbol — Method

jacobi_symbol(x::ZZRingElem, y::ZZRingElem)

Return the value of the Jacobi symbol $\left(\frac{x}{y}\right)$. The modulus $y$ must be odd and positive, otherwise a DomainError is thrown.

kronecker_symbol — Method

kronecker_symbol(x::ZZRingElem, y::ZZRingElem)
kronecker_symbol(x::Int, y::Int)

Return the value of the Kronecker symbol $\left(\frac{x}{y}\right)$. The definition is as per Henri Cohen's book, "A Course in Computational Algebraic Number Theory", Definition 1.4.8.

divisor_sigma — Method

divisor_sigma(x::ZZRingElem, y::Int)
divisor_sigma(x::ZZRingElem, y::ZZRingElem)
divisor_sigma(x::Int, y::Int)

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

Examples

julia> divisor_sigma(ZZ(32), 10)
1127000493261825

julia> divisor_sigma(ZZ(32), ZZ(10))
1127000493261825

julia> divisor_sigma(32, 10)
1127000493261825

euler_phi — Method

euler_phi(x::ZZRingElem)
euler_phi(x::Int)

Return the value of the Euler phi function at $x$, i.e. the number of positive integers up to $x$ (inclusive) that are coprime with $x$. An exception is raised if $x \leq 0$.

Examples

julia> euler_phi(ZZ(12480))
3072

julia> euler_phi(12480)
3072

number_of_partitions — Method

number_of_partitions(x::Int)
number_of_partitions(x::ZZRingElem)

Return the number of partitions of $x$.

Examples

julia> number_of_partitions(100)
190569292

julia> number_of_partitions(ZZ(1000))
24061467864032622473692149727991

is_perfect_power — Method

is_perfect_power(a::IntegerUnion)

Return whether $a$ is a perfect power, that is, whether $a = m^r$ for some integer $m$ and $r > 1$.

is_prime_power — Method

is_prime_power(q::IntegerUnion) -> Bool

Returns whether $q$ is a prime power.

is_prime_power_with_data — Method

is_prime_power_with_data(q::IntegerUnion) -> Bool, ZZRingElem, Int

Returns a flag indicating whether $q$ is a prime power and integers $e, p$ such that $q = p^e$. If $q$ is a prime power, than $p$ is a prime.

Digits and bases

bin — Method

bin(n::ZZRingElem)

Return $n$ as a binary string.

Examples

julia> bin(ZZ(12))
"1100"

oct — Method

oct(n::ZZRingElem)

Return $n$ as a octal string.

Examples

julia> oct(ZZ(12))
"14"

dec — Method

dec(n::ZZRingElem)

Return $n$ as a decimal string.

Examples

julia> dec(ZZ(12))
"12"

hex — Method

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

Return $n$ as a hexadecimal string.

Examples

julia> hex(ZZ(12))
"c"

base — Method

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

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

Examples

julia> base(ZZ(12), 13)
"c"

number_of_digits — Method

number_of_digits(x::ZZRingElem, b::Integer)

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

Examples

julia> number_of_digits(ZZ(12), 3)
3

nbits — Method

nbits(x::ZZRingElem)

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

Examples

julia> nbits(ZZ(12))
4

Bit twiddling

popcount — Method

popcount(x::ZZRingElem)

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

Examples

julia> popcount(ZZ(12))
2

prevpow2 — Method

prevpow2(x::ZZRingElem)

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

nextpow2 — Method

nextpow2(x::ZZRingElem)

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

Examples

julia> nextpow2(ZZ(12))
16

trailing_zeros — Method

trailing_zeros(x::ZZRingElem)

Return the number of trailing zeros in the binary representation of $x$.

clrbit! — Method

clrbit!(x::ZZRingElem, 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.

Examples

julia> a = ZZ(12)
12

julia> clrbit!(a, 3)

julia> a
4

setbit! — Method

setbit!(x::ZZRingElem, 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.

Examples

julia> a = ZZ(12)
12

julia> setbit!(a, 0)

julia> a
13

combit! — Method

combit!(x::ZZRingElem, 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

julia> a = ZZ(12)
12

julia> combit!(a, 2)

julia> a
8

tstbit — Method

tstbit(x::ZZRingElem, c::Int)

Return bit $i$ of x (numbered from 0) as true for 1 or false for 0.

Examples

julia> a = ZZ(12)
12

julia> tstbit(a, 0)
false

julia> tstbit(a, 2)
true

Random generation

rand_bits — Method

rand_bits(::ZZRing, b::Int)

Return a random signed integer whose absolute value has $b$ bits.

rand_bits_prime — Method

rand_bits_prime(::ZZRing, n::Int, proved::Bool=true)

Return a random prime number with the given number of bits. If only a probable prime is required, one can pass proved=false.

Examples

a = rand_bits(ZZ, 23)
b = rand_bits_prime(ZZ, 7)

Complex Integers

The Gaussian integer type in Nemo is provided by a pair of Flint integers. The associated ring of integers and the fraction field can be retrieved by Nemo.GaussianIntegers() and Nemo.GaussianRationals().

Examples

julia> ZZi = Nemo.GaussianIntegers()
Gaussian integer ring

julia> a = ZZ(5)*im
5*im

julia> b = ZZi(3, 4)
3 + 4*im

julia> is_unit(a)
false

julia> factor(a)
im * (2 - im) * (2 + im)

julia> a//b
4//5 + 3//5*im

julia> abs2(a//b)
1