From d40de259097c5e8d8fd35539560ca7c3d47523e7 Mon Sep 17 00:00:00 2001
From: Ryan Rueger <git@rueg.re>
Date: Sat, 1 Mar 2025 20:25:41 +0100
Subject: Initial Commit
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Co-Authored-By: Damien Robert <Damien.Olivier.Robert+git@gmail.com>
Co-Authored-By: Frederik Vercauteren <frederik.vercauteren@gmail.com>
Co-Authored-By: Jonathan Komada Eriksen <jonathan.eriksen97@gmail.com>
Co-Authored-By: Pierrick Dartois <pierrickdartois@icloud.com>
Co-Authored-By: Riccardo Invernizzi <nidadoni@gmail.com>
Co-Authored-By: Ryan Rueger <git@rueg.re>                                                                                                                                           [0.01s]
Co-Authored-By: Benjamin Wesolowski <benjamin@pasch.umpa.ens-lyon.fr>
Co-Authored-By: Arthur Herlédan Le Merdy <ahlm@riseup.net>
Co-Authored-By: Boris Fouotsa <tako.fouotsa@epfl.ch>
---
 theta_lib/utilities/fast_sqrt.py | 55 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 55 insertions(+)
 create mode 100644 theta_lib/utilities/fast_sqrt.py

(limited to 'theta_lib/utilities/fast_sqrt.py')

diff --git a/theta_lib/utilities/fast_sqrt.py b/theta_lib/utilities/fast_sqrt.py
new file mode 100644
index 0000000..0609fe5
--- /dev/null
+++ b/theta_lib/utilities/fast_sqrt.py
@@ -0,0 +1,55 @@
+
+# ============================================ #
+#     Fast square root and quadratic roots     #
+# ============================================ #
+
+"""
+Most of this code has been taken from:
+https://github.com/FESTA-PKE/FESTA-SageMath
+
+Copyright (c) 2023 Andrea Basso, Luciano Maino and Giacomo Pope.
+
+Functions with another Copyright mention are not from the above authors.
+"""
+
+def sqrt_Fp2(a):
+    """
+    Efficiently computes the sqrt
+    of an element in Fp2 using that
+    we always have a prime p such that
+    p ≡ 3 mod 4.
+    """
+    Fp2 = a.parent()
+    p = Fp2.characteristic()
+    i = Fp2.gen() # i = √-1
+
+    a1 = a ** ((p - 3) // 4)
+    x0 = a1 * a
+    alpha = a1 * x0
+
+    if alpha == -1:
+        x = i * x0
+    else:
+        b = (1 + alpha) ** ((p - 1) // 2)
+        x = b * x0
+
+    return x
+
+def n_sqrt(a, n):
+    for _ in range(n):
+        a = sqrt_Fp2(a)
+    return a
+
+def sqrt_Fp(a):
+    """
+    Efficiently computes the sqrt
+    of an element in Fp using that
+    we always have a prime p such that
+    p ≡ 3 mod 4.
+
+    Copyright (c) Pierrick Dartois 2025.
+    """
+    Fp = a.parent()
+    p = Fp.characteristic()
+
+    return a**((p+1)//4)
-- 
cgit v1.2.3-70-g09d2