- /* (D, M) := (A/B, A%B) ... */
- if (BN_num_bits(A) == BN_num_bits(B))
- {
- if (!BN_one(D)) goto err;
- if (!BN_sub(M,A,B)) goto err;
+ /* Same for A and Y. Afterwards, (2) still holds. */
+ shift = 0;
+ while (!BN_is_bit_set(A, shift)) /* note that 0 < A */
+ {
+ shift++;
+
+ if (BN_is_odd(Y))
+ {
+ if (!BN_uadd(Y, Y, n)) goto err;
+ }
+ /* now Y is even */
+ if (!BN_rshift1(Y, Y)) goto err;
+ }
+ if (shift > 0)
+ {
+ if (!BN_rshift(A, A, shift)) goto err;
+ }
+
+
+ /* We still have (1) and (2).
+ * Both A and B are odd.
+ * The following computations ensure that
+ *
+ * 0 <= B < |n|,
+ * 0 < A < |n|,
+ * (1) -sign*X*a == B (mod |n|),
+ * (2) sign*Y*a == A (mod |n|),
+ *
+ * and that either A or B is even in the next iteration.
+ */
+ if (BN_ucmp(B, A) >= 0)
+ {
+ /* -sign*(X + Y)*a == B - A (mod |n|) */
+ if (!BN_uadd(X, X, Y)) goto err;
+ /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that
+ * actually makes the algorithm slower */
+ if (!BN_usub(B, B, A)) goto err;
+ }
+ else
+ {
+ /* sign*(X + Y)*a == A - B (mod |n|) */
+ if (!BN_uadd(Y, Y, X)) goto err;
+ /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */
+ if (!BN_usub(A, A, B)) goto err;
+ }