`DarkIntegers.cyclic_modulus`

— ConstantA constant denoting cyclic polynomial modulus (`x^N - 1`

), to be supplied to the `Polynomial`

constructor.

`DarkIntegers.negacyclic_modulus`

— ConstantA constant denoting negacyclic polynomial modulus (`x^N + 1`

), to be supplied to the `Polynomial`

constructor.

`DarkIntegers.MLInt`

— TypeMulti-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.MLUInt`

— TypeMulti-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.MgModUInt`

— TypeResidue 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.ModUInt`

— TypeAn 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.Polynomial`

— TypeFixed-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.addhilo`

— Method`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.addmod`

— Method`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.as_builtin`

— Method`as_builtin(x)`

Returns the integer `x`

converted to a builtin type with the minimum suitable size.

`DarkIntegers.bitsizeof`

— Method```
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_polynomial`

— Method`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.divhilo`

— Method`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.divremhilo`

— Method`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_type`

— Method`encompassing_type(tp::Type{<:Unsigned})`

Returns the built-in type that covers all the range of `tp`

(not necessarily unsigned).

`DarkIntegers.known_generator`

— Method`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.log_bitsizeof`

— Method```
log_bitsizeof(::Type{T}) where T
log_bitsizeof(x)
```

`log2()`

of the value returned by `bitsizeof`

for that argument.

`DarkIntegers.modulus`

— Method```
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_monomial`

— Method`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.mulhilo`

— Method`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.mulmod`

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

Returns `mod(x * y, modulus)`

(even if `x * y`

overflows `T`

).

`DarkIntegers.ntt`

— Method`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.num_bits`

— Method`num_bits(x)`

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

`DarkIntegers.powmod`

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

Returns `mod(x * y, modulus)`

(even if `x * y`

overflows `T`

).

`DarkIntegers.raw_value`

— Method`raw_value(x::AbstractModUInt{T, M})`

Returns the raw value of type `T`

stored in the object (without any conversions).

`DarkIntegers.remhilo`

— Method`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.resize`

— Method`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.submod`

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

Returns `mod(x - y, modulus)`

(even if `x - y`

underflows).

`DarkIntegers.value`

— Method`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_modulus`

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

Returns a new polynomial object with a changed modulus.

`DarkIntegers.NTTPlan`

— TypePrepared 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._get_polynomial_mul_function`

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

`DarkIntegers._karatsuba_mul`

— MethodRecursive 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_single`

— MethodCalculates `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.addcarry`

— MethodSince `widen(UInt128) == BigInt`

, we need a specialized version to avoid allocations.

`DarkIntegers.addcarry`

— MethodReturns 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.addcarry`

— MethodA specialized version for `z == 0`

.

`DarkIntegers.addcarry_ml`

— MethodA multi-limb version of `addcarry`

.

`DarkIntegers.addmod_no_overflow`

— Method`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.bitreverse`

— MethodReverses the order of the lowest `l`

bits in `x`

and fills the rest with 0s.

`DarkIntegers.find_generator`

— MethodFinds 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_montgomery`

— MethodRecovers an integer from Montgomery representation (that is, calculates `x`

given `x * R mod m`

, where `R = typemax(MLUInt{N, T}) + 1`

).

`DarkIntegers.get_inverse_coeff`

— MethodReturns 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.

`DarkIntegers.get_montgomery_coeff`

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

— MethodCalculate the coefficient used for multiplication and conversion from M. representation. Namely, `m' = m^(-1) mod b`

, where `b = typemax(T)+1`

.

`DarkIntegers.get_montgomery_coeff_ct`

— MethodAn 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_ct`

— MethodCalculate 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_one`

— MethodReturns 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.get_to_montgomery_coeff`

— MethodCalculates the coefficient for conversion of an integer to Montgomery representation.

`DarkIntegers.karatsuba_mul`

— MethodMultiplies two polynomials using Karatsuba algorithm. Assumes the polynomials have the same length and the same value of the `modulus`

field.

`DarkIntegers.known_isprime`

— Method`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_function`

— Method`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.montgomery_coeff`

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

`DarkIntegers.mul_naive`

— MethodMultiplies 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.muladd_ml`

— MethodReturns `x + y * z`

, where `x`

and `y`

are multi-limb integers.

`DarkIntegers.muladdcarry`

— MethodReturns 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.mulmod_bitshift`

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

`DarkIntegers.mulmod_montgomery`

— MethodAn implementation of Montgomery reduction for simple types. Treats them as `MLUInt`

s of length 1.

`DarkIntegers.mulmod_montgomery`

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

).

`DarkIntegers.mulmod_montgomery`

— MethodAn optimized version of `mulmod_montgomery`

for the cases when one of the factors has only one limb.

`DarkIntegers.mulmod_remhilo`

— MethodModulo multiplication using wide multiplication into separate hi/lo variables.

`DarkIntegers.mulmod_widemul`

— MethodModulo multiplication using wide multiplication into a single bigger type.

`DarkIntegers.ntt_mul`

— MethodMultiplies two polynomials using NTT. Assumes the polynomials have the same length and the same value of the `modulus`

field.

`DarkIntegers.nussbaumer_mul`

— MethodMultiplies two polynomials using Nussbaumer convolution algorithm. Assumes the polynomials have the same length and the same value of the `modulus`

field.

`DarkIntegers.shift_by_one`

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

`DarkIntegers.subborrow`

— MethodReturns 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_ml`

— MethodAnd 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.submod_inner`

— MethodReturns `mod((x..., x_hi) - (y..., y_hi), m)`

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

.

`DarkIntegers.to_montgomery`

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

).

`DarkIntegers.to_montgomery_coeff`

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