* guaranteed to be either exact or one less than the correct value. This follows from fact that
     * floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not quite
     * trivial.
     */
    long quotient = ((dividend >>> 1) / divisor) << 1;
    long rem = dividend - quotient * divisor;
    return quotient + (compare(rem, divisor) >= 0 ? 1 : 0);
  }

extended binary GCD algorithm described in the Handbook of // Applied Cryptography, Algorithm 14.61, adapted by BoringSSL to bound // coefficients and avoid negative numbers. For more details and proof of // correctness, see https://github.com/mit-plv/fiat-crypto/pull/333/files. // // Following the proof linked in the PR above, the changes are: // // 1. Negate [B] and [C] so they are positive. The invariant now involves a // subtraction. // 2. If step 2 (both [x] and [y] are even) runs, abort immediately....