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.

LibraryElement typeParent type
FlintZZRingElemZZRing

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

Base.signMethod
sign(a::ZZRingElem)

Return the sign of aa, i.e. +1+1, 00 or 1-1.

source
sign(g::Perm)

Return the sign of a permutation.

sign returns 11 if g is even and 1-1 if g is odd. sign represents the homomorphism from the permutation group to the unit group of Z\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
source
Base.sizeMethod
size(a::ZZRingElem)

Return the number of limbs required to store the absolute value of aa.

source
Nemo.fitsMethod
fits(::Type{UInt}, a::ZZRingElem)

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

source
Nemo.fitsMethod
fits(::Type{Int}, a::ZZRingElem)

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

source
Base.denominatorMethod
denominator(a::ZZRingElem)

Return the denominator of aa thought of as a rational. Always returns 11.

source
Base.numeratorMethod
numerator(a::ZZRingElem)

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

source

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 aa and divisor bb, we can write a=bq+ra = bq + r with 0r<b0 \leq |r| < |b|. We call qq the quotient and rr the remainder.

We distinguish three cases. If qq is rounded towards zero, rr will have the same sign as aa. If qq is rounded towards plus infinity, rr will have the opposite sign to bb. Finally, if qq is rounded towards minus infinity, rr will have the same sign as bb.

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

FunctionReturnRounding of the quotient
modrtowards minus infinity
remrtowards zero
divqtowards minus infinity
divrem(a::ZZRingElem, b::ZZRingElem)q, rtowards minus infinity
tdivrem(a::ZZRingElem, b::ZZRingElem)q, rtowards zero
fdivrem(a::ZZRingElem, b::ZZRingElem)q, rtowards minus infinity
cdivrem(a::ZZRingElem, b::ZZRingElem)q, rtowards plus infinity
ntdivrem(a::ZZRingElem, b::ZZRingElem)q, rnearest integer, ties toward zero
nfdivrem(a::ZZRingElem, b::ZZRingElem)q, rnearest integer, ties toward minus infinity
ncdivrem(a::ZZRingElem, b::ZZRingElem)q, rnearest 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.

FunctionReturnRounding
mod(a::ZZRingElem, b::Int)rtowards minus infinity
rem(a::ZZRingElem, b::Int)rtowards zero
div(a::ZZRingElem, b::Int)qtowards zero
tdiv(a::ZZRingElem, b::Int)qtowards zero
fdiv(a::ZZRingElem, b::Int)qtowards minus infinity
cdiv(a::ZZRingElem, b::Int)qtowards 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 22. In other words, for Euclidean division of the form a=b2d+ra = b2^{d} + r. These are useful for bit twiddling.

FunctionReturnRounding
tdivpow2(a::ZZRingElem, d::Int)qtowards zero
fdivpow2(a::ZZRingElem, d::Int)qtowards minus infinity
fmodpow2(a::ZZRingElem, d::Int)rtowards minus infinity
cdivpow2(a::ZZRingElem, d::Int)qtowards 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>ba > b, zero if a==ba == b and a negative value if a<ba < 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|a| > |b|, zero if a==b|a| == |b| and a negative value if a<b|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

Base.:<<Method
<<(x::ZZRingElem, c::Int)

Return 2cx2^cx where c0c \geq 0.

source
Base.:>>Method
>>(x::ZZRingElem, c::Int)

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

source

Examples

julia> a = ZZ(12)
12

julia> a << 3
96

julia> a >> 5
0

Modular arithmetic

Nemo.sqrtmodMethod
sqrtmod(x::ZZRingElem, m::ZZRingElem)

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

Examples

julia> sqrtmod(ZZ(12), ZZ(13))
5
source
AbstractAlgebra.crtFunction
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](-m/2, m/2], otherwise it is in the range [0,m)[0,m), where mm 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
source

Integer logarithm

Nemo.flogMethod
flog(x::ZZRingElem, c::ZZRingElem)
flog(x::ZZRingElem, c::Int)

Return the floor of the logarithm of xx to base cc.

Examples

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

julia> flog(ZZ(12), 3)
2
source
Nemo.clogMethod
clog(x::ZZRingElem, c::ZZRingElem)
clog(x::ZZRingElem, c::Int)

Return the ceiling of the logarithm of xx to base cc.

Examples

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

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

Integer roots

Base.isqrtMethod
isqrt(x::ZZRingElem)

Return the floor of the square root of xx.

Examples

julia> isqrt(ZZ(13))
3
source
Nemo.isqrtremMethod
isqrtrem(x::ZZRingElem)

Return a tuple s,rs, r consisting of the floor ss of the square root of xx and the remainder rr, i.e. such that x=s2+rx = s^2 + r. We require x0x \geq 0.

Examples

julia> isqrtrem(ZZ(13))
(3, 4)
source
AbstractAlgebra.rootMethod
root(x::ZZRingElem, n::Int; check::Bool=true)

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

Examples

julia> root(ZZ(27), 3; check=true)
3
source
AbstractAlgebra.irootMethod
iroot(x::ZZRingElem, n::Int)

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

Examples

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

Number theoretic functionality

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

Return true if ff is a perfect square.

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

Return true if aa is a square.

source
Nemo.is_primeMethod
is_prime(x::ZZRingElem)
is_prime(x::Int)

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

Examples

julia> is_prime(ZZ(13))
true
source
AbstractAlgebra.is_probable_primeMethod
is_probable_prime(x::ZZRingElem)

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

source
AbstractAlgebra.factorMethod
factor(a::T) where T <: RingElement -> Fac{T}

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

source
Nemo.divisor_lenstraMethod
divisor_lenstra(n::ZZRingElem, r::ZZRingElem, m::ZZRingElem)

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

source
Base.factorialMethod
factorial(x::ZZRingElem)

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

Examples

julia> factorial(ZZ(100))
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
source
AbstractAlgebra.Generic.rising_factorialMethod
rising_factorial(x::ZZRingElem, n::ZZRingElem)

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

source
AbstractAlgebra.Generic.rising_factorialMethod
rising_factorial(x::ZZRingElem, n::Int)

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

source
AbstractAlgebra.Generic.rising_factorialMethod
rising_factorial(x::RingElement, n::Integer)

Return the rising factorial of xx, i.e. x(x+1)(x+2)(x+n1)x(x + 1)(x + 2)\cdots (x + n - 1). If n<0n < 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
source
Nemo.primorialMethod
primorial(x::ZZRingElem)

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

source
Nemo.primorialMethod
primorial(x::Int)

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

source
Nemo.fibonacciMethod
fibonacci(x::Int)

Return the xx-th Fibonacci number FxF_x. We define F1=1F_1 = 1, F2=1F_2 = 1 and Fi+1=Fi+Fi1F_{i + 1} = F_i + F_{i - 1} for all integers ii.

source
Nemo.fibonacciMethod
fibonacci(x::ZZRingElem)

Return the xx-th Fibonacci number FxF_x. We define F1=1F_1 = 1, F2=1F_2 = 1 and Fi+1=Fi+Fi1F_{i + 1} = F_i + F_{i - 1} for all integers ii.

source
Nemo.bellMethod
bell(x::ZZRingElem)

Return the Bell number BxB_x.

source
Base.binomialMethod
binomial(n::ZZRingElem, k::ZZRingElem)

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

source
Base.binomialMethod
binomial(n::UInt, k::UInt, ::ZZRing)

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

source
Nemo.moebius_muMethod
moebius_mu(x::Int)

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

source
Nemo.moebius_muMethod
moebius_mu(x::ZZRingElem)

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

source
Nemo.jacobi_symbolMethod
jacobi_symbol(x::Int, y::Int)

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

source
Nemo.jacobi_symbolMethod
jacobi_symbol(x::ZZRingElem, y::ZZRingElem)

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

source
Nemo.kronecker_symbolMethod
kronecker_symbol(x::ZZRingElem, y::ZZRingElem)
kronecker_symbol(x::Int, y::Int)

Return the value of the Kronecker symbol (xy)\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.

source
Nemo.divisor_sigmaMethod
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. 0<d  xdy\sum_{0 < d \;| x} d^y. If x0x \leq 0 or y<0y < 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
source
Nemo.euler_phiMethod
euler_phi(x::ZZRingElem)
euler_phi(x::Int)

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

Examples

julia> euler_phi(ZZ(12480))
3072

julia> euler_phi(12480)
3072
source
Nemo.number_of_partitionsMethod
number_of_partitions(x::Int)
number_of_partitions(x::ZZRingElem)

Return the number of partitions of xx.

Examples

julia> number_of_partitions(100)
190569292

julia> number_of_partitions(ZZ(1000))
24061467864032622473692149727991
source
Nemo.is_perfect_powerMethod
is_perfect_power(a::IntegerUnion)

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

source
Nemo.is_prime_power_with_dataMethod
is_prime_power_with_data(q::IntegerUnion) -> Bool, ZZRingElem, Int

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

source

Digits and bases

Base.binMethod
bin(n::ZZRingElem)

Return nn as a binary string.

Examples

julia> bin(ZZ(12))
"1100"
source
Base.octMethod
oct(n::ZZRingElem)

Return nn as a octal string.

Examples

julia> oct(ZZ(12))
"14"
source
Base.decMethod
dec(n::ZZRingElem)

Return nn as a decimal string.

Examples

julia> dec(ZZ(12))
"12"
source
Base.hexMethod
hex(n::ZZRingElem) = base(n, 16)

Return nn as a hexadecimal string.

Examples

julia> hex(ZZ(12))
"c"
source
Nemo.baseMethod
base(n::ZZRingElem, b::Integer)

Return nn as a string in base bb. We require 2b622 \leq b \leq 62.

Examples

julia> base(ZZ(12), 13)
"c"
source
AbstractAlgebra.number_of_digitsMethod
number_of_digits(x::ZZRingElem, b::Integer)

Return the number of digits of xx in the base bb (default is b=10b = 10).

Examples

julia> number_of_digits(ZZ(12), 3)
3
source
Nemo.nbitsMethod
nbits(x::ZZRingElem)

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

Examples

julia> nbits(ZZ(12))
4
source

Bit twiddling

Nemo.popcountMethod
popcount(x::ZZRingElem)

Return the number of ones in the binary representation of xx.

Examples

julia> popcount(ZZ(12))
2
source
Nemo.prevpow2Method
prevpow2(x::ZZRingElem)

Return the previous power of 22 up to including xx.

source
Nemo.nextpow2Method
nextpow2(x::ZZRingElem)

Return the next power of 22 that is at least xx.

Examples

julia> nextpow2(ZZ(12))
16
source
Base.trailing_zerosMethod
trailing_zeros(x::ZZRingElem)

Return the number of trailing zeros in the binary representation of xx.

source
Nemo.clrbit!Method
clrbit!(x::ZZRingElem, c::Int)

Clear bit cc of xx, where the least significant bit is the 00-th bit. Note that this function modifies its input in-place.

Examples

julia> a = ZZ(12)
12

julia> clrbit!(a, 3)

julia> a
4
source
Nemo.setbit!Method
setbit!(x::ZZRingElem, c::Int)

Set bit cc of xx, where the least significant bit is the 00-th bit. Note that this function modifies its input in-place.

Examples

julia> a = ZZ(12)
12

julia> setbit!(a, 0)

julia> a
13
source
Nemo.combit!Method
combit!(x::ZZRingElem, c::Int)

Complement bit cc of xx, where the least significant bit is the 00-th bit. Note that this function modifies its input in-place.

Examples

julia> a = ZZ(12)
12

julia> combit!(a, 2)

julia> a
8
source
Nemo.tstbitMethod
tstbit(x::ZZRingElem, c::Int)

Return bit ii 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
source

Random generation

Nemo.rand_bitsMethod
rand_bits(::ZZRing, b::Int)

Return a random signed integer whose absolute value has bb bits.

source
Nemo.rand_bits_primeMethod
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.

source

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