Shared2017-12-01-102525.sagewsOpen in CoCalc
Author: Oswaldo Velásquez Castañón
Views : 4
# Método de Schoof
# La curva elíptica E está en forma de Weierstrass y^2=f(x)=x^3+Ax+B divpoly_factor = 0 # vaariable global para factor del polinomio de división cuando ocurre ZeroDivisionError # Elementos de End(E[ell]) son representados como pares (a,b*y), con a,b in Fp[x]/(h(x)), donde h es el divpoly (polinomio de división) ell-ésimo (o un factor de él) # El factor y es implícito, pero debe tenerse en cuenta cuando se aplica la ley de grupo -- usndo la ecuación de curva y^2=f(x) reemplazamos y^2 con f(x) donde aparezca # En muchas de las funciones abajo pasamos tanto A como f # donde f es la imagen de x^3+Ax+B en Fp[x]/(h(x)) -- necesitamos ambos ya que si deg(h)<= 3 no podemos recuperar A de (x^3+Ax+B) mod h(x) def add(P,Q,A,f): """sumar endomorfismos P y Q en End(E[ell])""" global divpoly_factor if not P: return Q if not Q: return P a1 = P[0]; b1 = P[1]; a2=Q[0]; b2=Q[1] if a1 == a2: if b1 == b2: return dbl(P,A,f) else: return () try: m = (b2-b1)/(a2-a1) except ZeroDivisionError: ### como a2-a1 está reducido mod h, ZeroDivisionError significa que gcd(a2-a1,h) debe ser un factor no trivial g de h ### esto da un error, para que podamos reiniciar el algoritmo trabajando en un anillo cociente más pequeño divpoly_factor = a2-a1 raise a3 = f*m^2 -a1 - a2 b3 = m*(a1-a3) - b1 return (a3,b3) def dbl(P,A,f): """doblar el endomorfismo P en End(E[ell]) """ global divpoly_factor if not P: return P a1 = P[0]; b1 = P[1] try: m = (3*a1^2+A) / (2*b1*f) except ZeroDivisionError: divpoly_factor = 2*b1*f raise a3 = f*m^2 - 2*a1 b3 = m*(a1-a3) - b1 return (a3,b3) def neg(P): """ negar el endomorfismo P en End(E[ell]) """ if not P: return P return (P[0],-P[1]) def smul (n,P,A,f): """ calcular el múltiplo escalar n*P en End(E[ell]) usando dbl y add""" if not n: return () nbits = n.digits(2) i = len(nbits)-2 Q = P while i >= 0: Q = dbl(Q,A,f) if nbits[i]: Q = add(P,Q,A,f) i -= 1 return Q def mul (P,Q): """ calcular el producto (i.e. composición de) P*Q de dos endomorfismos en End(E[ell]) """ return (P[0].lift()(Q[0]),P[1].lift()(Q[0])*Q[1]) def trace_mod (E, ell): """ calcular la traza de Frobenius (el entero 'l') de E módulo ell """ FF=E.base_ring() q = FF.cardinality() # cuerpo finito FF_q R.<t>=PolynomialRing(FF) A=E.a4(); B=E.a6() # E: y^2 = x^3 + Ax + B if ell == 2: # t is impar si y solo si f es irreducible if (t^3+A*t+B).is_irreducible(): return 1 else: return 0 h = E.division_polynomial(ell,t,0).monic() while true: try: RR.<x> = R.quotient(ideal(h)) # RR es End(E[ell]) (o un subanillo) f = x^3+A*x+B xq = x^q; yq = f^((q-1)/2) pi = (xq,yq) # pi es el endomorfismo de Frobenius pi2 = mul(pi,pi) # pi2 = pi^2 id = (x,RR(1)) # identidad, esto es el mapeo de multiplicación por 1 Q = smul(q%ell,id,A,f) # Q es el mapeo de multiplicación por q S = add(pi2,Q,A,f) # S = pi^2 + q = t*pi if not S: return 0 # si S=0 entonces t=0 if S == pi: return 1 # si S=pi entonces t=1 if neg(S) == pi: return -1 # si S=-pi entonces t=-1 P = pi for t in range(2,ell-1): P = add(P,pi,A,f) # P = t*pi if P==S: return t # si S=P entonces encontramos t print "Error, Frob no cumple charpoly!!" assert false except ZeroDivisionError: h = gcd(h,divpoly_factor.lift()) # si alcanzamos un divisor de cero, reiniciamos con un nuevo h print "Encontrado %d-divpoly factor de grado %d"%(ell,h.degree()) def Schoof(E): """ Calcular la traza de Frobenius de E usando el algoritmo de Schoof """ q=E.base_ring().cardinality() t = 0; M=1; ell=1; while M <= 4*sqrt(q): ell = next_prime(ell) start = cputime() tell = trace_mod(E,ell) print "Traza %d mod %d calculada en %.2f segundos"%(tell,ell,cputime()-start) a = M*M.inverse_mod(ell); b = ell*ell.inverse_mod(M) M *= ell t = (a*tell+b*t) % M if t >= M/2: return t-M else: return t
%time FF=GF(next_prime(2^80)) E=EllipticCurve([FF(314159),FF(2781828)]) t=Schoof(E) print t,E.trace_of_frobenius()
Traza 1 mod 2 calculada en 0.01 segundos Traza -1 mod 3 calculada en 0.04 segundos Traza 0 mod 5 calculada en 0.03 segundos Traza 2 mod 7 calculada en 0.04 segundos Traza 7 mod 11 calculada en 0.18 segundos Encontrado 13-divpoly factor de grado 6 Traza 6 mod 13 calculada en 0.27 segundos Traza 15 mod 17 calculada en 0.92 segundos Traza 1 mod 19 calculada en 0.94 segundos Traza 8 mod 23 calculada en 2.58 segundos Traza 22 mod 29 calculada en 10.14 segundos Traza 13 mod 31 calculada en 12.83 segundos Traza 17 mod 37 calculada en 38.30 segundos -1315484487805 -1315484487805 CPU time: 66.43 s, Wall time: 69.42 s
next_prime(2^80)+1-t
1208925819615944659193995
F=EllipticCurve([0,-1,1,-10,-20]) F.torsion_points()
[(0 : 1 : 0), (5 : -6 : 1), (5 : 5 : 1), (16 : -61 : 1), (16 : 60 : 1)]
t11= 1/2+2*q+2*q^2+4*q^3+10*q^4+8*q^5+16*q^6+8q^7+18*q^8+14*q^9+O(q^10) t12=1/2+6*q^2+6*q^3+6*q^4+6*q^5+12*q^6+12*q^7+18*q^8+18*q^9+O(q^10) t22=1/2+3*q+3*q^3+12*q^4+9*q^5+18*q^6+6*q^7+18*q^8+12*q^9+O(q^10) E0=1/2*t11+1/3*t12 E0
606fe807-feff-4cc0-8889-28de2c9b05fas t11= 1/2+2*q+2*q^2+4*q^3+10*q^4+8*q^5+16*q^6+8q^7+18*q^8+14*q^9+O(q^10) t12=1/2+6*q^2+6*q^3+6*q^4+6*q^5+12*q^6+12*q^7+18*q^8+18*q^9+O(q^10) t22=1/2+3*q+3*q^3+12*q^4+9*q^5+18*q^6+6*q^7+18*q^8+12*q^9+O(q^10) E0=1/2*t11+1/3*t12 E0