1  
  2  //
  3  // the quadratic field extension `F[X] / (X^2 - 7)` over Goldilocks
  4  //
  5  // note: `X^2 - 7` is also irreducible over the field of size `2^8 - 2^4 + 1`
  6  // so can use it for testing too.
  7  //
  8  
  9  pragma circom 2.2.0;
 10  
 11  include "goldilocks.circom";
 12  // include "misc.circom";
 13  
 14  //------------------------------------------------------------------------------
 15  //
 16  // the type of quadratic field extension elements.
 17  //
 18  
 19  bus GoldilocksExt() {
 20    Goldilocks() real;
 21    Goldilocks() imag;
 22  }
 23  
 24  template GoldilocksToExt() {
 25    input  Goldilocks()    inp;
 26    output GoldilocksExt() out;
 27    out.real     <== inp;
 28    out.imag.val <== 0;
 29  }
 30  
 31  //------------------------------------------------------------------------------
 32  
 33  template NegExt() {
 34    input  GoldilocksExt() A;
 35    output GoldilocksExt() C;
 36  
 37    C.real <== Neg()( A.real );
 38    C.imag <== Neg()( A.imag );
 39  }
 40  
 41  template AddExt() {
 42    input  GoldilocksExt() A,B;
 43    output GoldilocksExt() C;
 44  
 45    C.real <== Add()( A.real , B.real );
 46    C.imag <== Add()( A.imag , B.imag );
 47  }
 48  
 49  template SubExt() {
 50    input  GoldilocksExt() A,B;
 51    output GoldilocksExt() C;
 52  
 53    C.real <== Sub()( A.real , B.real );
 54    C.imag <== Sub()( A.imag , B.imag );
 55  }
 56  
 57  //------------------------------------------------------------------------------
 58  
 59  template SevenTimesProduct() {
 60    input  Goldilocks() inp1,inp2;
 61    output Goldilocks() out;
 62    out <== ReduceModP( 3 + SolinasExpoBig() )( 7 * inp1.val * inp2.val ); 
 63  }
 64  
 65  template SevenTimesSquare() {
 66    input  Goldilocks() inp;
 67    output Goldilocks() out;
 68    out <== ReduceModP( 3 + SolinasExpoBig() )( 7 * inp.val * inp.val ); 
 69  }
 70  
 71  //--------------------------------------
 72  
 73  template MulExt() {
 74    input  GoldilocksExt() A,B;
 75    output GoldilocksExt() C;
 76  
 77    Goldilocks() RR, IR, RI, IIx7;
 78    RR   <== Mul()( A.real , B.real );
 79    IR   <== Mul()( A.imag , B.real );
 80    RI   <== Mul()( A.real , B.imag );
 81    IIx7 <== SevenTimesProduct()( A.imag , B.imag );
 82  
 83    C.real <== Add()( RR , IIx7 );
 84    C.imag <== Add()( IR , RI   );
 85  }
 86  
 87  template SqrExt() {
 88    input  GoldilocksExt() A;
 89    output GoldilocksExt() C;
 90  
 91    Goldilocks() RR, IR, IIx7;
 92    RR   <== Sqr()( A.real );
 93    IR   <== Mul()( A.imag , A.real );
 94    IIx7 <== SevenTimesSquare()( A.imag );
 95  
 96    C.real <== Add()( RR , IIx7 );
 97    C.imag <== Add()( IR , IR   );
 98  
 99    // log("\nsqrExt");
100    // log( "A = (", A.real.val, " , ", A.imag.val, ")" );
101    // log( "C = (", C.real.val, " , ", C.imag.val, ")" );
102    // log( "RR   = ", RR.val   );
103    // log( "IR   = ", IR.val   );
104    // log( "IRx7 = ", IIx7.val );
105  }
106  
107  //------------------------------------------------------------------------------
108  
109  template InvExt() {
110    input  GoldilocksExt() A;
111    output GoldilocksExt() C;
112  
113    Goldilocks() seven, RR, IIx7;
114    seven.val <== 7;
115    RR   <== Sqr()( A.real );
116    IIx7 <== SevenTimesSquare()( A.imag );
117  
118    Goldilocks() denom     <== Sub()( RR , IIx7 );
119    Goldilocks() mult      <== Inv()( denom     );
120    Goldilocks() minusImag <== Neg()( A.imag );
121  
122    C.real <== Mul()( A.real    , mult );
123    C.imag <== Mul()( minusImag , mult );
124  }
125  
126  template DivExt() {
127    input  GoldilocksExt() A,B;
128    output GoldilocksExt() C;
129  
130    GoldilocksExt() invB <== InvExt()( B );
131    C <== MulExt()( A , invB );
132  
133    log("\ndivExt");
134    log( "A = (", A.real.val, " , ", A.imag.val, ")" );
135    log( "B = (", B.real.val, " , ", B.imag.val, ")" );
136    log( "C = (", C.real.val, " , ", C.imag.val, ")" );
137  
138  }
139  
140  //------------------------------------------------------------------------------