invert method

void invert(
  1. Element z
)

Invert sets v = 1/z mod p, and returns v.

If z == 0, Invert returns v = 0.

Implementation

void invert(Element z) {
  // Inversion is implemented as exponentiation with exponent p − 2. It uses the
  // same sequence of 255 squarings and 11 multiplications as [Curve25519].
  Element z2 = Element.feZero();
  Element z9 = Element.feZero();
  Element z11 = Element.feZero();
  Element z2_5_0 = Element.feZero();
  Element z2_10_0 = Element.feZero();
  Element z2_20_0 = Element.feZero();
  Element z2_50_0 = Element.feZero();
  Element z2_100_0 = Element.feZero();
  Element t = Element.feZero();

  z2.square(z); // 2
  t.square(z2); // 4
  t.square(t); // 8
  z9.multiply(t, z); // 9
  z11.multiply(z9, z2); // 11
  t.square(z11); // 22
  z2_5_0.multiply(t, z9); // 31 = 2^5 - 2^0

  t.square(z2_5_0); // 2^6 - 2^1
  for (int i = 0; i < 4; i++) {
    t.square(t); // 2^10 - 2^5
  }
  z2_10_0.multiply(t, z2_5_0); // 2^10 - 2^0

  t.square(z2_10_0); // 2^11 - 2^1
  for (int i = 0; i < 9; i++) {
    t.square(t); // 2^20 - 2^10
  }
  z2_20_0.multiply(t, z2_10_0); // 2^20 - 2^0

  t.square(z2_20_0); // 2^21 - 2^1
  for (int i = 0; i < 19; i++) {
    t.square(t); // 2^40 - 2^20
  }
  t.multiply(t, z2_20_0); // 2^40 - 2^0

  t.square(t); // 2^41 - 2^1
  for (int i = 0; i < 9; i++) {
    t.square(t); // 2^50 - 2^10
  }
  z2_50_0.multiply(t, z2_10_0); // 2^50 - 2^0

  t.square(z2_50_0); // 2^51 - 2^1
  for (int i = 0; i < 49; i++) {
    t.square(t); // 2^100 - 2^50
  }
  z2_100_0.multiply(t, z2_50_0); // 2^100 - 2^0

  t.square(z2_100_0); // 2^101 - 2^1
  for (int i = 0; i < 99; i++) {
    t.square(t); // 2^200 - 2^100
  }
  t.multiply(t, z2_100_0); // 2^200 - 2^0

  t.square(t); // 2^201 - 2^1
  for (int i = 0; i < 49; i++) {
    t.square(t); // 2^250 - 2^50
  }
  t.multiply(t, z2_50_0); // 2^250 - 2^0

  t.square(t); // 2^251 - 2^1
  t.square(t); // 2^252 - 2^2
  t.square(t); // 2^253 - 2^3
  t.square(t); // 2^254 - 2^4
  t.square(t); // 2^255 - 2^5

  multiply(t, z11); // 2^255 - 21
}