- { if (!BN_mul(a,x,y)) goto err; }
- if (!BN_rshift(d,a,nb)) goto err;
- if (!BN_mul(b,d,i)) goto err;
- if (!BN_rshift(c,b,nb)) goto err;
- if (!BN_mul(b,m,c)) goto err;
- if (!BN_sub(r,a,b)) goto err;
+ a=x; /* Just do the mod */
+
+ BN_div_recp(NULL,r,a,recp,ctx);
+ ret=1;
+err:
+ BN_CTX_end(ctx);
+ return(ret);
+ }
+
+int BN_div_recp(BIGNUM *dv, BIGNUM *rem, BIGNUM *m, BN_RECP_CTX *recp,
+ BN_CTX *ctx)
+ {
+ int i,j,ret=0,ex;
+ BIGNUM *a,*b,*d,*r;
+
+ BN_CTX_start(ctx);
+ a=BN_CTX_get(ctx);
+ b=BN_CTX_get(ctx);
+ if (dv != NULL)
+ d=dv;
+ else
+ d=BN_CTX_get(ctx);
+ if (rem != NULL)
+ r=rem;
+ else
+ r=BN_CTX_get(ctx);
+ if (a == NULL || b == NULL || d == NULL || r == NULL) goto err;
+
+ if (BN_ucmp(m,&(recp->N)) < 0)
+ {
+ BN_zero(d);
+ BN_copy(r,m);
+ BN_CTX_end(ctx);
+ return(1);
+ }
+
+ /* We want the remainder
+ * Given input of ABCDEF / ab
+ * we need multiply ABCDEF by 3 digests of the reciprocal of ab
+ *
+ */
+ i=BN_num_bits(m);
+ if (i%2) i--;
+
+ j=recp->num_bits*2;
+ if (j > i)
+ {
+ i=j;
+ ex=0;
+ }
+ else
+ {
+ ex=(i-j)/2;
+ }
+
+ j=i/2;
+
+ if (i != recp->shift)
+ recp->shift=BN_reciprocal(&(recp->Nr),&(recp->N),
+ i,ctx);
+
+ if (!BN_rshift(a,m,j-ex)) goto err;
+ if (!BN_mul(b,a,&(recp->Nr),ctx)) goto err;
+ if (!BN_rshift(d,b,j+ex)) goto err;
+ d->neg=0;
+ if (!BN_mul(b,&(recp->N),d,ctx)) goto err;
+ if (!BN_usub(r,m,b)) goto err;
+ r->neg=0;
+