DarkIntegers.MLIntType

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})
DarkIntegers.MLUIntType

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})
DarkIntegers.MgModUIntType

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.

DarkIntegers.ModUIntType

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.

DarkIntegers.PolynomialType

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

DarkIntegers.addhiloMethod
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.

DarkIntegers.addmodMethod
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.

DarkIntegers.bitsizeofMethod
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.

DarkIntegers.broadcast_into_polynomial!Method
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.

DarkIntegers.broadcast_into_polynomialMethod
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.

DarkIntegers.divhiloMethod
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.

DarkIntegers.divremhiloMethod
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.

DarkIntegers.encompassing_typeMethod
encompassing_type(tp::Type{<:Unsigned})

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

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

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

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

DarkIntegers.mul_by_monomialMethod
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.

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

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

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

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

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

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

DarkIntegers.raw_valueMethod
raw_value(x::AbstractModUInt{T, M})

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

DarkIntegers.remhiloMethod
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.

DarkIntegers.resizeMethod
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.

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

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

DarkIntegers.valueMethod
raw_value(x::AbstractModUInt{T, M})

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

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

Returns a new polynomial object with a changed modulus.

DarkIntegers.NTTPlanType

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

DarkIntegers._karatsuba_mulMethod

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.

DarkIntegers._mul_by_singleMethod

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.

DarkIntegers.addcarryMethod

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

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

DarkIntegers.find_generatorMethod

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.

DarkIntegers.from_montgomeryMethod

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

DarkIntegers.get_montgomery_coeffMethod

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.

DarkIntegers.get_montgomery_coeff_ctMethod

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.

DarkIntegers.get_montgomery_coeff_ctMethod

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.

DarkIntegers.get_root_of_oneMethod

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.

DarkIntegers.karatsuba_mulMethod

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

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

DarkIntegers.known_polynomial_mul_functionMethod
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.

DarkIntegers.mul_naiveMethod

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.

DarkIntegers.muladdcarryMethod

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.

DarkIntegers.ntt_mulMethod

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

DarkIntegers.nussbaumer_mulMethod

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

DarkIntegers.subborrowMethod

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.

DarkIntegers.subborrow_mlMethod

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

DarkIntegers.to_montgomeryMethod

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