Commit fb63a2cfae

Frank Denis <github@pureftpd.org>
2020-10-06 14:02:06
std/crypto: faster (mod 2^255-19) square root computation
251 squarings, 250 multiplications -> 251 squarings, 11 multiplications
master
1 parent dd4771a
Changed files (1)
lib
std
crypto
25519
field.zig
lib/std/crypto/25519/field.zig
@@ -307,12 +307,14 @@ pub const Fe = struct {
     }
 
     pub fn pow2523(a: Fe) Fe {
-        var c = a;
-        var i: usize = 0;
-        while (i < 249) : (i += 1) {
-            c = c.sq().mul(a);
-        }
-        return c.sq().sq().mul(a);
+        var t0 = a.mul(a.sq());
+        var t1 = t0.mul(t0.sqn(2)).sq().mul(a);
+        t0 = t1.sqn(5).mul(t1);
+        var t2 = t0.sqn(5).mul(t1);
+        t1 = t2.sqn(15).mul(t2);
+        t2 = t1.sqn(30).mul(t1);
+        t1 = t2.sqn(60).mul(t2);
+        return t1.sqn(120).mul(t1).sqn(10).mul(t0).sqn(2).mul(a);
     }
 
     pub fn abs(a: Fe) Fe {