/* From B = a mod |n|, A = |n| it follows that
*
* 0 <= B < A,
- * X*a == B (mod |n|),
+ * sign*X*a == B (mod |n|),
* -sign*Y*a == A (mod |n|).
*/
/*
* 0 < B < A,
- * (*) X*a == B (mod |n|),
+ * (*) sign*X*a == B (mod |n|),
* -sign*Y*a == A (mod |n|)
*/
* i.e.
* -sign*Y*a - D*A == B (mod |n|).
* Similarly, (*) translates into
- * X*a == A (mod |n|).
+ * sign*X*a == A (mod |n|).
*
* Thus,
- * -sign*Y*a - D*X*a == B (mod |n|),
+ * -sign*Y*a - D*sign*X*a == B (mod |n|),
* i.e.
- * -sign*(Y + D*X)*a == B (mod |n|).
+ * -sign*(Y + D*X)*a == B (mod |n|).
*
* So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
- * X*a == B (mod |n|),
+ * sign*X*a == B (mod |n|),
* -sign*Y*a == A (mod |n|).
* Note that X and Y stay non-negative all the time.
*/
{
if (!BN_lshift1(tmp,X)) goto err;
}
- else if (BN_is_word(D,3))
- {
- if (!BN_lshift1(tmp,X)) goto err;
- if (!BN_add(tmp,tmp,X)) goto err;
- }
else if (BN_is_word(D,4))
{
if (!BN_lshift(tmp,X,2)) goto err;
}
+ else if (D->top == 1)
+ {
+ if (!BN_copy(tmp,X)) goto err;
+ if (!BN_mul_word(tmp,D->d[0])) goto err;
+ }
else
{
if (!BN_mul(tmp,D,X,ctx)) goto err;
}
/*
- * The while loop ends when
+ * The while loop (Euclid's algorithm) ends when
* A == gcd(a,n);
* we have
* -sign*Y*a == A (mod |n|),
{
/* Y*a == 1 (mod |n|) */
if (BN_ucmp(Y,n) < 0)
+ {
if (!BN_copy(R,Y)) goto err;
+ }
else
+ {
if (!BN_nnmod(R,Y,n,ctx)) goto err;
+ }
}
else
{
BN_CTX_end(ctx);
return(ret);
}
-