## Introduction

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 asociated 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 element constructors

There are various ways to construct integers given an integer ring parent object such as `ZZ`

. As usual, one can coerce various elements into the ring of integers using the parent object. Here are some examples.

```
ZZ(123)
ZZ("123")
ZZ(123.0)
```

Note that when coercing from floating point numbers of various kinds, the input must be exactly an integer without fractional part.

Apart from coercing elements into the ring of integers, we offer the following functions.

#
** Base.zero** —

*Method*.

```
zero(R::FlintIntegerRing)
```

Return the integer .

#
** Base.one** —

*Method*.

```
one(R::FlintIntegerRing)
```

Return the integer .

Here are some examples of constructing integers.

```
a = ZZ(123)
b = one(ZZ)
c = zero(ZZ)
```

## Basic functionality

The following basic functionality is provided by the default integer implementation in Nemo, to support construction of generic rings over the integers. Any custom integer implementation in Nemo should provide these functions along with the usual arithmetic operations and greatest common divisor.

```
parent_type(::Type{fmpz})
```

Gives the type of the parent object of a Flint integer.

```
elem_type(R::FlintIntegerRing)
```

Given the parent object for the integer ring, return the type of elements of the integer ring.

```
Base.hash(a::fmpz, h::UInt)
```

Return a `UInt`

hexadecimal hash of the integer . This should be xor'd with a fixed random hexadecimal specific to the integer type. The hash of the machine words used to store the integer should be xor'd with the supplied parameter `h`

as part of computing the hash.

```
deepcopy(a::fmpz)
```

Construct a copy of the given integer and return it. This function must recursively construct copies of all of the internal data in the given integer. Nemo integers are mutable and so returning shallow copies is not sufficient.

```
mul!(c::fmpz, a::fmpz, b::fmpz)
```

Multiply by and set the existing integer to the result. This function is provided for performance reasons as it saves allocating a new object for the result and eliminates associated garbage collection.

```
addeq!(c::fmpz, a::fmpz)
```

In-place addition. Adds to and sets to the result. This function is provided for performance reasons as it saves allocating a new object for the result and eliminates associated garbage collection.

Given the parent object `ZZ`

for the integer ring, the following coercion functions are provided to coerce various elements into the integer ring. Developers provide these by overloading the `call`

operator for the integer ring parent objects.

```
ZZ()
```

Coerce zero into the integer ring.

```
ZZ(n::Integer)
```

Coerce an 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.

```
ZZ(f::fmpz)
```

Take an integer that is already in the Flint integer ring and simply return it. A copy of the original is not made.

In addition to the above, developers of custom integer types must ensure that they provide the equivalent of the function `base_ring(R::FlintIntegerRing)`

which should return `Union{}`

. In addition to this they should ensure that each integer element contains a field `parent`

specifying the parent object of the integer, or at least supply the equivalent of the function `parent(a::fmpz)`

to return the parent object of an integer.

## Basic manipulation

Numerous functions are provided to manipulate integers. Also see the section on basic functionality above.

#
** Nemo.base_ring** —

*Method*.

```
base_ring(a::FlintIntegerRing)
```

Returns

`Union{}`

as this ring is not dependent on another ring.

#
** Nemo.base_ring** —

*Method*.

```
base_ring(a::fmpz)
```

Returns

`Union{}`

as the parent ring is not dependent on another ring.

#
** Base.parent** —

*Method*.

```
parent(a::fmpz)
```

Returns the unique Flint integer parent object

`FlintZZ`

.

#
** Nemo.iszero** —

*Method*.

```
iszero(a::fmpz)
```

Return

`true`

if the given integer is zero, otherwise return`false`

.

#
** Nemo.isone** —

*Method*.

```
isone(a::fmpz)
```

Return

`true`

if the given integer is one, otherwise return`false`

.

#
** Nemo.isunit** —

*Method*.

```
isunit(a::fmpz)
```

Return

`true`

if the given integer is a unit, i.e. , otherwise return`false`

.

#
** Base.sign** —

*Method*.

```
sign(a::fmpz)
```

Returns the sign of , i.e. , or .

#
** Base.size** —

*Method*.

```
size(a::fmpz)
```

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

#
** 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.den** —

*Method*.

```
den(a::fmpz)
```

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

#
** Base.num** —

*Method*.

```
num(a::fmpz)
```

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

Here are some examples of basic manipulation of integers.

```
a = ZZ(12)
R = base_ring(ZZ)
S = base_ring(a)
T = parent(a)
iszero(a)
isone(a)
isunit(a)
sign(a)
s = size(a)
fits(Int, a)
n = num(a)
d = den(a)
```

## Arithmetic operations

Nemo provides all the standard ring operations for integers, as follows.

Function | Operation |
---|---|

-(a::fmpz) | unary minus |

+(a::fmpz, b::fmpz) | addition |

-(a::fmpz, b::fmpz) | subtraction |

*(a::fmpz, b::fmpz) | multiplication |

divexact(a::fmpz, b::fmpz) | exact division |

In addition, the following ad hoc ring operations are defined.

Function | Operation |
---|---|

+(a::fmpz, b::Integer) | addition |

+(a::Integer, b::fmpz) | addition |

-(a::fmpz, b::Integer) | subtraction |

-(a::Integer, b::fmpz) | subtraction |

*(a::fmpz, b::Integer) | multiplication |

*(a::Integer, b::fmpz) | multiplication |

divexact(a::fmpz, b::Integer) | exact division |

divexact(a::Integer, b::fmpz) | exact division |

^(a::fmpz, b::Int) | powering |

Here are some examples of arithmetic operations on integers.

```
a = fmpz(12)
b = fmpz(3)
c = a + b
d = divexact(a, b)
f = 3a
g = a*ZZ(7)
h = 3 - a
k = divexact(a, 4)
m = a^7
```

## Euclidean division

Nemo also provides a large number of Euclidean division operations. Recall that for a dividend and divisor , we can write with . We call the quotient and the remainder.

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

In the following table we list the division functions and their rounding behaviour. We also give the return value of the function, with representing return of the quotient and 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 . In other words, for Euclidean division of the form . 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 |

Here are some examples of Euclidean division.

```
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

Nemo provides a full complement of comparison operators for integers. This includes the usual operators. These are usually provided via Julia once Nemo provides the `isless`

function and the `==`

function. However, to avoid two calls to Flint for such comparisons we implement them differently.

Instead of `isless`

we implement a function `cmp(a, b)`

which returns a positive value if , zero if and a negative value if . 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 , zero if and a negative value if . 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)

Here are some examples of comparisons.

```
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 where .

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

Return , discarding any remainder, where .

Here are some examples of shifting.

```
a = fmpz(12)
a << 3
a >> 5
```

## Modular arithmetic

#
** Base.mod** —

*Method*.

```
mod(x::fmpz, y::fmpz)
```

Return the remainder after division of by . The remainder will be the least nonnegative remainder.

#
** Base.mod** —

*Method*.

```
mod(x::fmpz, y::Int)
```

Return the remainder after division of by . The remainder will be the least nonnegative remainder.

#
** Nemo.powmod** —

*Method*.

```
powmod(x::fmpz, p::fmpz, m::fmpz)
```

Return . The remainder will be in the range

#
** Nemo.powmod** —

*Method*.

```
powmod(x::fmpz, p::Int, m::fmpz)
```

Return . The remainder will be in the range

#
** Base.invmod** —

*Method*.

```
invmod(x::fmpz, m::fmpz)
```

Return . The remainder will be in the range

#
** Nemo.sqrtmod** —

*Method*.

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

Return a square root of if one exists. The remainder will be in the range . We require that is prime, otherwise the algorithm may not terminate.

#
** Nemo.crt** —

*Method*.

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

Find such that and . If

`signed = true`

, will be in the range . If`signed = false`

the value will be in the range .

#
** Nemo.crt** —

*Method*.

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

Find such that and . If

`signed = true`

, will be in the range . If`signed = false`

the value will be in the range .

Here are some examples of modular arithmetic.

```
a = powmod(ZZ(12), ZZ(110), ZZ(13))
a = powmod(ZZ(12), 110, ZZ(13))
b = invmod(ZZ(12), ZZ(13))
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 to base .

#
** Nemo.flog** —

*Method*.

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

Return the floor of the logarithm of to base .

#
** Nemo.clog** —

*Method*.

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

Return the ceiling of the logarithm of to base .

#
** Nemo.clog** —

*Method*.

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

Return the ceiling of the logarithm of to base .

Here are some examples of computing integer logarithms.

```
a = fmpz(12)
b = fmpz(2)
c = flog(a, b)
d = clog(a, 3)
```

## GCD and LCM

#
** Base.gcd** —

*Method*.

```
gcd(x::fmpz, y::fmpz)
```

Return the greatest common divisor of and . The returned result will always be nonnegative and will be zero iff and are zero.

#
** Base.gcd** —

*Method*.

```
gcd(x::Array{fmpz, 1})
```

Return the greatest common divisor of the elements of . The returned result will always be nonnegative and will be zero iff all elements of are zero.

#
** Base.lcm** —

*Method*.

```
lcm(x::fmpz, y::fmpz)
```

Return the least common multiple of and . The returned result will always be nonnegative and will be zero iff and are zero.

#
** Base.lcm** —

*Method*.

```
lcm(x::Array{fmpz, 1})
```

Return the least common multiple of the elements of . The returned result will always be nonnegative and will be zero iff the elements of are zero.

#
** Base.gcdx** —

*Method*.

```
gcdx(a::fmpz, b::fmpz)
```

Return a tuple such that is the greatest common divisor of and and integers and such that .

#
** Nemo.gcdinv** —

*Method*.

```
gcdinv(a::fmpz, b::fmpz)
```

Return a tuple where is the greatest common divisor of and and where is the inverse of modulo if . This function can be used to detect impossible inverses, i.e. where and are not coprime, and to yield the common factor of and if they are not coprime. We require .

Here are some examples of GCD and LCM.

```
a = ZZ(3)
b = ZZ(12)
c = gcd(a, b)
d = lcm(a, b)
g, s, t = gcdx(a, b)
g, s = gcdinv(a, b)
```

## Integer roots

#
** Base.isqrt** —

*Method*.

```
isqrt(x::fmpz)
```

Return the floor of the square root of .

#
** Nemo.isqrtrem** —

*Method*.

```
isqrtrem(x::fmpz)
```

Return a tuple consisting of the floor of the square root of and the remainder , i.e. such that . We require .

#
** Nemo.root** —

*Method*.

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

Return the floor of the -the root of . We require and that if is even.

Here are some examples of integer roots.

```
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 is divisible by , otherwise return`false`

. We require .

#
** Nemo.divisible** —

*Method*.

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

Return

`true`

if is divisible by , otherwise return`false`

. We require .

#
** Nemo.issquare** —

*Method*.

```
issquare(x::fmpz)
```

Return

`true`

if is a square, otherwise return`false`

.

```
isprime(::UInt)
isprime(::fmpz)
```

#
** Nemo.isprobabprime** —

*Method*.

```
isprobabprime(x::fmpz)
```

Return

`true`

if is a very probably a prime number, otherwise return`false`

. No counterexamples are known to this test, but it is conjectured that infinitely many exist.

```
factor(::fmpz)
```

```
remove(::fmpz, y:fmpz)
```

#
** Nemo.divisor_lenstra** —

*Method*.

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

If has a factor which lies in the residue class for , this function returns such a factor. Otherwise it returns . This is only efficient if is at least the cube root of . We require gcd and this condition is not checked.

#
** Nemo.fac** —

*Method*.

```
fac(x::Int)
```

Return the factorial of , i.e. . We require .

#
** Nemo.risingfac** —

*Method*.

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

Return the rising factorial of , i.e. . If we throw a

`DomainError()`

.

#
** Nemo.risingfac** —

*Method*.

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

Return the rising factorial of , i.e. . If we throw a

`DomainError()`

.

#
** Nemo.primorial** —

*Method*.

```
primorial(x::Int)
```

Return the primorial of , i.e. the product of all primes less than or equal to . If we throw a

`DomainError()`

.

#
** Nemo.fib** —

*Method*.

```
fib(x::Int)
```

Return the -th Fibonacci number . We define , and for all . We require . For convenience, we define .

#
** Nemo.bell** —

*Method*.

```
bell(x::Int)
```

Return the Bell number .

#
** Nemo.binom** —

*Method*.

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

Return the binomial coefficient . If or we return .

#
** Nemo.moebiusmu** —

*Method*.

```
moebiusmu(x::fmpz)
```

Returns the Moebius mu function of as an \code{Int}. The value returned is either , or . If we throw a

`DomainError()`

.

#
** Nemo.jacobi** —

*Method*.

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

Return the value of the Jacobi symbol . If or , we throw a

`DomainError()`

.

#
** Nemo.sigma** —

*Method*.

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

Return the value of the sigma function, i.e. . If we throw a

`DomainError()`

.

#
** Nemo.eulerphi** —

*Method*.

```
eulerphi(x::fmpz)
```

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

#
** Nemo.numpart** —

*Method*.

```
numpart(x::Int)
```

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

#
** Nemo.numpart** —

*Method*.

```
numpart(x::fmpz)
```

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

Here are some examples of number theoretic functionality.

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

## Number digits and bases

#
** Base.bin** —

*Method*.

```
bin(n::fmpz)
```

Return as a binary string.

#
** Base.oct** —

*Method*.

```
oct(n::fmpz)
```

Return as a octal string.

#
** Base.dec** —

*Method*.

```
dec(n::fmpz)
```

Return as a decimal string.

#
** Base.hex** —

*Method*.

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

Return as a hexadecimal string.

#
** Base.base** —

*Method*.

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

Return as a string in base . We require .

#
** Base.ndigits** —

*Method*.

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

Return the number of digits of in the base (default is ).

#
** Nemo.nbits** —

*Method*.

```
nbits(x::fmpz)
```

Return the number of binary bits of . We return zero if .

Here are some examples of writing numbers in various bases.

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

#
** Base.prevpow2** —

*Method*.

```
prevpow2(x::fmpz)
```

Return the previous power of up to including .

#
** Base.nextpow2** —

*Method*.

```
nextpow2(x::fmpz)
```

Return the next power of that is at least .

#
** Base.trailing_zeros** —

*Method*.

```
trailing_zeros(x::fmpz)
```

Count the trailing zeros in the binary representation of .

#
** Nemo.clrbit!** —

*Method*.

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

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

#
** Nemo.setbit!** —

*Method*.

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

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

#
** Nemo.combit!** —

*Method*.

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

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

Here are some examples of bit twiddling.

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