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.

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})

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})

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.

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.

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

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.

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.

as_builtin(x)

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

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.

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.

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.

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.

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.

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

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

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

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

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

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

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

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.

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

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

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

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

num_bits(x)

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

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

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

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

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

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.

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.

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

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

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

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

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

Returns a new polynomial object with a changed modulus.

Prepared NTT plan.

If tangent is false, the NTT can be used to multiply polynomials modulo X^len-1 (cyclic), if it is true, it can be used to multiply polynomials modulo X^len+1 (negacyclic).

Select the best available polynomial multiplication function based on the element type an polynomial length.

Recursive Karatsuba multiplication function. Multiplies two polynomials of length full_len (must be a power of 2) whose coefficients are stored in arrays p1c and p2c starting from locations p1_s and p2_s, respectively. The result is placed in the array res starting from the location res_s. res is assumed to have enough space to store the full result of length 2 * full_len. buf and buf2 are temporary buffers with enough space for 2 * full_len elements starting from locations buf_s and buf2_s, respectively.

Calculates x * y, where x is a multi-precision number of length N, and y is a single radix digit. Returns the N+1-long result as tuple of the lowest digit and a multi-precision number with the N highest digits.

Since widen(UInt128) == BigInt, we need a specialized version to avoid allocations.

Returns the pair (hi, lo) of x + y + z. That is, hi * R + lo = x + y + z, where 0 <= x, y, z, lo < R, hi <= 2, and R = typemax(T) + 1.

If z <= 1, hi <= 1 (so it can be used as new_carry, res = addcarry(x, y, carry)).

A specialized version for z == 0.

A multi-limb version of addcarry.

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

Same as addmod(), but assumes that x + y doesn't overflow T (that is, modulus is less than or equal to half of typemax(T)+1).

Reverses the order of the lowest l bits in x and fills the rest with 0s.

Finds a generator element for a finite field defined by type T (that is, we assume that the modulus in T is prime). This means that every power of the returned g from 1 to M-1 produces all the elements of the field (integers from 1 to M-1), and g^(M-1) = 1.

Recovers an integer from Montgomery representation (that is, calculates x given x * R mod m, where R = typemax(MLUInt{N, T}) + 1).

Returns the scaling coefficient for the inverse NTT. Similarly to FFT, it's 1/N, but in our case we need to take the finite field inverse.

An implementation of Montgomery coefficient for a multi-precision number. Using the fact that m^(-1) mod R == (mod(m, b+1))^(-1) mod b, where b = typemax(T)+1 is the radix, and R = b^N = typemax(MLUInt{N, T})+1 is the total size of the type.

Calculate the coefficient used for multiplication and conversion from M. representation. Namely, m' = m^(-1) mod b, where b = typemax(T)+1.

An implementation of Montgomery coefficient for a multi-precision number. Using the fact that m^(-1) mod R == (mod(m, b+1))^(-1) mod b, where b = typemax(T)+1 is the radix, and R = b^N = typemax(MLUInt{N, T})+1 is the total size of the type.

Calculate the coefficient used for multiplication and conversion from M. representation. Namely, m' = -m^(-1) mod b, where b = typemax(T)+1.

Note that this coefficient is different from what the non-constant-time version uses.

Returns the root of one for NTT (an analogue of the root of one in FFT, e^(-2pi * im / N); the returned value also has the property w^N = 1). (M-1) must be divisible by N, where M is the modulus of the type T.

Calculates the coefficient for conversion of an integer to Montgomery representation.

Multiplies two polynomials using Karatsuba algorithm. Assumes the polynomials have the same length and the same value of the modulus field.

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.

Caches the coefficient used for multiplication and conversion from Montgomery representation based on the type.

Multiplies two polynomials of length l whose coefficients are stored in arrays p1c and p2c starting from locations p1_s and p2_s, respectively. The result is placed in the array res starting from the location res_s. res is assumed to have enough space to store the full result of length 2l.

Returns x + y * z, where x and y are multi-limb integers.

Returns the pair (hi, lo) of x + y * z + w. That is, hi * R + lo = x + y * z + w, where 0 <= x, y, z, w, hi, lo < R, and R = typemax(T) + 1.

Modulo multiplication using bitshift (by 1 bit) and modulo addition/subtraction.

An implementation of Montgomery reduction for simple types. Treats them as MLUInts of length 1.

Montgomery multiplication (or Montgomery reduction algorithm). For x = x' * R mod m and y = y' * R mod m calculates x' * y' * R mod m, where R = typemax(MLUInt{N, T}) + 1. m_prime is the Montgomery coefficient (see get_montgomery_coeff).

An optimized version of mulmod_montgomery for the cases when one of the factors has only one limb.

Modulo multiplication using wide multiplication into separate hi/lo variables.

Modulo multiplication using wide multiplication into a single bigger type.

Multiplies two polynomials using NTT. Assumes the polynomials have the same length and the same value of the modulus field.

Multiplies two polynomials using Nussbaumer convolution algorithm. Assumes the polynomials have the same length and the same value of the modulus field.

Given a MLUInt {x1, x2, ..., xN-1, xN} returns a tuple (x1, {x2, x3, ..., xN, 0}).

Returns the pair (new_borrow, res) of x - (y + borrow >> (sizeof(T) - 1)). borrow and new_borrow can be either 0 or typemax(T), the latter meaning that the borrow occurred during subtraction.

Note that it is not an analogue of addhilo for subtraction.

And extended version of subborrow() for two multi-limb integers (x..., x_hi) and (y..., y_hi) (x and y represent lower limbs of the corresponding numbers). Returned borrow is the same as for the single-limb subborrow().

Returns mod((x..., x_hi) - (y..., y_hi), m). Assumes -m <= (x..., x_hi) - (y..., y_hi) < m.

Converts an integer to Montgomery representation (that is, calculates x * R mod m == x * coeff mod m where coeff = R mod m, where R = typemax(T) + 1).

Caches the coefficient used for conversion to Montgomery representation based on the type.