Speedup RawMod.is_residue by using fast Jacobi symbol impl.

2 files changed, 29 insertions, 2 deletions

diff --git a/pyecsca/ec/mod.py b/pyecsca/ec/mod.py
index cb9ef7e..8aca8a9 100644
--- a/pyecsca/ec/mod.py
+++ b/pyecsca/ec/mod.py
@@ -60,6 +60,28 @@ def extgcd(a, b):
 
 
 @public
+def jacobi(x: int, n: int):
+    """Jacobi symbol."""
+    if n <= 0:
+        raise ValueError("'n' must be a positive integer.")
+    if n % 2 == 0:
+        raise ValueError("'n' must be odd.")
+    x %= n
+    r = 1
+    while x != 0:
+        while x % 2 == 0:
+            x //= 2
+            nm8 = n % 8
+            if nm8 == 3 or nm8 == 5:
+                r = -r
+        x, n = n, x
+        if x % 4 == 3 and n % 4 == 3:
+            r = -r
+        x %= n
+    return r if n == 1 else 0
+
+
+@public
 @lru_cache
 def miller_rabin(n: int, rounds: int = 50) -> bool:
     """Miller-Rabin probabilistic primality test."""
@@ -257,7 +279,7 @@ class RawMod(Mod):
             return True
         if self.n == 2:
             return self.x in (0, 1)
-        legendre_symbol = self ** ((self.n - 1) // 2)
+        legendre_symbol = jacobi(self.x, self.n)
         return legendre_symbol == 1
 
     def sqrt(self):
diff --git a/test/ec/test_mod.py b/test/ec/test_mod.py
index 4c0c483..a21ef06 100644
--- a/test/ec/test_mod.py
+++ b/test/ec/test_mod.py
@@ -1,7 +1,7 @@
 from sympy import FF, symbols
 from unittest import TestCase
 
-from pyecsca.ec.mod import Mod, gcd, extgcd, Undefined, miller_rabin, has_gmp, RawMod, SymbolicMod
+from pyecsca.ec.mod import Mod, gcd, extgcd, Undefined, miller_rabin, has_gmp, RawMod, SymbolicMod, jacobi
 from pyecsca.ec.error import NonInvertibleError, NonResidueError, NonInvertibleWarning, NonResidueWarning
 from pyecsca.misc.cfg import getconfig, TemporaryConfig
 
@@ -13,6 +13,11 @@ class ModTests(TestCase):
         self.assertEqual(extgcd(15, 0), (1, 0, 15))
         self.assertEqual(extgcd(15, 20), (-1, 1, 5))
 
+    def test_jacobi(self):
+        self.assertEqual(jacobi(5, 1153486465415345646578465454655646543248656451), 1)
+        self.assertEqual(jacobi(564786456646845, 46874698564153465453246546545456849797895547657), -1)
+        self.assertEqual(jacobi(564786456646845, 46874698564153465453246546545456849797895), 0)
+
     def test_miller_rabin(self):
         self.assertTrue(miller_rabin(2))
         self.assertTrue(miller_rabin(3))