u=-(2^62 + 2^55 +1)

p=36*u^4+36*u^3+24*u^2+6*u+1
r=36*u^4+36*u^3+18*u^2+6*u+1
t=6*u^2+1
#-------------- Fp--------------
Fp=GF(p)
#-------------------------------
b=2
#--------------Fp^2--------------
K2.<i>=PolynomialRing(Fp)
Fp2.<i>=FiniteField(p^2,modulus=i^2+1)
#------------------------------------
#-------------Fp^6---------------------
K6.<v>=PolynomialRing(Fp2)
Fp6.<v>=Fp2.extension(v^3-i-1)
#-------------------------------------

#---------------Fp^12-------------------

K12.<z>=PolynomialRing(Fp6)
Fp12.<z>=Fp6.extension(z^2-v)
Fp12.is_field=lambda:True
#---------------------------------------

a00=Fp.random_element()
a01=Fp.random_element()
a10=Fp.random_element()
a11=Fp.random_element()
a20=Fp.random_element()
a21=Fp.random_element()

b00=Fp.random_element()
b01=Fp.random_element()
b10=Fp.random_element()
b11=Fp.random_element()
b20=Fp.random_element()
b21=Fp.random_element()

#------------------------------------
f= (((a00+i*a01)+(a10+i*a11)*v+(a20+i*a21)*v^2)+((b00+i*b01)+(b10+i*b11)*v+(b20+i*b21)*v^2)*z)
#--------------------------------------
def multiplication2(a00,a10,a01,a11):                                     
   
   t0=a00+a01
   t1=a10+a11
   t0=t0*t1
   t1=a00*a10
   t2=a01*a11
   t0=t0-t1
   t0=t0-t2
   t1=(t1-t2)                                                               
   return (t1,t0) 
#----------------------------------

#-----------------------------------
#-----------------------------------
def carre2(a20,a21):                                                       
   
   t0=a20+a21
   t1=a20-a21
   t0=t0*t1
   t1=a20*a21
   t1=2*t1  
   return (t1,t0) 
#----------------------------------
#----------------------------------



#-------------carre ds Fp^6-----------------------

def carre(a00, a01, a10, a11, a20, a21):                    
   t0,t1= multiplication2(a00,a10,a01,a11)                     
   t0=2*t0
   t1=2*t1                                         
#---------------------------------
   t2,t3= carre2(a20,a21)                                            
#---------------------------------
   t4=t2-t3
   t4=t4+t0
   t5=t2+t3
   t5=t5+t1
   
   t6=t0-t2
   t7=t1-t3
#----------------------------
   t8,t9=carre2(a00,a01)                                           
   t0=a00-a10                                                           
   t0=t0+a20
   t1=a01-a11
   t1=t1+a21
   t0,t1=carre2(t0,t1)                           
#----------------------------------
   t2,t3= multiplication2(a10,a20,a11,a21)         
   t2=2*t2
   t3=2*t3

#------------------------------------
   
   
   t6=t6-t8
   t6=t6+t0
   t6=t6+t2
   t7=t7-t9
   t7=t7+t1
   t7=t7+t3
   
   
   
   t0=t2-t3
   t0=t0+t8
   t1=t2+t3
   t1=t1+t9
  
#-------------------------------------
   
   return t0,t1,t4,t5,t6,t7
   
   
#----------------------------------------

def base_deux(n):
    L=[]
    i=n
    while i!=0:
        if i%2==0:
            L=L+[0];
            i=i/2;
        else:
            L=L+[1];
            i=(i-1)/2;
    return(L)
#--------------------------------    
def expo_rapide(t0,t1,e):
    t0=1;                                               
    t1=1;
    
    if e==0:
        return(1,0);
    else:
        L=base_deux(e);
        k=len(L);
        for j in range (1,k):
            (t2,t3)=carre2(t0,t1);                                     
            (t0,t1)=(t2%p, t3%p);        
            if L[k-j-1]==1:
                t2=(t0-t1) ;             
                t3=(t0+t1);
                t0=t2%p;
                t1=t3%p;
    return (t0,t1)
    

#-----------------------------------------------


def carree(a00, a01, a10, a11, a20, a21, b00, b01, b10, b11, b20, b21):
    t0,t1,t2,t3,t4,t5=carre(a00, a01, a10, a11, a20, a21)
    
    t6,t7,t8,t9,t10,t11=carre(b00, b01, b10, b11, b20, b21)
    
    t12,t13,t14,t15,t16,t17=carre(a00+b00, a01+b01, a10+b10, a11+b11, a20+b20, a21+b21)
    
    t12,t13,t14,t15,t16,t17=(t12-t0, t13-t1, t14-t2, t15-t3, t16-t4, t17-t5)
    t12,t13,t14,t15,t16,t17=(t12-t6, t13-t7, t14-t8, t15-t9, t16-t10, t17-t11)
  
  
    t6,t7,t8,t9,t10,t11=(t10-t11, t10+t11, t6, t7, t8, t9)
    t6,t7,t8,t9,t10,t11=(t6+t0, t7+t1, t8+t2, t9+t3, t10+t4, t11+t5)
    
    return (t6,t7,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17)
    
#-------------------------------------------------------------------------------------


#----multiplication ds Fp^6------------------
def multiplication(a00, a01, a10, a11, a20, a21, c00, c01, c10, c11, c20, c21):
  t2,t3=multiplication2(a10,c10,a11,c11)                                  
#-------------------------------------
  t4,t5=multiplication2(a20,c20,a21,c21)                                   
#-------------------------------------
  t6,t7=multiplication2(a10+a20,c10+c20,a11+a21,c11+c21)                   
#-------------------------------------- 
  t6=t6-t2
  t6=t6-t4 
  t7=t7-t3
  t7=t7-t5
  t8,t9=t6-t7, t6+t7                                
  t0,t1=multiplication2(a00,c00,a01,c01)
  t8=t8+t0
  t9=t9+t1                                            
#------------------------------------------
  t6,t7=multiplication2(a00+a10,c00+c10,a01+a11,c01+c11)                                                   
#------------------------------------------------
  t6=t6-t0
  t7=t7-t1
  t6=t6-t2
  t7=t7-t3  
  
  t6=t6+t4
  t6=t6-t5
  t7=t7+t5
  t7=t7+t4                          
#-------------------------------------------                                                   
  t0,t1=(t0+t4, t1+t5)
  t0,t1=(t0-t2, t1-t3)  
  t2,t3=multiplication2(a00+a20,c00+c20,a01+a21,c01+c21)
  t0,t1=(t2-t0, t3-t1)                    
#-------------------------------
  return (t8,t9,t6,t7,t0,t1)
  
#----------------------------------------   

#----------------multiplication ds Fp^12---------------------------------------------------
def multiplicationn(a00, a01, a10, a11, a20, a21, c00, c01, c10, c11, c20, c21,b00, b01, b10, b11, b20, b21, d00, d01, d10, d11, d20, d21):
   
    
    t6,t7,t8,t9,t10,t11=multiplication(b00, b01, b10, b11, b20, b21, d00, d01, d10, d11, d20, d21)
    t0,t1,t2,t3,t4,t5=multiplication(a00, a01, a10, a11, a20, a21, c00, c01, c10, c11, c20, c21)
    t12,t13,t14,t15,t16,t17=multiplication(a00+b00, a01+b01, a10+b10, a11+b11, a20+b20, a21+b21, c00+d00, c01+d01, c10+d10, c11+d11, c20+d20, c21+d21)
   
    t12,t13,t14,t15,t16,t17=(t12-t0, t13-t1, t14-t2, t15-t3, t16-t4, t17-t5)
    t12,t13,t14,t15,t16,t17=(t12-t6, t13-t7, t14-t8, t15-t9, t16-t10, t17-t11)
  
   
    t6,t7,t8,t9,t10,t11=(t10-t11, t10+t11, t6, t7, t8, t9)
    t6,t7,t8,t9,t10,t11=(t6+t0, t7+t1, t8+t2, t9+t3, t10+t4, t11+t5)
    
    return (t6,t7,t8,t9,t10,t11,t12,t13,t14,t15,t16,t17)
    
#-------------------------------------------------------

#------------inversionFp^2-------------
def inversion2(a00, a01):
    t0=a00^2                                                               
    t1=a01^2
    t0=t0+t1
    t1=t0^(-1)
    t0=a00*t1
    t1=-a01*t1
    
    return (t0,t1)
    
    
    
#------------------------------------------

#-----------inversion Fp^6------------------
def inversion6(a00,a01,a10,a11,a20,a21):
    t0,t1=carre2(a00,a01)
    t2,t3=multiplication2(a10,a20,a11,a21)
    t0,t1=(t0-t2, t1-t2)
    t0,t1=(t0+t3,t1-t3) 
    t4,t5=multiplication2(a00,a10,a01,a11)
    t6,t7=carre2(a20,a21)
    t4,t5=(t6-t4, t6-t5)
    t4,t5=(t4-t7, t5+t7)
    t2,t3=carre2(a10,a11) 
    t6,t7=multiplication2(a00,a20,a01,a21)
    t6,t7=(t2-t6, t3-t7)
    
    t8,t9=multiplication2(a20-a21,t4,a20+a21,t5)
    t2,t3=multiplication2(a00,t0,a01,t1) 
    t2,t3=(t2+t8, t3+t9)
    t8,t9=multiplication2(a10-a11,t6,a10+a11,t7)
    t2,t3=(t2+t8, t3+t9)
        
    t2,t3=inversion2(t2,t3)                   
    t0,t1=multiplication2(t0, t2, t1,t3)    
    t4,t5=multiplication2(t4, t2, t5,t3)
    t6,t7=multiplication2(t6, t2, t7,t3)
    
    return(t0,t1,t4,t5,t6,t7)
    
#-------------------------------------------------
                
  #--------------Inversion ds Fp^12-----------------------

def inversion(a00, a01, a10, a11, a20, a21, b00, b01, b10, b11, b20, b21):
    t0,t1,t2,t3,t4,t5=carre(a00, a01, a10, a11, a20, a21)
   
    t6,t7,t8,t9,t10,t11=carre(b00, b01, b10, b11, b20, b21)
    
    t0,t1,t2,t3,t4,t5=(t0-t10+t11, t1-t10-t11, t2-t6, t3-t7,t4-t8, t5-t9)
    
    t0,t1,t2,t3,t4,t5=inversion6(t0,t1,t2,t3,t4,t5)
    
#--------------------------------------
    t6,t7,t8,t9,t10,t11=multiplication(a00, a01, a10, a11, a20, a21, t0, t1, t2, t3,t4,t5) 
                                     
    t0,t1,t2,t3,t4,t5=multiplication(b00, b01, b10, b11, b20, b21, t0, t1, t2, t3, t4, t5) 
                                      
  
    return  (t6,t7,t8,t9,t10,t11, -t0,-t1,-t2,-t3,-t4,-t5)
    
    
#--------------------------------------------
q0,q1=expo_rapide(1,1, (p^2-1)/6)                
q2,q3=expo_rapide(1,1, 2*(p^2-1)/6)    
q4,q5=expo_rapide(1,1, 3*(p^2-1)/6)
q6,q7=expo_rapide(1,1, 4*(p^2-1)/6)
q8,q9=expo_rapide(1,1, 5*(p^2-1)/6)
#---------------------------------------------
s00,s01=expo_rapide(1,1, (p^3-1)/6)                
s02,s03=expo_rapide(1,1, 2*(p^3-1)/6)    
s04,s05=expo_rapide(1,1, 3*(p^3-1)/6)
s06,s07=expo_rapide(1,1, 4*(p^3-1)/6)
s08,s09=expo_rapide(1,1, 5*(p^3-1)/6)
#----------------------------------------------
t10,t11=expo_rapide(1,1, (p-1)/6)                
t12,t13=expo_rapide(1,1, 2*(p-1)/6)    
t14,t15=expo_rapide(1,1, 3*(p-1)/6)
t16,t17=expo_rapide(1,1, 4*(p-1)/6)
t18,t19=expo_rapide(1,1, 5*(p-1)/6)

def frob1(a00, a01, a10, a11, a20, a21, b00, b01, b10, b11, b20, b21 ,p): 
       
       
    t0,t1=multiplication21(b00,t10,b01,t11)
    t2,t3=multiplication21(a10,t12,a11,t13)
    t4,t5=multiplication21(b10,t14,b11,t15)
    t6,t7=multiplication21(a20,t16,a21,t17)
    t8,t9=multiplication21(b20,t18,b21,t19)

    return (a00, -a01, t2, t3, t6,t7, t0, t1, t4, t5, t8, t9)
  
    
#---------------------------------------
def frob2(a00, a01, a10, a11, a20, a21, b00, b01, b10, b11, b20, b21,p):
        
    t0,t1=multiplication2(b00,q0,b01,q1)
    t2,t3=multiplication2(a10,q2,a11,q3)
    t4,t5=multiplication2(b10,q4,b11,q5)
    t6,t7=multiplication2(a20,q6,a21,q7)
    t8,t9=multiplication2(b20,q8,b21,q9)
#-------------------------------------------
    
    return (a00, a01, t2, t3, t6,t7, t0, t1, t4, t5, t8, t9)
    
#----------------------------------------------------------------------  
def frob3(a00, a01, a10, a11, a20, a21, b00, b01, b10, b11, b20, b21 ,p): 
       
   
    
    t0,t1=multiplication21(b00,s00,b01,s01)
    t2,t3=multiplication21(a10,s02,a11,s03)
    t4,t5=multiplication21(b10,s04,b11,s05)
    t6,t7=multiplication21(a20,s06,a21,s07)
    t8,t9=multiplication21(b20,s08,b21,s09)
#-------------------------------------------
    
    return (a00, -a01, t2, t3, t6,t7, t0, t1, t4, t5, t8, t9)

#----------------------------------------------------------------------  
def frob6(a00, a01, a10, a11, a20, a21, b00, b01, b10, b11, b20, b21 ,p): 
    return (a00, a01, a10, a11, a20, a21, -b00, -b01, -b10, -b11, -b20, -b21)  
     
#----------------------------------------------------------------------

def expoo_rapide(a00, a01, a10, a11, a20, a21, b00, b01, b10, b11, b20, b21, e):
    t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11= a00,a01,a10,a11,a20,a21,b00,b01,b10,b11,b20,b21
    
    if e==0:
        return (1); 
    else:   
        t12=base_deux(e);
        t13=len(t12);
        for j in range(1,t13):
           t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11= carree(t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11);          
           
           if t12[t13-j-1]==1:
               t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11= multiplicationn(a00, a01, a10, a11, a20, a21, t0, t1, t2, t3,t4, t5, b00, b01, b10, b11, b20,  b21, t6, t7, t8, t9, t10, t11);              
               
    return (t0,t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11)

u=-(2^62 + 2^55 +1)

p=36*u^4+36*u^3+24*u^2+6*u+1
p-1/12