Initial Commit

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>

1 files changed, 163 insertions, 0 deletions

diff --git a/uv_params.py b/uv_params.py
new file mode 100644
index 0000000..c651347
--- /dev/null
+++ b/uv_params.py
@@ -0,0 +1,163 @@
+from sage.all import *
+
+import coin
+import const_precomp
+
+class UV_params:
+    """
+    Parameter set for running the algorithm and finding solutions to the coin
+    equation. By default, takes as input the securty level
+    (500|1000|1500|2000|4000) and proceed to setup the predefined parameters
+    for such level. Optionally, different parameters can be provided as a
+    dictionary.
+
+    Parameters:
+    - p: the underlying prime
+    - O: them maximal order Z[(pi + 1)/2]
+    - uv_e: the 2-torsion available for solving the norm equation; by default
+      is v_2(p+1) - 2;
+    - spr: precomputed rounded square root of p;
+    - allowed_primes: small elkies primes that can be removed from the norm
+      equation and computed separately; a different (heuristically) optimal set
+      is available for each level; to update the list, and all the associated
+      parameters, use the functions `set_allowed_primes` and
+      `add_allowed_prime` described below;
+    - allowed_primes_prod: the product of all allowed_primes;
+    - sos_allowed_primes: primes that can be removed from the sum of squares
+      step; consists of the primes 3 mod 4 in allowed_primes;
+    - norm_bound: scaling factor used to bound the norms of the short vectors
+      sampled from the ideal lattice; only vectors with norm smaller than
+      norm_bound*spr are considered;
+    - norm_cff_bound: short vectors are computed as linear combinations of an
+      LLL basis; this value bound the coefficients of the combinations; by
+      default is the (rounded) square root of norm_bound;
+    - comb_bound: the number of short vectors that are combined to try to find
+      a solution to the coin equation; by default is 10, meaning 100
+      combinations are tried;
+    - n_squares: how many between u and v must be sums of squares; default 2;
+    - sol_bound: how many solutions to try before returning the best one found;
+      default 1;
+
+    Methods:
+    - set_allowed_primes(ls): takes in input a list `ls` and set
+      `self.allowed_primes` to the Elkies primes contained in `ls`; updates the
+      related parameters accordingly;
+    - add_allowed_prime(ell): if the given prime `ell` is Elkies, it is added
+      to `self.allowed_primes` and the function returns True; otherwise, it
+      returns False.
+    """
+
+    def __init__(self, level, params=None):
+        level = int(level)
+        if level == 500:
+            self.init_500()
+        elif level == 1000:
+            self.init_1000()
+        elif level == 1500:
+            self.init_1500()
+        elif level == 2000:
+            self.init_2000()
+        elif level == 4000:
+            self.init_4000()
+        else:
+            raise ValueError('unknown level')
+
+        # Arithmetic
+        self.Fp = GF(self.p)
+        self.Fp2 = GF((self.p, 2), name='i', modulus=var('x')**2 + 1)
+        self.K = NumberField(name="pi", polynomial = var('x')**2 + self.p)
+        self.w = self.K.gens()[0]
+        self.max_order = self.K.maximal_order()
+        self.order = self.K.order_of_conductor(2)
+
+        # Starting curve
+        E_start = EllipticCurve(self.Fp, [0, self.A, 0, 1, 0])
+        self.E_start = E_start
+
+        # UV parameters
+        self.uv_e = self.e - 3
+        self.spr = isqrt(self.p)
+        p_3mod4 = list(filter(lambda x: x%4 == 3, self.allowed_primes))
+        self.sos_allowed_primes = p_3mod4
+        self.allowed_primes_prod = prod(self.allowed_primes)
+        self.norm_bound = ZZ(self.p).nbits()
+        self.norm_cff_bound = isqrt(self.norm_bound) + 1
+        self.comb_bound = 10
+        self.n_squares = 2
+        self.sol_bound = 1
+
+        # Optional parameter update
+        if params:
+            for p_key, p_val in params.items():
+                setattr(self,p_key,p_value)
+
+    def init_500(self):
+        self.f = 33
+        self.e = 503
+        self.p = self.f * 2**self.e - 1
+        self.A = 846923981206860774667188923127927404866138431504857441785556155002892474407686465068998563030997400041497236660113832719116298437902864009587446028542241
+        allowed_primes = [3, 7, 11, 13]
+        self.allowed_primes = [ZZ(li) for li in allowed_primes]
+
+    def init_1000(self):
+        self.f = 15
+        self.e = 1004
+        self.p = self.f * 2**self.e - 1
+        self.A = 2447932165031884901753526747235802754200581132492013990029309589916334680445261935406178846882142279733036010435356728900482083533977052489550706097041090570437350041707592382243329641233414772511433265807801169694848478362818691704488235495552842938554477902999119670514198118427921959251521459174283757
+        allowed_primes = [3, 5, 7, 11]
+        self.allowed_primes = [ZZ(li) for li in allowed_primes]
+
+    def init_1500(self):
+        self.f = 9
+        self.e = 1551
+        self.p = self.f * 2**self.e - 1
+        self.A = 470690138325573302381284028925922066259197385545434613961546293117200415888454393210985745811672527707750649809464293986828934656433695254827553343115710988038803620829829607213986283428022502352610750230825225753910990410861379903133396479857538580518638524776922388484859923418301448669856130467309798601801912903218678382572894516230515348525582714674329329665444893417613957336453258663721257841338989369604936267692408989319582217755257612152597484632197929506422
+        allowed_primes = [3, 5, 11]
+        self.allowed_primes = [ZZ(li) for li in allowed_primes]
+        coin.good_prime_prod = const_precomp.good_prime_prod_100k
+        coin.bad_prime_prod = const_precomp.bad_prime_prod_100k
+
+    def init_2000(self):
+        self.f = 51
+        self.e = 2026
+        self.p = self.f * 2**self.e - 1
+        self.A = 81522175295034447595829362752089781064926402323585792843903881571299469475765731013589255502541646344652265632612080053850583985808199619939412577427961666539089410884159333672468730652939947531656027845338622561223839271607859219023997914401035458486761172816051586319123853202351034903432110329760972693423592535540529210197485000054794934251253577983683962395651835481200021277459090885409493264948676810331609354889543129654381859017748250839312739412603528665722325984598111481835819726605526313101275796618189346971789271155935744998546622047982841689962568590619138079006213242588187631607235805859652542
+        allowed_primes = [3, 7, 11, 17]
+        self.allowed_primes = [ZZ(li) for li in allowed_primes]
+        coin.good_prime_prod = const_precomp.good_prime_prod_100k
+        coin.bad_prime_prod = const_precomp.bad_prime_prod_100k
+
+    def init_4000(self):
+        self.f = 63
+        self.e = 4084
+        self.p = self.f * 2**self.e - 1
+        self.A = 3861182440791393427115834319919792363082397953235366672989642232032664601358637530587592475724492228157994152478762370779212684014665350275282740708992301403517860204937961301178353993394123923639955895951016030909047562464435151058330155507538738419078593938731652956043256633693827720453080631845604091259290706126622597714437085574776283248730437225629704782127771641525437187101408298218133833634726212421345805005641803578982727095077266614175977073363364911048284637511496334424899430835066269145012363608931646817082193451123867313226197275905378376442493746564842029440001132446848573232704980649005361798250530086069725335482701101306335776380418104681645935311890062938192551774656426376713685296742945987418112888455314815190689399358568871101254106213839110567602195750401800211431397684678743127540890669195457658925252532743828619079040054116684464335116945294570022631103926522225020600966809347462518428416543333615647560326220108209234883366833121125898408957117320377370772129934485893908787438550276617471673661822552984223791369029779538709395655155777458500406072451055588404055831790775259870437154343571081246432780811947116682159194253450328736841478964648801067542070339026439293541698676665959781451048203
+        allowed_primes = [3, 7, 11, 17, 19]
+        self.allowed_primes = [ZZ(li) for li in allowed_primes]
+        coin.good_prime_prod = const_precomp.good_prime_prod_100k
+        coin.bad_prime_prod = const_precomp.bad_prime_prod_100k
+
+    def set_allowed_primes(self, allowed_primes):
+        """
+        Set the list of allowed primes to a given list by filtering non-Elkies
+        primes, and update parameters accordingly.
+        """
+        self.allowed_primes = list(filter(
+            lambda ell: kronecker(-self.p, ell) == 1, allowed_primes))
+        self.allowed_primes_prod = prod(self.allowed_primes)
+        p_3mod4 = list(filter(lambda x: x%4 == 3, self.allowed_primes))
+        self.sos_allowed_primes = p_3mod4
+
+    def add_allowed_prime(self, ell):
+        """
+        Check if ell is an elkies prime; if so, add it to the list of allowed
+        primes, update the related parameters accordingly, and return True;
+        otherwise, return False.
+        """
+        if ell in self.allowed_primes or kronecker(-self.p, ell) != 1:
+            return False
+        self.allowed_primes.append(ell)
+        self.allowed_primes_prod *= ell
+        if ell%4 == 3:
+            self.sos_allowed_primes.append(ell)
+        return True