sqrt method

@override ECFieldElement? sqrt()

return a sqrt root - the routine verifies that the calculation returns the right value - if none exists it returns null.

Implementation

@override
ECFieldElement? sqrt() {
  if (!_testBit(q!, 0)) {
    throw UnimplementedError('Not implemented yet');
  }

  // p % 4 == 3
  if (_testBit(q!, 1)) {
    // z = g^(u+1) + p, p = 4u + 3
    var z = ECFieldElement(q, x!.modPow((q! >> 2) + BigInt.one, q!));
    return z.square() == this ? z : null;
  }

  // p % 4 == 1
  var qMinusOne = q! - BigInt.one;

  var legendreExponent = qMinusOne >> 1;
  if (x!.modPow(legendreExponent, q!) != BigInt.one) {
    return null;
  }

  var u = qMinusOne >> 2;
  var k = (u << 1) + BigInt.one;

  var Q = x!;
  var fourQ = (Q >> 2) % q!;

  BigInt U, V;
  var rand = SecureRandom();
  do {
    BigInt? P;
    do {
      P = rand.nextBigInteger(q!.bitLength);
    } while ((P >= q!) ||
        (((P * P) - fourQ).modPow(legendreExponent, q!) != qMinusOne));

    var result = _lucasSequence(q!, P, Q, k);
    U = result[0];
    V = result[1];

    if (((V * V) % q!) == fourQ) {
      // Integer division by 2, mod q
      if (_testBit(V, 0)) {
        V = V + q!;
      }

      V = V >> 1;

      //assert V.multiply(V).mod(q).equals(x);

      return ECFieldElement(q, V);
    }
  } while ((U == BigInt.one) || (U == qMinusOne));

  return null;
}