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.

1 files changed, 14 insertions, 0 deletions

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 };