Manual
In this section we assume that every example is preceded with
using DarkIntegers
Multi-limb integers
The basic facility in DarkIntegers
are multi-limb unsigned integers MLUInt{N, T}
. The type takes two parameters, N
(an integer) being the number of limbs, or digits, and T
(an unsigned integer type) is the type of a limb. Its functionality is closer to that of BigInt
, but MLUInt
still has fixed length (although it can be much greater than what any Julia built-in type supports). On the other hand, operations with it do not require dynamic memory allocation and are faster than the BigInt
ones.
The MLUInt
constructor takes any integer:
a = MLUInt{2, UInt8}(65534)
println(a)
# output
{(0xfe, 0xff)}
Note that the limbs are arranged in the big-endian order.
A multi-limb integer can be converted back to any integer:
b = convert(Int, a)
println(b)
# output
65534
Multi-precision numbers support arithmetic operations and comparisons and act identically to built-in unsigned integer types:
a = MLUInt{2, UInt8}(65534)
b = MLUInt{2, UInt8}(65533)
println(a + b)
println(convert(Int, a + b))
# output
{(0xfb, 0xff)}
65531
Modulo integers
The next level above multi-limb integers (and built-in unsigned integers) are unsigned integers with arithmetic operations performed modulo some number. The object of type ModUInt{T, M}
is parametrized by the number type T
(an unsigned integer) and the modulus M
(which is a value of type T
).
Similarly to MLUInt
objects, ModUInt
objects can be constructed out of an integer. If the integer is greater than the modulus, it will be truncated (by applying mod()
):
modulus = UInt8(200)
a = ModUInt{UInt8, modulus}(250)
println(a)
# output
50RR
All arithmetic operations on ModUInt
objects are performed modulo modulus
. Any regular integers in mixed expressions are promoted to ModUInt
objects:
println(a + 101)
# output
151RR
ModUInt
objects can be converted back to integers after extracting its value with value
:
println(convert(Int, value(a)))
# output
50
Montgomery representation
Modulo integers can be converted to an alternate representation, which makes use of Montgomery reduction for multiplication. As a result, the multiplication becomes much faster, addition and subtraction stay the same, and division (and conversion to and from integers) become slower. The representation implemented as the type MgModUInt{T, M}
, which is parametrized in the same way as ModUInt
. Depending on the relative amount of different arithmetic operations one needs to perform, either ModUInt
or MgModUInt
may perform better.
The interface is the same as the one for ModUInt
, except for the restriction on M
to be an odd number:
modulus = UInt8(201)
a = MgModUInt{UInt8, modulus}(250)
println(a)
println(convert(Int, value(a + 101)))
# output
49RRM
150
Cyclic polynomials
Anything type supporting arithmetic operations (including MLUInt
, ModUInt
and MgModUInt
) can serve as the coefficient type in the Polynomial
type. DarkIntegers
supports cyclic polynomials (with operations performed modulo x^n-1
, where n
is some non-negative integer called the length of the polynomial) and negacyclic ones (with operations performed modulo x^n+1
).
Polynomials are created out of a coefficient array (where the i
-th element corresponds to the (i-1)
-th power of x
) and negacyclic modulus (x^N+1
):
p = Polynomial([1, 2, 3, 4], negacyclic_modulus) # creates a negacyclic polynomial
println(p)
println(p + 1)
println(p * 2)
# output
Polynomial{Int64,4}([1, 2, 3, 4], DarkIntegers.NegacyclicModulus(), DarkIntegers.karatsuba_mul, false)
Polynomial{Int64,4}([2, 2, 3, 4], DarkIntegers.NegacyclicModulus(), DarkIntegers.karatsuba_mul, false)
Polynomial{Int64,4}([2, 4, 6, 8], DarkIntegers.NegacyclicModulus(), DarkIntegers.karatsuba_mul, false)
The polynomial can be multiplied by a power of x
using mul_by_monomial
. Since the polynomial we created is cyclic, the coefficients with the powers greater or equal to n
will reappear from the other side with the opposite sign (one can work it out by applying the x^n+1
modulus manually):
println(mul_by_monomial(p, 2))
# output
Polynomial{Int64,4}([-3, -4, 1, 2], DarkIntegers.NegacyclicModulus(), DarkIntegers.karatsuba_mul, false)
Note the multiplication function that is the part of the Polynomial
structure. The default for the multiplication is Karatsuba algorithm; if possible a more faster NTT-based algorithm will be chosen. It requires:
- the coefficient type to be a modulo integer (
ModUInt
orMgModUInt
) with a prime modulus; - the length of the polynomial to be a power of 2;
- the length of the polynomial to be a factor of
(modulus - 1)
for cyclic polynomials, and(modulus - 1)/2
for negacyclic ones.
For example:
modulus = UInt8(241)
tp = ModUInt{UInt8, modulus}
p1 = Polynomial(tp[1, 2, 3, 4], negacyclic_modulus)
p2 = Polynomial(tp[1, 0, 1, 0], negacyclic_modulus)
println(p1)
println(p2)
println(p1 * p2)
# output
Polynomial{ModUInt{UInt8,0xf1},4}(ModUInt{UInt8,0xf1}[1RR, 2RR, 3RR, 4RR], DarkIntegers.NegacyclicModulus(), DarkIntegers.ntt_mul, false)
Polynomial{ModUInt{UInt8,0xf1},4}(ModUInt{UInt8,0xf1}[1RR, 0RR, 1RR, 0RR], DarkIntegers.NegacyclicModulus(), DarkIntegers.ntt_mul, false)
Polynomial{ModUInt{UInt8,0xf1},4}(ModUInt{UInt8,0xf1}[239RR, 239RR, 4RR, 6RR], DarkIntegers.NegacyclicModulus(), DarkIntegers.ntt_mul, false)