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
Base.sign
— Methodsign(a::ZZRingElem)
Return the sign of $a$, i.e. $+1$, $0$ or $-1$.
Base.size
— Methodsize(a::ZZRingElem)
Return the number of limbs required to store the absolute value of $a$.
Nemo.fits
— Methodfits(::Type{UInt}, a::ZZRingElem)
Return true
if $a$ fits into a UInt
, otherwise return false
.
Nemo.fits
— Methodfits(::Type{Int}, a::ZZRingElem)
Return true
if $a$ fits into an Int
, otherwise return false
.
Base.denominator
— Methoddenominator(a::ZZRingElem)
Return the denominator of $a$ thought of as a rational. Always returns $1$.
Base.numerator
— Methodnumerator(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
Base.:<<
— Method<<(x::ZZRingElem, c::Int)
Return $2^cx$ where $c \geq 0$.
Base.:>>
— 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
Nemo.sqrtmod
— Methodsqrtmod(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
AbstractAlgebra.crt
— Functioncrt(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
Nemo.flog
— Methodflog(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
Nemo.clog
— Methodclog(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
Base.isqrt
— Methodisqrt(x::ZZRingElem)
Return the floor of the square root of $x$.
Examples
julia> isqrt(ZZ(13))
3
Nemo.isqrtrem
— Methodisqrtrem(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)
AbstractAlgebra.root
— Methodroot(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
AbstractAlgebra.iroot
— Methodiroot(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
AbstractAlgebra.is_divisible_by
— Methodis_divisible_by(x::ZZRingElem, y::ZZRingElem)
Return true
if $x$ is divisible by $y$, otherwise return false
.
AbstractAlgebra.is_divisible_by
— Methodis_divisible_by(x::ZZRingElem, y::ZZRingElem)
Return true
if $x$ is divisible by $y$, otherwise return false
.
AbstractAlgebra.is_square
— Methodis_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.
Nemo.is_prime
— Methodis_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
AbstractAlgebra.is_probable_prime
— Methodis_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.
AbstractAlgebra.factor
— Methodfactor(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.
Nemo.divisor_lenstra
— Methoddivisor_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.
Base.factorial
— Methodfactorial(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
AbstractAlgebra.Generic.rising_factorial
— Methodrising_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()
.
AbstractAlgebra.Generic.rising_factorial
— Methodrising_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()
.
AbstractAlgebra.Generic.rising_factorial
— Methodrising_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
Nemo.primorial
— Methodprimorial(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()
.
Nemo.primorial
— Methodprimorial(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.fibonacci
— Methodfibonacci(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$.
Nemo.fibonacci
— Methodfibonacci(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$.
Nemo.bell
— Methodbell(x::ZZRingElem)
Return the Bell number $B_x$.
Nemo.bell
— Methodbell(x::Int)
Return the Bell number $B_x$.
Base.binomial
— Methodbinomial(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
.
Base.binomial
— Methodbinomial(n::UInt, k::UInt, ::ZZRing)
Return the binomial coefficient $\frac{n!}{(n - k)!k!}$ as an ZZRingElem
.
Nemo.moebius_mu
— Methodmoebius_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()
.
Nemo.moebius_mu
— Methodmoebius_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()
.
Nemo.jacobi_symbol
— Methodjacobi_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.
Nemo.jacobi_symbol
— Methodjacobi_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.
Nemo.kronecker_symbol
— Methodkronecker_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.
Nemo.divisor_sigma
— Methoddivisor_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
Nemo.euler_phi
— Methodeuler_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
Nemo.number_of_partitions
— Methodnumber_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
Nemo.is_perfect_power
— Methodis_perfect_power(a::IntegerUnion)
Return whether $a$ is a perfect power, that is, whether $a = m^r$ for some integer $m$ and $r > 1$.
Nemo.is_prime_power
— Methodis_prime_power(q::IntegerUnion) -> Bool
Returns whether $q$ is a prime power.
Nemo.is_prime_power_with_data
— Methodis_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
Base.bin
— Methodbin(n::ZZRingElem)
Return $n$ as a binary string.
Examples
julia> bin(ZZ(12))
"1100"
Base.oct
— Methodoct(n::ZZRingElem)
Return $n$ as a octal string.
Examples
julia> oct(ZZ(12))
"14"
Base.dec
— Methoddec(n::ZZRingElem)
Return $n$ as a decimal string.
Examples
julia> dec(ZZ(12))
"12"
Base.hex
— Methodhex(n::ZZRingElem) = base(n, 16)
Return $n$ as a hexadecimal string.
Examples
julia> hex(ZZ(12))
"c"
Nemo.base
— Methodbase(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"
AbstractAlgebra.number_of_digits
— Methodnumber_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
Nemo.nbits
— Methodnbits(x::ZZRingElem)
Return the number of binary bits of $x$. We return zero if $x = 0$.
Examples
julia> nbits(ZZ(12))
4
Bit twiddling
Nemo.popcount
— Methodpopcount(x::ZZRingElem)
Return the number of ones in the binary representation of $x$.
Examples
julia> popcount(ZZ(12))
2
Nemo.prevpow2
— Methodprevpow2(x::ZZRingElem)
Return the previous power of $2$ up to including $x$.
Nemo.nextpow2
— Methodnextpow2(x::ZZRingElem)
Return the next power of $2$ that is at least $x$.
Examples
julia> nextpow2(ZZ(12))
16
Base.trailing_zeros
— Methodtrailing_zeros(x::ZZRingElem)
Return the number of trailing zeros in the binary representation of $x$.
Nemo.clrbit!
— Methodclrbit!(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
Nemo.setbit!
— Methodsetbit!(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
Nemo.combit!
— Methodcombit!(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
Nemo.tstbit
— Methodtstbit(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
Nemo.rand_bits
— Methodrand_bits(::ZZRing, b::Int)
Return a random signed integer whose absolute value has $b$ bits.
Nemo.rand_bits_prime
— Methodrand_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