From 485adb5e29853cb54a3dc4a314f37e7a5528f57c Mon Sep 17 00:00:00 2001 From: DexesTTP Date: Wed, 12 May 2021 22:47:07 +0200 Subject: LibCrypto: Add the montgomery modular power algorithm This algorithm allows for much faster computations of modular powers (around a 5x-10x speedup of the Crypto test). However, it is only valid for odd modulo values, and therefore the old algorithm must be kept for computations involving even modulo values. --- .../Libraries/LibCrypto/NumberTheory/ModularFunctions.cpp | 14 ++++++++++++++ 1 file changed, 14 insertions(+) (limited to 'Userland/Libraries/LibCrypto/NumberTheory') diff --git a/Userland/Libraries/LibCrypto/NumberTheory/ModularFunctions.cpp b/Userland/Libraries/LibCrypto/NumberTheory/ModularFunctions.cpp index 83212d8b84..a4beb68e45 100644 --- a/Userland/Libraries/LibCrypto/NumberTheory/ModularFunctions.cpp +++ b/Userland/Libraries/LibCrypto/NumberTheory/ModularFunctions.cpp @@ -37,6 +37,20 @@ UnsignedBigInteger ModularPower(const UnsignedBigInteger& b, const UnsignedBigIn if (m == 1) return 0; + if (m.is_odd()) { + UnsignedBigInteger temp_z0 { 0 }; + UnsignedBigInteger temp_rr { 0 }; + UnsignedBigInteger temp_one { 0 }; + UnsignedBigInteger temp_z { 0 }; + UnsignedBigInteger temp_zz { 0 }; + UnsignedBigInteger temp_x { 0 }; + UnsignedBigInteger temp_extra { 0 }; + + UnsignedBigInteger result; + UnsignedBigIntegerAlgorithms::montgomery_modular_power_with_minimal_allocations(b, e, m, temp_z0, temp_rr, temp_one, temp_z, temp_zz, temp_x, temp_extra, result); + return result; + } + UnsignedBigInteger ep { e }; UnsignedBigInteger base { b }; -- cgit v1.2.3