nucypher / darkintegers.jl Goto Github PK
View Code? Open in Web Editor NEWA modulo arithmetic toolbox for integers and polynomials
Home Page: https://nucypher.github.io/DarkIntegers.jl
License: GNU General Public License v3.0
A modulo arithmetic toolbox for integers and polynomials
Home Page: https://nucypher.github.io/DarkIntegers.jl
License: GNU General Public License v3.0
Now that Polynomial
has a proper modulus
field, support for arbitrary moduli (in addition to the current x^N - 1
/x^N + 1
) can be added. The Polynomial
class may be split into two, non-modulo and modulo ones (same as we have now with integers).
Will need issue #6 implemented.
_benchmark_distribution()
can be replaced by setup=
keyword of @benchmark
. Instead of standard deviation, standard error of the mean should be printed.
Benchmark results should be looked at after this replacement - there is some overhead in @benchmark
, plus an incorrect choice between using symbols vs splicing arguments in this macro can change the results drastically.
To reduce the error, tests can be designed better - e.g. for divrem
of multi-limb integers check several cases of n
limbs by m
limbs, instead of taking a random over the whole range (which, naturally ends up as maximum limbs by maximum limbs in most cases).
Useful, for example, in RNS decomposition (issue #12).
See the last line, x, c1 || c2
. We're joining two carry bits there because it seems that they are never 1
at the same time, but that remains to be proven. Exhaustive tests seem to pass, though.
At the moment of writing it the primary focus were negacyclic convolutions, so nussbaumer_mul_cyclic()
never got unrolled, but doing so will speed it up.
Currently it is calculated just as 0 - x
, which can probably be improved.
Useful for HEAAN. For reference see:
rns.jl
)The question is, can we cram the moduli into the type like ModUInt
does? In particular, how fast it will be?
Also check out RNS conversion based on core functions (see especially Abtahi et al, 2005, 10.1016/j.camwa.2005.03.008). Also see other ways in "Residue Number Systems"; and RNS to integer conversion using reconstruction coefficients in Montgomery form (allows us to keep inside the modulus range, but apparently quite slow as compared to straightforward reconstruction coefficient multiplication).
A number of paper works with "centralized" modulo numbers, that is for a modulus q
they lie in [-q÷2, q÷2]
. For example, see Shuhong Gao's FHE scheme (and SGFHE project).
See the line a = submod(a, p2, m)
. submod()
requires both of its first two arguments to be lower than m
, but I am not sure how to prove that a
satisfies that.
On the other hand, exhaustive tests with MLUInt{2}
pass, so perhaps it's okay?
Originally they were removed because of combinatorial explosion when new types are added, and currently one has to unpack ModUInt
and MgModUInt
using value()
before conversion.
It may be possible to build a sensible conversion system that won't double in size when, e.g. ModInt
and MgModInt
are added (see issue #10).
Currently it transforms the argument from Montgomery representation first. Can we determine if the value is odd or not without the transformation?
Two possible variants:
typemax()
(see e.g. efficient multiplication https://hal-lirmm.ccsd.cnrs.fr/file/index/docid/106470/filename/D547.PDF)According to Knuth it loops at most twice, so unrolling it may speed the function up.
See e.g. R. Crandall and C. Pomerance, "Prime Numbers", Algorithm 9.5.2
Need to support constructions like
rand(MLUInt)
rand(MLInt)
rand(a:b) # where `a`, `b` are of type `MLUInt`/`MLInt`
Currently implemented: MLUInt % built_in_type
. Remaining:
MLInt % built_in_type
MLUInt/MLInt % MLUInt/MLInt
built_in_type % MLUInt/MLInt
from_montgomery()
's performance depends on whether we use mulmod_montgomery(x, 1)
or mulmod_montgomery(1, x)
- the former works faster with MLUInt{3, UInt32}
, and the latter with MLUInt{2, UInt64}
. Need to run tests on different combinations, determine the pattern, and make several implementations.
See the LogProof
project for an example.
Those would be useful to have, but one needs to check first if Julia provides any constant-time guarantees for its functions on builtin types. If not, this may be achieved by linking a C library, but that would defeat the purpose of easily-modifiable all-Julia implementation.
Currently limbs in MLUInt
/MLInt
are stored as big-endian, because that's how multi-limb algorithms are generally described in the literature (e.g. in TAOCP or Handbook of Applied Cryptography). Perhaps, little-endian would be a more convenient format - limbs are already little-endian (on most systems where this library actually works), and it will help visually compare MLUInt
/MLInt
numbers with builtin types, or initialize them with predefined constants.
The title says it all.
One problem I can see is what if the highmost coefficient isn't a multiple of the highmost coefficient of the divisor? For example, (3x^4 + 1) ÷ (2x^2 + 1)
. Convert to floating point coefficients (possibly the same as Julia does it, that is have /
and ÷
operations)? Disallow divisors with the highmost coefficient other than one (this will work for the purposes of polynomial moduli, at least, since that's the case for all of them)?
Currently it is super-slow, even streamlined from mod(MLUInt{N, T}, MLUInt{N, T})
(10x the times for BigInt), but it would be very useful for RNS decomposition (issue #12). Need to see if we can lift NTL or https://github.com/niekbouman/ctbignum implementation.
Specifically, for MLUInt
. If we don't have to calculate the remainder/the quotient, will it be faster?
The branch adk_mul
contains an implementation of arbitrary degree Karatsuba (ADK), in polynomials.jl::adk_mul()
.
Sources:
It is faster than mul_naive()
and even mul_karatsuba
for small polynomial sizes (still N^2
complexity though, so Karatsuba wins for larger sizes). It also does not require the polynomial size to be a power of 2.
It may be possible to get rid of the additional buffer requirement, in which case it will become even faster.
In Julia, MyType{T, V} <: MyType{T}
, so in some sense the first type argument is more "basic" than the second one. MLUInt
/MLInt
have arguments {N, T}
, so the number of limbs is first, then the type. This is made by analogy with NTuple
, for which this may be more logical, but for multi-limb integers the order may be better reversed.
Although, to be fair, it is exclusively a cosmetic change, since it is no problem to generalize the first type argument explicitly when necessary: MyType{Int, Bool} <: MyType{T, Bool} where T
.
Currently it is a very crude implementation using Julia's bitstring()
. Although it is called only during NTT plan creation, and the plans are cached, so its performance is not too important.
Currently mulmod()
uses divrem()
which can be quite slow.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.