# New Cocks-Pinch curves with rho = 2 but optimal ate pairing available. # j = 0 import sage from exceptions import ValueError from sage.functions.log import log from sage.functions.other import ceil from sage.functions.other import sqrt from sage.arith.misc import XGCD, xgcd from sage.rings.integer import Integer from sage.rings.finite_rings.finite_field_constructor import FiniteField from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing from sage.schemes.elliptic_curves.ell_finite_field import EllipticCurve_finite_field from sage.schemes.elliptic_curves.constructor import EllipticCurve import PairingFriendlyCurve from PairingFriendlyCurve import get_curve_parameter_b_j0, get_curve_generator_order_r_j0 from PairingFriendlyCurve import print_parameters, print_parameters_for_RELIC class CocksPinch6(EllipticCurve_finite_field): """ A Cocks-Pinch curve of embedding degree k=6, D=3, rho=2 and optimal ate pairing available. """ def __init__(self, u, hy, sign_y0=None, ht=None, exp_tr=None, p=None, r=None, c=None, tr=None, y=None, b=None, beta=None, lamb=None): """ :param u: seed :param hy : integer such that y = y0 + hy*r :param ht : integer such that tr = tr0 + ht*r :param exp_tr: integer such that tr = u^exp_tr + 1 mod r :param b : curve parameter in E: y^2 = x^3 + b :param p : prime, field characteristic :param r : prime, divides the curve order :param c : cofactor such that r*c = (p+1-tr), the curve order :param tr : trace of the curve :param y : integer s.t. p = (tr^2 + D*y^2)/4 :param beta : integer s.t. beta^2+beta+1 = 0 mod p :param lamb : integer s.t. lamb^2+lamb+1 = 0 mod r """ hy = Integer(hy) if ht != None: ht = Integer(ht) else: ht = Integer(0) #T = Integer(u) self._k = 6 # embedding degree self._D = 3 # curve discriminant self._a = 0 self._u = Integer(u) self._hy = hy self._ht = ht if exp_tr == None: self._i = 1 else: self._i = exp_tr # see bottom of file for formulas self.polynomial_r = [1, -1, 1] # u^2-u+1 self.polynomial_tr_denom = Integer(1) self.polynomial_y_denom = Integer(3) self.polynomial_p_denom = Integer(12) self.polynomial_c_denom = Integer(12) self.polynomial_lamb = [Integer(0), Integer(-1)] self.polynomial_lamb_denom = Integer(1) if self._i == 1 and (self._u % 3) == 0: self.polynomial_tr = [1+ht, 1-ht, ht] #tr = T + 1 +h_t*r if sign_y0 == None: sign_y0 = -1 if sign_y0 == 1: #malediction, encore -y0 au lieu de y0 self.polynomial_y = [3*hy, -3*hy-2, 3*hy+1] #y = (T^2-2*T)//3 +h_y*r self.polynomial_p = [3*(ht+1)**2+9*hy**2, -6*(ht**2+3*hy**2+2*hy-1), (9*ht**2+27*hy**2+18*hy+7), -2*(3*ht**2-3*ht+9*hy**2+9*hy+2), 3*ht**2+(3*hy+1)**2] #self.polynomial_p= [3*(ht+1)**2+9*hy**2, -6*ht**2-18*hy**2+12*hy+6, 9*ht**2+27*hy**2-18*hy+7, -6*ht**2-18*hy**2+6*ht+18*hy-4, 3*ht**2+9*hy**2-6*hy+1] self.polynomial_c = [3*(3*hy**2+(ht+1)**2), -3*((ht-1)**2+hy*(3*hy+4)), (3*hy+1)**2+3*ht**2] self.polynomial_beta = [6*(ht**2+3*hy**2-1), -((3*ht-1)**2+27*hy**2+24*hy+8), ((3*ht-1)**2+(9*hy+2)*(3*hy+2)), -(3*ht**2+(3*hy+1)**2)] self.polynomial_beta_denom = 6*(ht+3*hy+1) else: # default case in CocksPinchVariant self.polynomial_y = [3*hy, -3*hy+2, 3*hy-1] #y = -(T^2-2*T)//3 +h_y*r self.polynomial_p = [3*(ht+1)**2+9*hy**2, -6*(ht**2+3*hy**2-2*hy-1), (9*ht**2+27*hy**2-18*hy+7), -2*(3*ht**2+9*hy**2-3*ht-9*hy+2), 3*ht**2+(3*hy-1)**2] self.polynomial_c = [3*ht**2-6*ht+3+9*hy**2, -3*ht**2-9*hy**2+6*ht+12*hy-3, 3*ht**2+9*hy**2-6*hy+1] self.polynomial_beta = [ -6*ht**2-6*ht-18*hy**2+18*hy, (3*ht-1)**2+27*hy**2-24*hy+8, -(3*ht-1)**2 -27*hy**2+24*hy-4, 3*ht**2+9*hy**2-6*hy+1] self.polynomial_beta_denom = 6*(ht-3*hy+1) #(3*h_t^2 + 9*h_y^2 - 6*h_y + 1)*T^3 + (-9*h_t^2 + 6*h_t - 27*h_y^2 + 24*h_y - 5)*T^2 + (9*h_t^2 - 6*h_t + 27*h_y^2 - 24*h_y + 9)*T - 6*h_t^2 - 6*h_t - 18*h_y^2 + 18*h_y #(-3*h_t^2 - 9*h_y^2 + 6*h_y - 1)*T^3 + (9*h_t^2 - 6*h_t + 27*h_y^2 - 24*h_y + 5)*T^2 + (-9*h_t^2 + 6*h_t - 27*h_y^2 + 24*h_y - 9)*T + 6*h_t^2 + 18*h_y^2 - 6 elif self._i == 1 and (self._u % 3) == 1: self.polynomial_tr = [1+ht, 1-ht, ht] #tr = T + 1 +h_t*r if sign_y0 == None: sign_y0 = 1 if sign_y0 == -1: self.polynomial_y = [-2+3*hy, -3*hy, -1+3*hy] # y = -(T^2+2)//3 + hy*r self.polynomial_p = [3*(ht+1)**2+(3*hy-2)**2, -6*(ht**2+3*hy**2-2*hy-1), 9*ht**2+27*hy**2-18*hy+7, -6*(ht**2-ht+3*hy**2-hy), 3*ht**2+(3*hy-1)**2] self.polynomial_c = [3*(ht+1)**2+(3*hy-2)**2, -(3*ht**2-6*ht+9*hy**2-1), (3*ht**2+(3*hy-1)**2)] #self.polynomial_beta = [-6*ht**2-6*ht-18*hy**2+6*hy+4, 9*ht**2-6*ht+27*hy**2-12*hy+5, -9*ht**2+6*ht-27*hy**2+12*hy-1, 3*ht**2+9*hy**2-6*hy+1] self.polynomial_beta = [6*ht**2+18*hy**2-24*hy+2, -(3*ht-1)**2-27*hy**2+12*hy-4, (3*ht-1)**2+27*hy**2-12*hy, -3*ht**2-9*hy**2+6*hy-1] self.polynomial_beta_denom = 6*(ht+3*hy-1) else: self.polynomial_y = [2+3*hy, -3*hy, 1+3*hy] # y = (T^2+2)//3 + hy*r self.polynomial_p = [3*(ht+1)**2+(3*hy+2)**2, -6*(ht**2+3*hy**2+2*hy-1), 9*ht**2+27*hy**2+18*hy+7, -6*(ht**2-ht+3*hy**2+hy), 3*ht**2+(3*hy+1)**2] self.polynomial_c = [3*(ht-1)**2+(3*hy+2)**2, -(3*ht**2-6*ht+9*hy**2-1), (3*ht**2+(3*hy+1)**2)] self.polynomial_beta = [-6*ht*(ht+1)-6*hy*(1+3*hy)+4,(3*ht-1)**2+27*hy**2+12*hy+4, -9*ht**2+6*ht-27*hy**2-12*hy-1, 3*ht**2+(3*hy+1)**2] self.polynomial_beta_denom = 6*(ht-3*hy-1) elif self._i == 5 and (self._u % 3) == 1: if sign_y0 == None: sign_y0 = 1 self.polynomial_tr = [2+ht, -ht-1, ht] if sign_y0 == -1: # alternative choice of y (sign of y0) self.polynomial_y = [3*hy+1, 3*hy, 3*hy-1] # y = -(T^2-1)//3 + hy*r self.polynomial_p = [3*(ht+2)**2+(3*hy+1)**2, -6*(ht**2+3*ht+3*hy**2+hy+2), (9*ht**2+18*ht+27*hy**2+1), -6*(ht**2+ht+3*hy**2-hy), 3*ht**2+(3*hy-1)**2] self.polynomial_c = [3*ht**2+12*ht+(3*hy+1)**2, -(3*ht**2+6*ht+9*hy**2-1), 3*ht**2+(3*hy-1)**2] self.polynomial_beta = [3*ht**2+9*hy**2-12*hy-8, 2*(3*ht-3*hy+2), -6*(ht-hy), 3*(ht**2+3*hy**2)] self.polynomial_beta_denom = 6*(ht+3*hy) else: self.polynomial_y = [3*hy-1, -3*hy, 3*hy+1] # y = (T^2-1)//3 +hy*r self.polynomial_p = [3*(ht+2)**2+(3*hy-1)**2, -6*(ht**2+3*ht+3*hy**2-hy+2), (9*ht**2+18*ht+27*hy**2+1), -6*(ht**2+ht+3*hy**2+hy), 3*ht**2+(3*hy+1)**2] self.polynomial_c = [3*ht**2+(3*hy-1)**2, -3*(ht+1)**2-9*hy**2+4, 3*ht**2+(3*hy+1)**2] self.polynomial_beta = [3*ht**2+9*hy**2-6*hy-11, 6*ht-6*hy+2, -6*ht+6*hy+2, 3*ht**2+9*hy**2+6*hy+1] self.polynomial_beta_denom = 6*(ht+3*hy+1) elif self._i == 5 and (self._u % 3) == 0: self.polynomial_tr = [2+ht, -ht-1, ht] if sign_y0 == None: sign_y0 = -1 """ self.polynomial_y = [3*hy, -3*hy-1, 3*hy+2] self.polynomial_p = [3*ht**2+9*hy**2+12*ht+12, -6*ht**2-18*hy**2-18*ht-6*hy-12, 9*ht**2+27*hy**2+18*ht+18*hy+4, -6*ht**2-18*hy**2-6*ht-18*hy-4, 3*ht**2+9*hy**2+12*hy+4] self.polynomial_c = [3*ht**2+9*hy**2, -3*ht**2-9*hy**2-6*ht-6*hy, 3*ht**2+9*hy**2+12*hy+4] self.polynomial_y = [3*hy, -3*hy+1, 3*hy-2] self.polynomial_p = [3*ht**2+9*hy**2+12*ht+12, -6*ht**2-18*hy**2-18*ht+6*hy-12, 9*ht**2+27*hy**2+18*ht-18*hy+4, -6*ht**2-18*hy**2-6*ht+18*hy-4, 3*ht**2+9*hy**2-12*hy+4] self.polynomial_c = [3*ht**2+9*hy**2, -3*ht**2-9*hy**2-6*ht+6*hy, 3*ht**2+9*hy**2-12*hy+4] """ if sign_y0 == -1: self.polynomial_y = [3*hy-3, -3*hy+2, 3*hy-1] # y = (-3+2*T-T^2)/3 + hy*r self.polynomial_p = [3*ht**2+9*hy**2+12*ht-18*hy+21, -6*ht**2-18*hy**2-18*ht+30*hy-24, 9*ht**2+27*hy**2+18*ht-36*hy+13, -6*ht**2-18*hy**2-6*ht+18*hy-4, 3*ht**2+9*hy**2-6*hy+1] self.polynomial_c = [3*ht**2+9*hy**2-18*hy+9, -3*ht**2-9*hy**2-6*ht+12*hy-3, 3*ht**2+9*hy**2-6*hy+1] self.polynomial_beta = [3*ht**2+9*hy**2-18*hy-3, 6*ht-6*hy+6, -6*ht+6*hy-2, 3*ht**2+9*hy**2-6*hy+1] self.polynomial_beta_denom = 6*(ht+3*hy-1) else: raise ValueError("Error: tr = T^{} + 1 and u=T={} mod 3 but only tr=T+1 with T=0,1 mod 3 or tr=T^5+1 with T=0,1 mod 3 are allowed.".format(self._i, (self._u % 3))) self._r = sum([Integer(self.polynomial_r[i])*self._u**i for i in range(len(self.polynomial_r))]) if r != None: if self._r != Integer(r): raise ValueError("Error: r does not match the polynomial r(T)\nr = {:= #x} #(input)\nr = {:= #x} # from polynomial r(T,ht,hy) = {}".format(r,self._r,self.polynomial_r)) #else: # print("valid r") self._tr = sum([Integer(self.polynomial_tr[i])*self._u**i for i in range(len(self.polynomial_tr))]) if tr != None: if self._tr != Integer(tr): raise ValueError("Error: tr does not match the polynomial tr(T,ht)\ntr = {:= #x} #(input)\ntr = {:= #x} # from polynomial tr(T,ht,hy) = {}".format(tr,self._tr,self.polynomial_tr)) #else: # print("valid tr") self._y = sum([Integer(self.polynomial_y[i])*self._u**i for i in range(len(self.polynomial_y))])//Integer(self.polynomial_y_denom) if y != None: if self._y != Integer(y): raise ValueError("Error: y does not match the polynomial y(T)\ny = {:= #x} #(input)\ny = {:= #x} # from polynomial y(T,ht,hy) = {}".format(y,self._y,self.polynomial_y)) #else: # print("valid y") self._p = sum([Integer(self.polynomial_p[i])*self._u**i for i in range(len(self.polynomial_p))])//Integer(self.polynomial_p_denom) if p != None: if self._p != Integer(p): raise ValueError("Error: p does not match the polynomial P(T,ht,hy)\np = {:= #x} #(input)\np = {:= #x} # from polynomial p(T,ht,hy) = {}/{}".format(p,self._p,self.polynomial_p,self.polynomial_p_denom)) #else: # print("valid p") self._c = sum([Integer(self.polynomial_c[i])*self._u**i for i in range(len(self.polynomial_c))])//Integer(self.polynomial_c_denom) if self._c*self._r != (self._p+1-self._tr): raise ValueError("Error: r*c != p+1-tr,\nr*c ={}\np+1-tr={}\np ={}\nr ={}\ntr ={}\nc ={}\np+1-tr % r = {}\n".format(self._c*self._r,(self._p+1-self._tr), self._p, self._r, self._tr, self._c, ((self._p+1-self._tr) % self._r) )) #else: # print("valid c") self._pbits = self._p.nbits() self._beta = sum([Integer(self.polynomial_beta[i])*self._u**i for i in range(len(self.polynomial_beta))])/Integer(self.polynomial_beta_denom) self._lamb = -self._u try: self._Fp = FiniteField(self._p) except ValueError as err: print("ValueError creating Fp: {}".format(err)) raise except: print("Error creating Fp") raise if not self._r.is_prime(): raise ValueError("Error r is not prime") self._beta = Integer(self._Fp(self._beta)) if ((self._beta**2 + self._beta + 1) % self._p) != 0: raise ValueError("Error beta^2 + beta + 1 != 0 mod p") if ((self._lamb**2 + self._lamb + 1) % self._r) != 0: raise ValueError("Error lamb^2 + lamb + 1 != 0 mod r") self._Fpz = PolynomialRing(self._Fp, names=('z',)) (self._z,) = self._Fpz._first_ngens(1) if b != None: try: b = Integer(b) except: raise self._b = b self._bp = self._Fp(b) else: self._b, self._bp = get_curve_parameter_b_j0(self._tr, self._y, self._beta, self._p, self._Fp) self._ap = self._Fp(0) # first curve parameter is 0 because j=0 # Now self._b is such that E: y^2 = x^3 + b has order r try: # this init function of super inherits from class EllipticCurve_generic defined in ell_generic.py # __init__ method inherited from ell_generic EllipticCurve_finite_field.__init__(self, self._Fp, [0,0,0,0,self._bp]) except ValueError as err: print("ValueError at EllipticCurve_finite_field.__init__: {}".format(err)) raise except: print("An error occured when initialising the elliptic curve") raise self.order_checked = super(CocksPinch6,self).order() if self.order_checked != (self._p+1-self._tr): #if (self.order_checked % self._r) != 0: print("Error, wrong order") if self.order_checked == (self._p+1+self._tr): raise ValueError("Wrong curve order: this one is a twist (order p+1+tr)") else: raise ValueError("Wrong curve order, not p+1-tr, not p+1+tr") # computes a generator self._G = get_curve_generator_order_r_j0(self) self._Gx = self._G[0] self._Gy = self._G[1] # adjust beta and lamb according to the curve # do we have (beta*x,y) = lamb*(x,y)? if self([self._Gx*self._beta, self._Gy]) != self._lamb*self._G: print("adjusting beta, lambda") if self([self._Gx*(-self._beta-1), self._Gy]) == self._lamb*self._G: self._beta = -self._beta-1 print("beta -> -beta-1") elif self([self._Gx*self._beta, self._Gy]) == (-self._lamb-1)*self._G: self._lamb = -self._lamb-1 print("lamb -> -lamb-1") elif self([self._Gx*(-self._beta-1), self._Gy]) == (-self._lamb-1)*self._G: self._beta = -self._beta-1 self._lamb = -self._lamb-1 print("lamb -> -lamb-1") print("beta -> -beta-1") else: raise ValueError("Error while adjusting beta, lamb: compatibility not found") def _repr_(self): return "CP6 p"+str(self._pbits)+" (modified Cocks-Pinch k=6) curve with seed "+str(self._u)+"\n"+super(CocksPinch6,self)._repr_() def u(self): return self._u def p(self): return self._p def r(self): return self._r def c(self): return self._c def tr(self): return self._tr def y(self): return self._y def a(self): return self._a # 0 def ap(self): return self._ap # 0 def b(self): return self._b # Integer def bp(self): return self._bp # in Fp (finite field element) def beta(self): return self._beta def lamb(self): return self._lamb def k(self): return self._k def Fp(self): return self._Fp def Fpz(self): return self._Fpz, self._z def G(self): return self._G def print_parameters(self): PairingFriendlyCurve.print_parameters(self) def print_parameters_for_RELIC(self): PairingFriendlyCurve.print_parameters_for_RELIC(self) """ sage: load("formules-familles-CocksPinch.sage") sage: formulas(6) ######################################## k=6 D=3 i=1 T%6=0 t = T + 1 +h_t*r y = 1/3*T^2 - 2/3*T +h_y*r coeffs p, T^4 first, constant last: ((1/3) * (3*h_t^2 + 9*h_y^2 + 6*h_y + 1))*T^4 + ((-2/3) * (3*h_t^2 + 9*h_y^2 - 3*h_t + 9*h_y + 2))*T^3 + ((1/3) * (9*h_t^2 + 27*h_y^2 + 18*h_y + 7))*T^2 + ((-2) * (h_t^2 + 3*h_y^2 + 2*h_y - 1))*T + (h_t^2 + 3*h_y^2 + 2*h_t + 1) p+1-t0 = (1/12) * (T^2 - T + 1) * (3*T^2*h_t^2 + 9*T^2*h_y^2 - 3*T*h_t^2 + 6*T^2*h_y - 9*T*h_y^2 + T^2 + 6*T*h_t + 3*h_t^2 - 12*T*h_y + 9*h_y^2 - 3*T + 6*h_t + 3) denominator cancellation condition for c: (h_t + h_y + 1)^2 * (T^2 + T + 1) coeffs c, T^2 1st, constant last: ((1/12) * (3*h_t^2 + 9*h_y^2 + 6*h_y + 1))*T^2 + ((-1/4) * (h_t^2 + 3*h_y^2 - 2*h_t + 4*h_y + 1))*T + ((1/4) * (h_t^2 + 3*h_y^2 + 2*h_t + 1)) horner c: ((1/4*h_t^2 + 3/4*h_y^2 + 1/2*h_y + 1/12)*T+-1/4*h_t^2 - 3/4*h_y^2 + 1/2*h_t - h_y - 1/4)*T+1/4*h_t^2 + 3/4*h_y^2 + 1/2*h_t + 1/4 formula for 3*c in case T mod 3 == 0 and h_t mod 2 == 0 [3*u^2 + 9*w^2 - 6*w + 1, -3*u^2 - 9*w^2 + 3*u + 3*w, 3*u^2 + 9*w^2 + 3*u - 9*w + 3] 12M + 2s + 2u + 2w + 2U formula for 3*c in case T mod 3 == 0 and h_t mod 2 == 1 [3*u^2 + 9*w^2 - 3*u + 3*w + 1, -3*u^2 - 9*w^2 + 6*u - 6*w - 3, 3*u^2 + 9*w^2] 10M + 3s + 2u + 2w + 2U ######################################## k=6 D=3 i=1 T%6=1 t = T + 1 +h_t*r y = -1/3*T^2 - 2/3 +h_y*r coeffs p, T^4 first, constant last: ((1/3) * (3*h_t^2 + 9*h_y^2 - 6*h_y + 1))*T^4 + ((-2) * (h_t^2 + 3*h_y^2 - h_t - h_y))*T^3 + ((1/3) * (9*h_t^2 + 27*h_y^2 - 18*h_y + 7))*T^2 + ((-2) * (h_t^2 + 3*h_y^2 - 2*h_y - 1))*T + ((1/3) * (3*h_t^2 + 9*h_y^2 + 6*h_t - 12*h_y + 7)) p+1-t0 = (1/12) * (T^2 - T + 1) * (3*T^2*h_t^2 + 9*T^2*h_y^2 - 3*T*h_t^2 - 6*T^2*h_y - 9*T*h_y^2 + T^2 + 6*T*h_t + 3*h_t^2 + 9*h_y^2 + T + 6*h_t - 12*h_y + 7) denominator cancellation condition for c: (h_t + h_y + 1)^2 * (T^2 + T + 1) coeffs c, T^2 1st, constant last: ((1/12) * (3*h_t^2 + 9*h_y^2 - 6*h_y + 1))*T^2 + ((-1/12) * (3*h_t^2 + 9*h_y^2 - 6*h_t - 1))*T + ((1/12) * (3*h_t^2 + 9*h_y^2 + 6*h_t - 12*h_y + 7)) horner c: ((1/4*h_t^2 + 3/4*h_y^2 - 1/2*h_y + 1/12)*T+-1/4*h_t^2 - 3/4*h_y^2 + 1/2*h_t + 1/12)*T+1/4*h_t^2 + 3/4*h_y^2 + 1/2*h_t - h_y + 7/12 formula for 3*c in case T mod 3 == 1 and h_t mod 2 == 0 [3*u^2 + 9*w^2 + 6*w + 1, 3*u^2 + 9*w^2 + 3*u + 3*w, 3*u^2 + 9*w^2 + 6*u] 10M + 2s + 2u + 2w + 2U formula for 3*c in case T mod 3 == 1 and h_t mod 2 == 1 [3*u^2 + 9*w^2 - 3*u - 3*w + 1, 3*u^2 + 9*w^2 - 6*w, 3*u^2 + 9*w^2 + 3*u - 9*w] 11M + 2s + 2u + 2w + 2U ######################################## k=6 D=3 i=5 T%3=0 t = -T + 2 +h_t*r y = 1/3*T^2 - 2/3*T + 1 +h_y*r coeffs p, T^4 first, constant last: ((1/3) * (3*h_t^2 + 9*h_y^2 + 6*h_y + 1))*T^4 + ((-2/3) * (3*h_t^2 + 9*h_y^2 + 3*h_t + 9*h_y + 2))*T^3 + ((1/3) * (9*h_t^2 + 27*h_y^2 + 18*h_t + 36*h_y + 13))*T^2 + ((-2) * (h_t^2 + 3*h_y^2 + 3*h_t + 5*h_y + 4))*T + (h_t^2 + 3*h_y^2 + 4*h_t + 6*h_y + 7) p+1-t0 = (1/12) * (T^2 - T + 1) * (3*T^2*h_t^2 + 9*T^2*h_y^2 - 3*T*h_t^2 + 6*T^2*h_y - 9*T*h_y^2 + T^2 - 6*T*h_t + 3*h_t^2 - 12*T*h_y + 9*h_y^2 - 3*T + 12*h_t + 18*h_y + 9) denominator cancellation condition for c: (h_t + h_y + 1)^2 * (T^2 + T + 1) coeffs c, T^2 1st, constant last: ((1/12) * (3*h_t^2 + 9*h_y^2 + 6*h_y + 1))*T^2 + ((-1/4) * (h_t^2 + 3*h_y^2 + 2*h_t + 4*h_y + 1))*T + ((1/4) * (h_t^2 + 3*h_y^2 + 4*h_t + 6*h_y + 3)) horner c: ((1/4*h_t^2 + 3/4*h_y^2 + 1/2*h_y + 1/12)*T+-1/4*h_t^2 - 3/4*h_y^2 - 1/2*h_t - h_y - 1/4)*T+1/4*h_t^2 + 3/4*h_y^2 + h_t + 3/2*h_y + 3/4 formula for 3*c in case T mod 3 == 0 and h_t mod 2 == 0 [3*u^2 + 9*w^2 - 6*w + 1, -3*u^2 - 9*w^2 - 3*u + 3*w, 3*u^2 + 9*w^2 + 6*u] 10M + 2s + 2u + 2w + 2U formula for 3*c in case T mod 3 == 0 and h_t mod 2 == 1 [3*u^2 + 9*w^2 - 3*u + 3*w + 1, -3*u^2 - 9*w^2 - 6*w, 3*u^2 + 9*w^2 + 3*u + 9*w] 11M + 2s + 2u + 2w + 2U ######################################## k=6 D=3 i=5 T%3=1 t = -T + 2 +h_t*r y = -1/3*T^2 + 1/3 +h_y*r coeffs 4*p, T^4 first, constant last: ((1/3) * (3*h_t^2 + 9*h_y^2 - 6*h_y + 1))*T^4 + ((-2) * (h_t^2 + 3*h_y^2 + h_t - h_y))*T^3 + ((1/3) * (9*h_t^2 + 27*h_y^2 + 18*h_t + 1))*T^2 + ((-2) * (h_t^2 + 3*h_y^2 + 3*h_t + h_y + 2))*T + ((1/3) * (3*h_t^2 + 9*h_y^2 + 12*h_t + 6*h_y + 13)) p+1-t0 = (1/12) * (T^2 - T + 1) * (3*T^2*h_t^2 + 9*T^2*h_y^2 - 3*T*h_t^2 - 6*T^2*h_y - 9*T*h_y^2 + T^2 - 6*T*h_t + 3*h_t^2 + 9*h_y^2 + T + 12*h_t + 6*h_y + 1) denominator cancellation condition for c: (h_t + h_y + 1)^2 * (T^2 + T + 1) coeffs c, T^2 1st, constant last: ((1/12) * (3*h_t^2 + 9*h_y^2 - 6*h_y + 1))*T^2 + ((-1/12) * (3*h_t^2 + 9*h_y^2 + 6*h_t - 1))*T + ((1/12) * (3*h_t^2 + 9*h_y^2 + 12*h_t + 6*h_y + 1)) horner c: ((1/4*h_t^2 + 3/4*h_y^2 - 1/2*h_y + 1/12)*T+-1/4*h_t^2 - 3/4*h_y^2 - 1/2*h_t + 1/12)*T+1/4*h_t^2 + 3/4*h_y^2 + h_t + 1/2*h_y + 1/12 formula for 3*c in case T mod 3 == 1 and h_t mod 2 == 0 [3*u^2 + 9*w^2 + 6*w + 1, 3*u^2 + 9*w^2 - 3*u + 3*w, 3*u^2 + 9*w^2 + 3*u + 9*w + 3] 12M + 2s + 2u + 2w + 2U formula for 3*c in case T mod 3 == 1 and h_t mod 2 == 1 [3*u^2 + 9*w^2 - 3*u - 3*w + 1, 3*u^2 + 9*w^2 - 6*u - 6*w + 3, 3*u^2 + 9*w^2] 10M + 3s + 2u + 2w + 2U ############################################################ Rxm = QQ['x, m']; (x, m,) = Rxm._first_ngens(2) # polynomials (will be needed later for polynomial selection) R_CP6 = x^2 - x + 1 # cyclotomic_polynomial(6) T_CP6 = x + 1 """