# Changes in [1294:fd82c524f715:1295:2b7e2be9a808]

Ignore:
Files:
9 edited

Unmodified
Removed
• ## sage/functions/constants.py

 r1097 return R.pi() def _real_double_(self): return sage.rings.all.RD.pi() def __abs__(self): if self.str()[0] != '-': return Integer(2) def _real_double_(self): return sage.rings.all.RD.e() # This just gives a string in singular anyways, and it's # *REALLY* slow! def _mpfr_(self,R): return R('NaN') #??? nan in mpfr: void mpfr_set_nan (mpfr_t x) def _real_double_(self): return sage.rings.all.RD.nan() NaN = NotANumber() def __float__(self): return float(0.5)*(float(1.0)+math.sqrt(float(5.0))) def _real_double_(self): """ EXAMPLES: sage: RealDoubleField()(golden_ratio) 1.61803398874989484820458 """ return sage.rings.all.RDF(1.61803398874989484820458) def _mpfr_(self,R):  #is this OK for _mpfr_ ? return math.log(2) def _real_double_(self): """ EXAMPLES: sage: RealDoubleField()(log2) 0.69314718055994530941723212145817656808   # 64-bit """ return sage.rings.all.RD.log2() def _mpfr_(self,R): return R.log2() return R.euler_constant() def _real_double_(self): """ EXAMPLES: sage: RealDoubleField()(euler_gamma) 0.57721566490153287 """ return sage.rings.all.RD.euler() def floor(self): return Integer(0) def _mpfr_(self, R): return R.catalan_constant() def _real_double_(self): """ EXAMPLES: sage: RealDoubleField()(catalan) 0.91596559417721901 """ return sage.rings.all.RDF(0.91596559417721901505460351493252) def __float__(self): """ EXAMPLES: sage: float(catalan) 0.91596559417721901 """ return 0.91596559417721901505460351493252 def floor(self): raise NotImplementedError, "Khinchin's constant only available up to %s bits"%self.__bits def _real_double_(self): """ EXAMPLES: sage: RealDoubleField()(khinchin) 2.6854520010653064453 """ return sage.rings.all.RDF(2.685452001065306445309714835481795693820) def __float__(self): return 2.685452001065306445309714835481795693820 raise NotImplementedError, "Twin Prime constant only available up to %s bits"%self.__bits def _real_double_(self): """ EXAMPLES: sage: RealDoubleField()(twinprime) 0.66016181584686962 """ return sage.rings.all.RDF(0.660161815846869573927812110014555778432) def __float__(self): """ raise NotImplementedError, "Merten's constant only available up to %s bits"%self.__bits def _real_double_(self): """ EXAMPLES: sage: RealDoubleField()(merten) 0.261497212847642783755426838608695859051 """ return sage.rings.all.RDF(0.261497212847642783755426838608695859051) def __float__(self): """ raise NotImplementedError, "Brun's constant only available up to %s bits"%self.__bits def _real_double_(self): """ EXAMPLES: sage: RealDoubleField()(brun) 1.9021605831040 """ return sage.rings.all.RDF(1.9021605831040) def __float__(self): """
• ## sage/rings/all.py

 r1271 Reals = RealField from real_double import RealDoubleField, RDF, RealDoubleElement # Complex numbers from complex_field import ComplexField, is_ComplexField, CC
• ## sage/rings/finite_field_element.py

 r924 Return a square root of this finite field element in its finite field, if there is one.  Otherwise, raise a ValueError. EXAMPLES: sage: F = GF(7^2) sage: F(2).square_root() 3 sage: F(3).square_root() 2*a + 6 sage: F(3).square_root()**2 3 sage: F(4).square_root() 2 sage: K = GF(7^3) sage: K(3).square_root() Traceback (most recent call last): ... ValueError: must be a perfect square. """ R = polynomial_ring.PolynomialRing(self.parent()) g = f.factor() if len(g) == 2 or g[0][1] == 2: return -g[0][0] return -g[0][0][0] raise ValueError, "must be a perfect square."
• ## sage/schemes/elliptic_curves/ell_finite_field.py

 r1097 from ell_field import EllipticCurve_field import sage.rings.ring as ring from sage.rings.all import Integer from sage.rings.all import Integer, PolynomialRing import gp_cremona import sea def __points_over_arbitrary_field(self): # TODO -- rewrite this insanely stupid implementation!! print "WARNING: Using very very stupid algorithm for finding points over" print "non-prime finite field.  Please rewrite.  See the file ell_finite.field.py." # The best way to rewrite is to extend Cremona's code (either gp or mwrank) so # it works over non-prime fields (should be easy), then generate up the group. # todo: This function used to have the following comment: ### TODO -- rewrite this insanely stupid implementation!! ### print "WARNING: Using very very stupid algorithm for finding points over" ### print "non-prime finite field.  Please rewrite.  See the file ell_finite.field.py." ### The best way to rewrite is to extend Cremona's code (either gp or mwrank) so ### it works over non-prime fields (should be easy), then generate up the group. # I changed the algorithm so that it's not as naive as it used to be. # But it's still surely far from optimal; I don't know anything about # point enumeration algorithms. -- David Harvey (2006-09-24) points = [self(0)] R = PolynomialRing(self.base_ring()) a1, a2, a3, a4, a6 = self.ainvs() for x in self.base_field(): for y in self.base_field(): try: points.append(self([x,y])) except TypeError: pass f = R([-(x**3 + a2*x**2 + a4*x + a6), (a1*x + a3), 1]) factors = f.factor() if len(factors) == 2 or factors[0][1] == 2: for factor in factors: points.append(self([x, -factor[0][0]])) return points All the points on this elliptic curve. If the base field is another other than $\FF_p$, this function currently uses a VERY VERY naive algorithm.   The problem is that Cremona's gp script \code{ell_zp.gp} currently only treats the case of prime fields. If you need more general functionality, please volunteer to implement it, either by extending \code{ell_zp.gp} (if you know PARI/GP well) or by writing new \sage code. EXAMPLES: sage: p = 5 sage: F = GF(p) sage: E = EllipticCurve(F, [1, 3]) sage: a_sub_p = E.change_ring(QQ).ap(p); a_sub_p 2 sage: len(E.points()) 4 sage: p + 1 - a_sub_p 4 sage: E.points() [(0 : 1 : 0), (4 : 1 : 1), (1 : 0 : 1), (4 : 4 : 1)] sage: K = GF(p**2) sage: E = E.change_ring(K) sage: len(E.points()) 32 sage: (p + 1)**2 - a_sub_p**2 32 sage: E.points() [(0 : 1 : 0), (0 : 2*a + 4 : 1), (0 : 3*a + 1 : 1), (1 : 0 : 1), (2 : 2*a + 4 : 1), (2 : 3*a + 1 : 1), (3 : 2*a + 4 : 1), (3 : 3*a + 1 : 1), (4 : 1 : 1), (4 : 4 : 1), (a : 1 : 1), (a : 4 : 1), (a + 2 : a + 1 : 1), (a + 2 : 4*a + 4 : 1), (a + 3 : a : 1), (a + 3 : 4*a : 1), (a + 4 : 0 : 1), (2*a : 2*a : 1), (2*a : 3*a : 1), (2*a + 4 : a + 1 : 1), (2*a + 4 : 4*a + 4 : 1), (3*a + 1 : a + 3 : 1), (3*a + 1 : 4*a + 2 : 1), (3*a + 2 : 2*a + 3 : 1), (3*a + 2 : 3*a + 2 : 1), (4*a : 0 : 1), (4*a + 1 : 1 : 1), (4*a + 1 : 4 : 1), (4*a + 3 : a + 3 : 1), (4*a + 3 : 4*a + 2 : 1), (4*a + 4 : a + 4 : 1), (4*a + 4 : 4*a + 1 : 1)] """ try: return q + 1 - self.cardinality() def cardinality(self, algorithm='heuristic', early_abort=False): def cardinality(self, algorithm='heuristic', early_abort=False, disable_warning=False): r""" Return the number of points on this elliptic curve over this \note{If the cardinality of the base field is not prime, this function currently uses a very very naive enumeration of all points.  It's so stupid, that it prints a warning.} function literally enumerates the points and counts them. It's so stupid, it prints a warning. You can disable the warning with the disable_warning flag.} INPUT: EXAMPLES: sage: EllipticCurve(GF(4),[1,2,3,4,5]).cardinality() WARNING: Using very very stupid algorithm for finding points over non-prime finite field.  Please rewrite.  See the file ell_finite.field.py. WARNING: Using very very stupid algorithm for counting points over non-prime finite field. Please rewrite. See the file ell_finite_field.py. 8 sage: EllipticCurve(GF(9),[1,2,3,4,5]).cardinality() WARNING: Using very very stupid algorithm for finding points over non-prime finite field.  Please rewrite.  See the file ell_finite.field.py. WARNING: Using very very stupid algorithm for counting points over non-prime finite field. Please rewrite. See the file ell_finite_field.py. 16 sage: EllipticCurve(GF(10007),[1,2,3,4,5]).cardinality() if N == 0: if not disable_warning: print "WARNING: Using very very stupid algorithm for counting " print "points over non-prime finite field. Please rewrite." print "See the file ell_finite_field.py." N = len(self.points()) self.__cardinality = Integer(N)
• ## sage/schemes/elliptic_curves/ell_generic.py

 r1169 def pseudo_torsion_polynomial(self, n, x=None, cache=None): r""" Returns the n-th torsion polynomial (division polynomial), without the 2-torsion factor if n is even, as a polynomial in $x$. These are the polynomials $g_n$ defined in Mazur/Tate (The p-adic sigma function''), but with the sign flipped for even $n$, so that the leading coefficient is always positive. The full torsion polynomials may be recovered as follows: \begin{itemize} \item $\psi_n = g_n$ for odd $n$. \item $\psi_n = (2y + a_1 x + a_3) g_n$ for even $n$. \end{itemize} Note that the $g_n$'s are always polynomials in $x$, whereas the $\psi_n$'s require the appearance of a $y$. SEE ALSO: -- torsion_polynomial() -- multiple_x_numerator() -- multiple_x_denominator() INPUT: n -- positive integer, or the special values -1 and -2 which mean $B_6 = (2y + a_1 x + a_3)^2$ and $B_6^2$ respectively (in the notation of Mazur/Tate). x -- optional ring element to use as the "x" variable. If x is None, then a new polynomial ring will be constructed over the base ring of the elliptic curve, and its generator will be used as x. Note that x does not need to be a generator of a polynomial ring; any ring element is ok. This permits fast calculation of the torsion polynomial *evaluated* on any element of a ring. cache -- optional dictionary, with integer keys. If the key m is in cache, then cache[m] is assumed to be the value of pseudo_torsion_polynomial(m) for the supplied x. New entries will be added to the cache as they are computed. ALGORITHM: -- Recursion described in Mazur/Tate. The recursive formulae are evaluated $O((log n)^2)$ times. TODO: -- for better unity of code, it might be good to make the regular torsion_polynomial() function use this as a subroutine. AUTHORS: -- David Harvey (2006-09-24) EXAMPLES: sage: E = EllipticCurve("37a") sage: E.pseudo_torsion_polynomial(1) 1 sage: E.pseudo_torsion_polynomial(2) 1 sage: E.pseudo_torsion_polynomial(3) 3*x^4 - 6*x^2 + 3*x - 1 sage: E.pseudo_torsion_polynomial(4) 2*x^6 - 10*x^4 + 10*x^3 - 10*x^2 + 2*x + 1 sage: E.pseudo_torsion_polynomial(5) 5*x^12 - 62*x^10 + 95*x^9 - 105*x^8 - 60*x^7 + 285*x^6 - 174*x^5 - 5*x^4 - 5*x^3 + 35*x^2 - 15*x + 2 sage: E.pseudo_torsion_polynomial(6) 3*x^16 - 72*x^14 + 168*x^13 - 364*x^12 + 1120*x^10 - 1144*x^9 + 300*x^8 - 540*x^7 + 1120*x^6 - 588*x^5 - 133*x^4 + 252*x^3 - 114*x^2 + 22*x - 1 sage: E.pseudo_torsion_polynomial(7) 7*x^24 - 308*x^22 + 986*x^21 - 2954*x^20 + 28*x^19 + 17171*x^18 - 23142*x^17 + 511*x^16 - 5012*x^15 + 43804*x^14 - 7140*x^13 - 96950*x^12 + 111356*x^11 - 19516*x^10 - 49707*x^9 + 40054*x^8 - 124*x^7 - 18382*x^6 + 13342*x^5 - 4816*x^4 + 1099*x^3 - 210*x^2 + 35*x - 3 sage: E.pseudo_torsion_polynomial(8) 4*x^30 - 292*x^28 + 1252*x^27 - 5436*x^26 + 2340*x^25 + 39834*x^24 - 79560*x^23 + 51432*x^22 - 142896*x^21 + 451596*x^20 - 212040*x^19 - 1005316*x^18 + 1726416*x^17 - 671160*x^16 - 954924*x^15 + 1119552*x^14 + 313308*x^13 - 1502818*x^12 + 1189908*x^11 - 160152*x^10 - 399176*x^9 + 386142*x^8 - 220128*x^7 + 99558*x^6 - 33528*x^5 + 6042*x^4 + 310*x^3 - 406*x^2 + 78*x - 5 sage: E.pseudo_torsion_polynomial(18) % E.pseudo_torsion_polynomial(6) == 0 True An example to illustrate the relationship with torsion points. sage: F = GF(11) sage: E = EllipticCurve(F, [0, 2]); E Elliptic Curve defined by y^2  = x^3 + 2 over Finite Field of size 11 sage: f = E.pseudo_torsion_polynomial(5); f 5*x^12 + x^9 + 8*x^6 + 4*x^3 + 7 sage: f.factor() (5) * (x^2 + 5) * (x^2 + 2*x + 5) * (x^2 + 5*x + 7) * (x^2 + 7*x + 7) * (x^2 + 9*x + 5) * (x^2 + 10*x + 7) This indicates that the x-coordinates of all the 5-torsion points of E are in GF(11^2), and therefore the y-coordinates are in GF(11^4). sage: K = GF(11^4) sage: X = E.change_ring(K) sage: f = X.pseudo_torsion_polynomial(5) sage: x_coords = [root for (root, _) in f.roots()]; x_coords [a^3 + 7*a^2 + 6*a, 2*a^3 + 3*a^2 + a + 7, 3*a^3 + 10*a^2 + 7*a + 1, 3*a^3 + 10*a^2 + 7*a + 3, 3*a^3 + 10*a^2 + 7*a + 8, 5*a^3 + 2*a^2 + 8*a + 7, 6*a^3 + 9*a^2 + 3*a + 4, 8*a^3 + a^2 + 4*a + 4, 8*a^3 + a^2 + 4*a + 8, 8*a^3 + a^2 + 4*a + 10, 9*a^3 + 8*a^2 + 10*a + 8, 10*a^3 + 4*a^2 + 5*a + 6] Now we check that these are exactly the x coordinates of the 5-torsion points of E. sage: for x in x_coords: ...       y = (x**3 + 2).square_root() ...       P = X([x, y]) ...       assert P.order(disable_warning=True) == 5 todo: need to show an example where the 2-torsion is missing """ if cache is None: cache = {} else: try: return cache[n] except KeyError: pass if x is None: x = rings.PolynomialRing(self.base_ring()).gen() b2, b4, b6, b8 = self.b_invariants() n = int(n) if n <= 4: if n == -1: answer = 4*x**3 + b2*x**2 + 2*b4*x + b6 elif n == -2: answer = self.pseudo_torsion_polynomial(-1, x, cache) ** 2 elif n == 1 or n == 2: answer = x.parent()(1) elif n == 3: answer = 3*x**4 + b2*x**3 + 3*b4*x**2 + 3*b6*x + b8 elif n == 4: answer = -self.pseudo_torsion_polynomial(-2, x, cache) + \ (6*x**2 + b2*x + b4) * \ self.pseudo_torsion_polynomial(3, x, cache) else: raise ValueError, "n must be a positive integer (or -1 or -2)" else: if n % 2 == 0: m = (n-2) // 2 g_mplus3 = self.pseudo_torsion_polynomial(m+3, x, cache) g_mplus2 = self.pseudo_torsion_polynomial(m+2, x, cache) g_mplus1 = self.pseudo_torsion_polynomial(m+1, x, cache) g_m      = self.pseudo_torsion_polynomial(m,   x, cache) g_mless1 = self.pseudo_torsion_polynomial(m-1, x, cache) answer = g_mplus1 * \ (g_mplus3 * g_m**2 - g_mless1 * g_mplus2**2) else: m = (n-1) // 2 g_mplus2 = self.pseudo_torsion_polynomial(m+2, x, cache) g_mplus1 = self.pseudo_torsion_polynomial(m+1, x, cache) g_m      = self.pseudo_torsion_polynomial(m,   x, cache) g_mless1 = self.pseudo_torsion_polynomial(m-1, x, cache) B6_sqr   = self.pseudo_torsion_polynomial(-2, x, cache) if m % 2 == 0: answer = B6_sqr * g_mplus2 * g_m**3 - \ g_mless1 * g_mplus1**3 else: answer = g_mplus2 * g_m**3 - \ B6_sqr * g_mless1 * g_mplus1**3 cache[n] = answer return answer def multiple_x_numerator(self, n, x=None, cache=None): r""" Returns the numerator of the x-coordinate of the nth multiple of a point, using torsion polynomials (division polynomials). The inputs n, x, cache are as described in pseudo_torsion_polynomial(). The result is adjusted to be correct for both even and odd n. WARNING: -- There may of course be cancellation between the numerator and the denominator (multiple_x_denominator()). Be careful. For more information on how to avoid cancellation, see Christopher Wuthrich's thesis. SEE ALSO: -- multiple_x_denominator() AUTHORS: -- David Harvey (2006-09-24) EXAMPLES: sage: E = EllipticCurve("37a") sage: P = E.gens()[0] sage: x = P[0] sage: (35*P)[0] -804287518035141565236193151/1063198259901027900600665796 sage: E.multiple_x_numerator(35, x) -804287518035141565236193151 sage: E.multiple_x_denominator(35, x) 1063198259901027900600665796 sage: (36*P)[0] 54202648602164057575419038802/15402543997324146892198790401 sage: E.multiple_x_numerator(36, x) 54202648602164057575419038802 sage: E.multiple_x_denominator(36, x) 15402543997324146892198790401 An example where cancellation occurs: sage: E = EllipticCurve("88a1") sage: P = E.gens()[0] sage: n = E.multiple_x_numerator(11, P[0]); n 442446784738847563128068650529343492278651453440 sage: d = E.multiple_x_denominator(11, P[0]); d 1427247692705959881058285969449495136382746624 sage: n/d 310 sage: 11*P (310 : -5458 : 1) """ if cache is None: cache = {} if x is None: x = rings.PolynomialRing(self.base_ring()).gen() n = int(n) if n < 2: print "n must be at least 2" self.pseudo_torsion_polynomial( -2, x, cache) self.pseudo_torsion_polynomial(n-1, x, cache) self.pseudo_torsion_polynomial(n  , x, cache) self.pseudo_torsion_polynomial(n+1, x, cache) if n % 2 == 0: return x * cache[-1] * cache[n]**2 - cache[n-1] * cache[n+1] else: return x * cache[n]**2 - cache[-1] * cache[n-1] * cache[n+1] def multiple_x_denominator(self, n, x=None, cache=None): r""" Returns the denominator of the x-coordinate of the nth multiple of a point, using torsion polynomials (division polynomials). The inputs n, x, cache are as described in pseudo_torsion_polynomial(). The result is adjusted to be correct for both even and odd n. SEE ALSO: -- multiple_x_numerator() TODO: the numerator and denominator versions share a calculation, namely squaring $\psi_n$. Maybe would be good to offer a combined version to make this more efficient. EXAMPLES: -- see multiple_x_numerator() AUTHORS: -- David Harvey (2006-09-24) """ if cache is None: cache = {} if x is None: x = rings.PolynomialRing(self.base_ring()).gen() n = int(n) if n < 2: print "n must be at least 2" self.pseudo_torsion_polynomial(-2, x, cache) self.pseudo_torsion_polynomial(n , x, cache) if n % 2 == 0: return cache[-1] * cache[n]**2 else: return cache[n]**2 def torsion_polynomial(self, n, i=0): """ Polynomial -- n-th torsion polynomial, which is a polynomial over the base field of the elliptic curve. SEE ALSO: pseudo_torsion_polynomial() EXAMPLES:
• ## sage/schemes/elliptic_curves/ell_point.py

 r1097 class EllipticCurvePoint_finite_field(EllipticCurvePoint_field): def order(self): def order(self, disable_warning=False): """ Return the order of this point on the elliptic curve. self.__order = rings.Integer(e.ellzppointorder(list(self.xy()))) else: print "WARNING -- using naive point order finding over finite field!" if not disable_warning: print "WARNING -- using naive point order finding over finite field!" # TODO: This is very very naive!!  -- should use baby-step giant step; maybe in mwrank #      note that this is *not* implemented in PARI!
• ## sage/server/notebook/notebook.py

 r1184 import shutil import socket import re           # regular expressions # SAGE libraries os.system(cmd) D = os.listdir(tmp)[0] worksheet = load('%s/%s/%s.sobj'%(tmp,D,D), compress=False) names = self.worksheet_names() if D in names: m = re.match('.*?([0-9]+)\$',D) if m is None: n = 0 else: n = int(m.groups()[0]) while "%s%d"%(D,n) in names: n += 1 cmd = 'mv %s/%s/%s.sobj %s/%s/%s%d.sobj'%(tmp,D,D,tmp,D,D,n) print cmd os.system(cmd) cmd = 'mv %s/%s %s/%s%d'%(tmp,D,tmp,D,n) print cmd os.system(cmd) D = "%s%d"%(D,n) worksheet.set_name(D) print D worksheet = load('%s/%s/%s.sobj'%(tmp,D,D), compress=False) S = self.__worksheet_dir cmd = 'rm -rf "%s/%s"'%(S,D) jsmath      = True, show_debug  = False, warn        = True): warn        = True, ignore_lock = False): r""" Start a SAGE notebook web server at the given port. if not (os.path.exists('%s/nb.sobj'%dir) or os.path.exists('%s/nb-backup.sobj'%dir)): raise RuntimeError, '"%s" is not a valid SAGE notebook directory (missing nb.sobj).'%dir if os.path.exists('%s/pid'%dir) and not ignore_lock: f = file('%s/pid'%dir) p = f.read() f.close() try: #This is a hack to check whether or not the process is running. os.kill(int(p),0) print "\n".join([" This notebook appears to be running with PID %s.  If it is"%p, " not responding, you will need to kill that process to continue.", " If another (non-sage) process is running with that PID, call", " notebook(..., ignore_lock = True, ...). " ]) return except OSError: pass f = file('%s/pid'%dir, 'w') f.write("%d"%os.getpid()) f.close() try: nb = load('%s/nb.sobj'%dir, compress=False) from sage.misc.misc import delete_tmpfiles delete_tmpfiles() os.remove('%s/pid'%dir) return nb
• ## sage/server/notebook/worksheet.py

 r1184 import traceback import time import crypt import pexpect self.__name = name self.__notebook = notebook self.__passcode = passcode self.__passcode = crypt.crypt(passcode, self.__salt) self.__passcrypt= True dir = list(name) for i in range(len(dir)): C.set_worksheet(self) def salt(self): try: return self.__salt except AttributeError: self.__salt = "%f"%time.time() return self.__salt def passcode(self): try: c = self.__passcrypt except AttributeError: self.__passcrypt = False try: if not self.__passcrypt: self.__passcode = crypt.crypt(self.__passcode, self.salt()) self.__passcrypt = True return self.__passcode except AttributeError: self.__passcode = '' return '' self.__passcode = crypt.crypt(self.__passcode, self.salt()) self.__passcrypt = True return self.__passcode def filename(self): def auth(self, passcode): if self.passcode() == '': return True else: return self.passcode() == passcode return self.passcode() == crypt.crypt(passcode, self.__salt) def _strip_synchro_from_start_of_output(self, s): return self.__name def set_name(self, name): self.__name = name def append(self, L): self.__cells.append(L)
• ## setup.py

 r1292 libraries = ['gsl', CBLAS]) real_double = Extension('sage.rings.real_double', ['sage/rings/real_double.pyx'], libraries = ['gsl', CBLAS]) complex_double = Extension('sage.rings.complex_double', ['sage/rings/complex_double.pyx'], gsl_interpolation, gsl_callback, real_double, complex_double,
Note: See TracChangeset for help on using the changeset viewer.