diff options
| author | Jack Lloyd <[email protected]> | 2018-02-26 11:48:12 -0500 |
|---|---|---|
| committer | Jack Lloyd <[email protected]> | 2018-02-26 12:00:24 -0500 |
| commit | 50c69e760b0f47e84f5a3c8d2bea6f072f3fd587 (patch) | |
| tree | f3b20364b9ea7a276a2f6222f198a18e50d5deee /src/lib/math/bigint/bigint.cpp | |
| parent | ac1d24cf06de5e800cbb8a3c7ab392c081aeb783 (diff) | |
Optimize Barrett reduction
OSS-Fuzz 6570 flagged an issue with slow modular exponentation.
It turned out the problem was not in the library version but the
simple square-and-multiply algorithm. Computing g^x % p with all
three integers being dense (high Hamming weight) numbers took about
1.5 seconds on a fast machine with almost all of the time taken
by the Barrett reductions. With these changes, same testcase
now takes only a tiny fraction of a second.
Diffstat (limited to 'src/lib/math/bigint/bigint.cpp')
| -rw-r--r-- | src/lib/math/bigint/bigint.cpp | 5 |
1 files changed, 5 insertions, 0 deletions
diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index c822a94e1..e99ddb50a 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -13,6 +13,11 @@ namespace Botan { +BigInt::BigInt(const word words[], size_t length) + { + m_reg.assign(words, words + length); + } + /* * Construct a BigInt from a regular number */ |