FeInvert function

void FeInvert(FieldElement out, FieldElement z)

Implementation

void FeInvert(FieldElement out, FieldElement z) {
  var t0 = FieldElement();
  var t1 = FieldElement();
  var t2 = FieldElement();
  var t3 = FieldElement();
  var i = 0;

  FeSquare(t0, z); // 2^1
  FeSquare(t1, t0); // 2^2
  for (i = 1; i < 2; i++) {
    // 2^3
    FeSquare(t1, t1);
  }
  FeMul(t1, z, t1); // 2^3 + 2^0
  FeMul(t0, t0, t1); // 2^3 + 2^1 + 2^0
  FeSquare(t2, t0); // 2^4 + 2^2 + 2^1
  FeMul(t1, t1, t2); // 2^4 + 2^3 + 2^2 + 2^1 + 2^0
  FeSquare(t2, t1); // 5,4,3,2,1
  for (i = 1; i < 5; i++) {
    // 9,8,7,6,5
    FeSquare(t2, t2);
  }
  FeMul(t1, t2, t1); // 9,8,7,6,5,4,3,2,1,0
  FeSquare(t2, t1); // 10..1
  for (i = 1; i < 10; i++) {
    // 19..10
    FeSquare(t2, t2);
  }
  FeMul(t2, t2, t1); // 19..0
  FeSquare(t3, t2); // 20..1
  for (i = 1; i < 20; i++) {
    // 39..20
    FeSquare(t3, t3);
  }
  FeMul(t2, t3, t2); // 39..0
  FeSquare(t2, t2); // 40..1
  for (i = 1; i < 10; i++) {
    // 49..10
    FeSquare(t2, t2);
  }
  FeMul(t1, t2, t1); // 49..0
  FeSquare(t2, t1); // 50..1
  for (i = 1; i < 50; i++) {
    // 99..50
    FeSquare(t2, t2);
  }
  FeMul(t2, t2, t1); // 99..0
  FeSquare(t3, t2); // 100..1
  for (i = 1; i < 100; i++) {
    // 199..100
    FeSquare(t3, t3);
  }
  FeMul(t2, t3, t2); // 199..0
  FeSquare(t2, t2); // 200..1
  for (i = 1; i < 50; i++) {
    // 249..50
    FeSquare(t2, t2);
  }
  FeMul(t1, t2, t1); // 249..0
  FeSquare(t1, t1); // 250..1
  for (i = 1; i < 5; i++) {
    // 254..5
    FeSquare(t1, t1);
  }
  FeMul(out, t1, t0); // 254..5,3,1,0
}