Changeset 7673:a5be33abd723

Timestamp:

11/08/07 08:57:43 (6 years ago)

Author:

Martin Albrecht <malb@…>

Branch:

default

Message:

EllipticCurve?(GF(2^{n),...).random element() works now}

Location:

sage

Files:

• rings/finite_field.py (modified) (2 diffs)
• schemes/elliptic_curves/ell_finite_field.py (modified) (3 diffs)
• schemes/hyperelliptic_curves/hyperelliptic_finite_field.py (modified) (2 diffs)

sage/rings/finite_field.py

@@ -193 +193 @@
         if name is None:
             raise TypeError, "you must specify the generator name"
-        if order < 2**16:  
+        if order < zech_log_bound:  
             # DO *NOT* use for prime subfield, since that would lead to
             # a circular reference in the call to ParentWithGens in the
@@ -437 +437 @@
         """
         return 1
+
+zech_log_bound = 2**16

sage/schemes/elliptic_curves/ell_finite_field.py

@@ -185 +185 @@
             sage: type(P)
             <class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
+            sage: P in E
+            True
 
             sage: k.<a> = GF(7^5)
@@ -191 +193 @@
             sage: type(P)
             <class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
+            sage: P in E
+            True
+
+            sage: k.<a> = GF(2^5)
+            sage: E = EllipticCurve(k,[a^2,a,1,a+1,1])
+            sage: P = E.random_element()
+            sage: type(P)
+            <class 'sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field'>
+            sage: P in E
+            True
 
         """
@@ -197 +209 @@
             return self(0)
         a1, a2, a3, a4, a6 = self.ainvs()
-        while True:
-            x = k.random_element()
-            d = 4*x**3 + (a1**2 + 4*a2)*x**2 + (2*a3*a1 + 4*a4)*x + (a3**2 + 4*a6)
-            try:
-                m = d.sqrt(extend=False)
-                y = (-(a1*x + a3) + m) / k(2)
+
+        if k.characteristic() == 2:
+            P = PolynomialRing(k,'y')
+            y = P.gen()
+            while True:
+                x = k.random_element()
+                f = y**2 + a1*x*y + a3*y - x**3 + a2*x**2 + a4*x + a6
+                roots = f.roots()
+                if roots == []:
+                    continue
+                if random.random() < 0.5:
+                    y = roots[0][0]
+                else:
+                    y = roots[1][0]
                 return self([x,y])
-            except ValueError:
-                pass
+        else:
+            while True:
+                x = k.random_element()
+                d = 4*x**3 + (a1**2 + 4*a2)*x**2 + (2*a3*a1 + 4*a4)*x + (a3**2 + 4*a6)
+                try:
+                    m = d.sqrt(extend=False)
+                    y = (-(a1*x + a3) + m) / k(2)
+                    return self([x,y])
+                except ValueError:
+                    pass
 
     def trace_of_frobenius(self):

sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py

@@ -179 +179 @@
             122
         """
+        from sage.rings.finite_field import zech_log_bound
         try:
             return self.__points
@@ -186 +187 @@
             self.__points = self._points_cache_sqrt()
         else:
-            self.__points = self._points_fast_sqrt()
+            if self.base_ring().order() < zech_log_bound:
+                self.__points = self._points_fast_sqrt() # this is fast using Zech logarithms
+            else:
+                self.__points = self._points_cache_sqrt()
             
         return self.__points