API reference

bitsizeof(::Type{T}) where T
bitsizeof(x)

Size, in bits, of the canonical binary representation of the given type T. Size, in bits, of object x if it is not a type.

log_bitsizeof(::Type{T}) where T
log_bitsizeof(x)

log2() of the value returned by bitsizeof for that argument.

num_bits(x)

Returns the number of bits in the representation of the absolute value of an integer.

encompassing_type(tp::Type{<:Unsigned})

Returns the built-in type that covers all the range of tp (not necessarily unsigned).

as_builtin(x)

Returns the integer x converted to a builtin type with the minimum suitable size.

addhilo(x_hi::T, x_lo::T, y::T) where T <: Unsigned

Calculates hi * B + lo = x_hi * B + x_lo + y, where B == typemax(T) + 1. Returns the result as a pair (hi::T, lo::T). An overflow in hi (if any) is ignored.

mulhilo(x::T, y::T) where T <: Unsigned

Calculates hi * B + lo = x * y, where B == typemax(T) + 1. Returns the result as a pair (hi::T, lo::T).

divremhilo(x_hi::T, x_lo::T, y::T) where T <: Unsigned

Calculates divrem(x_hi * B + x_lo, y), where B == typemax(T) + 1. Returns a tuple (q::T, r::T, o::Bool), where q is the quotient (the part of it fitting into the bits of T), r is the remainder is o is the overflow flag.

divhilo(x_hi::T, x_lo::T, y::T) where T <: Unsigned

Calculates div(x_hi * B + x_lo, y), where B == typemax(T) + 1. Returns a tuple (q::T, o::Bool), where q is the quotient (the part of it fitting into the bits of T), and o is the overflow flag.

remhilo(x_hi::T, x_lo::T, y::T) where T <: Unsigned

Calculates rem(x_hi * B + x_lo, y), where B == typemax(T) + 1.

addmod(x::T, y::T, modulus::T) where T <: Unsigned

Returns mod(x + y, modulus) (even if x + y overflows T). Assumes x and y are in range 0 ... modulus.

submod(x::T, y::T, modulus::T) where T <: Unsigned

Returns mod(x - y, modulus) (even if x - y underflows).

mulmod(x::T, y::T, modulus::T) where T <: Unsigned

Returns mod(x * y, modulus) (even if x * y overflows T).

powmod(x::T, y::V, modulus::T) where {T <: Unsigned, V}

Returns mod(x * y, modulus) (even if x * y overflows T).

Multi-precision unsigned integer type, with N limbs of type T (which must be an unsigned integer type).

Supports +, -, *, divrem, div, rem, mod, ^, ==, !=, <, <=, >, >=, zero, one, oneunit, iseven, isodd, typemin, typemax, iszero, sizeof (can be off if limbs have the type UInt4), bitsizeof, leading_zeros, trailing_zeros, eltype, abs.

Also supports num_bits, halve, double, encompassing_type.

The objects can be created either with convert(), or as

MLUInt(x::NTuple{N, T})
MLUInt{N, T}(x::NTuple{N, V})

Multi-precision unsigned integer type, with N limbs of type T (which must be an unsigned integer type).

Supports +, -, *, divrem, div, rem, mod, ^, ==, !=, <, <=, >, >=, zero, one, oneunit, iseven, isodd, typemin, typemax, iszero, sizeof (can be off if limbs have the type UInt4), bitsizeof, leading_zeros, trailing_zeros, eltype, abs.

Also supports num_bits, halve, double, encompassing_type.

The objects can be created either with convert(), or as

MLInt(x::NTuple{N, T})
MLInt{N, T}(x::NTuple{N, V})

An unsigned integer with all operations performed modulo M.

Supports +, -, *, divrem, div, rem, ^, <, <=, >, >=, zero, one and isodd. Note that the division is a regular division, not multiplication by the inverse (which is not guaranteed to exist for any M).

ModUInt{T, M}(x::Integer) where {T <: Unsigned, M}

Creates an ModUInt object. M must have the type T.

Residue ring element in Montgomery representation. Multiplication is much faster than for ModUInt, addition and subtraction are the same, but division and conversion to regular integers is slower.

Supports +, -, *, divrem, div, rem, ^, <, <=, >, >=, zero, one and isodd. Note that the division is a regular division, not multiplication by the inverse (which is not guaranteed to exist for any M).

MgModUInt{T, M}(x::Integer) where {T <: Unsigned, M}

Creates an MgModUInt object. M must have the type T and be an odd number.

raw_value(x::AbstractModUInt{T, M})

Returns the value of type T stored in the object (converted out of any special representation if necessary).

raw_value(x::AbstractModUInt{T, M})

Returns the raw value of type T stored in the object (without any conversions).

modulus(::Type{AbstractModUInt{T, M}})
modulus(x::AbstractModUInt{T, M})

Returns the modulus M (of type T) for a modulo integer object or type.

Fixed-size polynomials (with the degree limited by N-1). Currently supports moduli x^n-1 (cyclic_modulus) or x^n+1 (negacyclic_modulus). Supports any type that has arithmetic operators defined for it, including ModUInt and MgModUInt.

Polynomial(coeffs::AbstractArray{T, 1}, modulus::AbstractCyclicModulus) where T

Create a polynomial given the array of coefficients (the i-th coefficient corresponds to the (i-1)-th power).

mul_by_monomial(p::Polynomial, power::Integer)

Multiply the polynomial by x^power. If power lies outside [0, 2 * N) where N-1 is the maximum degree of the polynomial, a modulo 2 * N will be taken.

A constant denoting cyclic polynomial modulus (x^N - 1), to be supplied to the Polynomial constructor.

A constant denoting negacyclic polynomial modulus (x^N + 1), to be supplied to the Polynomial constructor.

known_isprime(::Val{X})

A method of this function can be defined by the user for a certain X to avoid isprime() being called on it when determining the multiplication function for a polynomial (which can reduce start-up time if X is very large).

known_polynomial_mul_function(::Type{T}, ::Val{N}, polynomial_modulus::AbstractPolynomialModulus)

A method of this function can be defined by the user to specify the multiplication function for a certain polynomial coefficient type, length and modulus. Has to return a function with the signature (p1::Polynomial{T, N}, p2::Polynomial{T, N}) :: Polynomial{T, N}, for example one of DarkIntegers.karatsuba_mul, DarkIntegers.nussbaumer_mul, DarkIntegers.ntt_mul.

broadcast_into_polynomial(func, args...)

Treat any polynomials in args as 1-dimensional arrays and apply func.(args...), saving the result into a new polynomial.

The moduli of the polynomials in args must be the same.

broadcast_into_polynomial!(func, p::Polynomial, args...)

Treat p and any polynomials in args as 1-dimensional arrays and apply p .= func.(args...).

The moduli of the polynomials in args and the modulus of p must be the same.

with_modulus(p::Polynomial{T, N}, new_modulus::AbstractPolynomialModulus)

Returns a new polynomial object with a changed modulus.

resize(p::Polynomial, new_length::Integer)

Returns a polynomial with changed length. If new_length is greater than the current length, coefficients for higher powers will be set to 0. If new_length is smaller, coefficients for higher powers will be discarded.

ntt(data::Array{T, 1}; inverse::Bool=false, tangent::Bool=false) where T <: AbstractModUInt

Perform an NTT on data. If tangent is true, use the tangent NTT (for multiplying tangent polynomials).

known_generator(::Val{X})

A method of this function can be defined by the user for a certain X to provide a known generator to use in NTT for this modulus.

A generator is a number g between 0 and X-1 such that g^1 mod X, ..., g^(X-1) mod X are all numbers from 1 to X-1 (in any order).