| Age | Commit message (Collapse) | Author |
|---|
|
|
|
These changes are arbitrarily divided into multiple commits to make it
easier to find potentially introduced bugs with git bisect.
|
|
Found by oss-fuzz: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=29326
|
|
|
|
This fixes the issue with the exported data having a leading zero,
causing RSA::encrypt to trim the block down, and ruining the encryption.
Fixes #2691 :^)
|
|
|
|
|
|
No need to do complicated math to import or export numbers,
just convert the byte stream to words and vice versa.
|
|
|
|
All the magic is happening in a "while != 0" loop, so we ended up with
an empty string for zero-value BigIntegers. Now we just check that
upfront and return early.
|
|
This patchset adds a simple SignedBigInteger that is entirely defined in
terms of UnsignedBigInteger.
It also adds a NumberTheory::Power function, which is terribly
inefficient, but since the use of exponentiation is very much
discouraged for large inputs, no particular attempts were made
to make it more performant.
|
|
.. and make travis run it.
I renamed check-license-headers.sh to check-style.sh and expanded it so
that it now also checks for the presence of "#pragma once" in .h files.
It also checks the presence of a (single) blank line above and below the
"#pragma once" line.
I also added "#pragma once" to all the files that need it: even the ones
we are not check.
I also added/removed blank lines in order to make the script not fail.
I also ran clang-format on the files I modified.
|
|
This avoids repeated traversals of the underlying words and gives a
30% speed-up on "test-crypto -t pk" :^)
|
|
Use Vector::resize_and_keep_capacity() to resize BigInt vectors to just
the right size without risking deallocation. Then do direct indexed
accesses to the underlying words (or use memset/memcpy.)
This gives a ~40% speed-up on the RSA tests in "test-crypto -t pk" :^)
|
|
|
|
This changes the plus, minus, etc... operators from UnsignedBigInteger to use a
static helper method. The static methods do not allocate any variables, instead
all the required BigInteger output and temporary variables are required on call
as parameters.
This change already optimizes the number of allocations in complex operations
such as multiply or divide, by having a single allocation per call (instead of
one per loop).
This new API also provides a way to limit the number of allocations for complex
computations in other parts of the code. This is done by using these helpers in
any place that currently makes use of the standard operators.
|
|
|
|
This commit attempts to make UnsignedBigInteger as fast as possible
without changing the underlaying architecture.
This effort involves
- Preallocating space for vector operations
- Avoiding calls to computationally expensive functions
- Inlining or flattening functions (sensibly)
|
|
|
|
|
|
This shaves off 1 second of runtime
|
|
These functions allow conversion to-and-from big-endian buffers
This commit also adds a ""_bigint operator for easy bigint use
|
|
- Add missing 'explicit' to the constructor
- Remove unneeded 'AK::' in AK::Vector
- Avoid copying 'words' in constructor
|
|
|
|
A regression test was added to the suite.
This commit also generally simplifies the subtraction method.
|
|
The division operation returns both the quotient and the remainder.
|
|
Also added documentation for the runtime complexity of some operations.
|
|
There was a bug when dealing with a carry when the addition
result for the current word was UINT32_MAX.
This commit also adds a regression test for the bug.
|
|
|
|
UnsignedBigInteger stores an unsigned ainteger of arbitrary length.
A big integer is represented as a vector of word. Each
word is an unsigned int.
|
