secp256k1FeSqrt static method

Implementation

static int secp256k1FeSqrt(Secp256k1Fe r, Secp256k1Fe a) {
  Secp256k1Fe x2 = Secp256k1Fe(),
      x3 = Secp256k1Fe(),
      x6 = Secp256k1Fe(),
      x9 = Secp256k1Fe(),
      x11 = Secp256k1Fe(),
      x22 = Secp256k1Fe(),
      x44 = Secp256k1Fe(),
      x88 = Secp256k1Fe(),
      x176 = Secp256k1Fe(),
      x220 = Secp256k1Fe(),
      x223 = Secp256k1Fe(),
      t1 = Secp256k1Fe();
  int j, ret;

  _cond(r != a, "secp256k1FeSqrt");

  secp256k1FeSqr(x2, a);
  secp256k1FeMul(x2, x2, a);

  secp256k1FeSqr(x3, x2);
  secp256k1FeMul(x3, x3, a);
  x6 = x3.clone();
  for (j = 0; j < 3; j++) {
    secp256k1FeSqr(x6, x6);
  }
  secp256k1FeMul(x6, x6, x3);

  x9 = x6.clone();
  for (j = 0; j < 3; j++) {
    secp256k1FeSqr(x9, x9);
  }
  secp256k1FeMul(x9, x9, x3);

  x11 = x9.clone();
  for (j = 0; j < 2; j++) {
    secp256k1FeSqr(x11, x11);
  }
  secp256k1FeMul(x11, x11, x2);

  x22 = x11.clone();
  for (j = 0; j < 11; j++) {
    secp256k1FeSqr(x22, x22);
  }
  secp256k1FeMul(x22, x22, x11);

  x44 = x22.clone();
  for (j = 0; j < 22; j++) {
    secp256k1FeSqr(x44, x44);
  }
  secp256k1FeMul(x44, x44, x22);

  x88 = x44.clone();
  for (j = 0; j < 44; j++) {
    secp256k1FeSqr(x88, x88);
  }
  secp256k1FeMul(x88, x88, x44);

  x176 = x88.clone();
  for (j = 0; j < 88; j++) {
    secp256k1FeSqr(x176, x176);
  }
  secp256k1FeMul(x176, x176, x88);

  x220 = x176.clone();
  for (j = 0; j < 44; j++) {
    secp256k1FeSqr(x220, x220);
  }
  secp256k1FeMul(x220, x220, x44);

  x223 = x220.clone();
  for (j = 0; j < 3; j++) {
    secp256k1FeSqr(x223, x223);
  }
  secp256k1FeMul(x223, x223, x3);

  /// The final result is then assembled using a sliding window over the blocks.

  t1 = x223.clone();
  for (j = 0; j < 23; j++) {
    secp256k1FeSqr(t1, t1);
  }
  secp256k1FeMul(t1, t1, x22);
  for (j = 0; j < 6; j++) {
    secp256k1FeSqr(t1, t1);
  }
  secp256k1FeMul(t1, t1, x2);
  secp256k1FeSqr(t1, t1);
  secp256k1FeSqr(r, t1);

  /// Check that a square root was actually calculated

  secp256k1FeSqr(t1, r);
  ret = secp256k1FeEqual(t1, a);

  /// verify
  if (ret == 0) {
    secp256k1FeNegate(t1, t1, 1);
    secp256k1FeNormalizeVar(t1);
    _cond(secp256k1FeEqual(t1, a) == 1, "secp256k1FeSqrt");
  }
  return ret;
}