📄 function_lib_c.c
字号:
else
cf1 = t[1];
if ((aa += t[0]) < t[0])
cf1++;
NN_DigitMult (t, xi, y[j]);
if ((aa+=cf2) < cf2)
cf2 = t[1]+1;
else
cf2 = t[1];
if ((aa += t[0]) < t[0])
cf2++;
if(j)A[j-1]=aa;
}
cfLow+=cf1;
if(cfLow<cf1)cfHigh++;
cfLow+=cf2;
if(cfLow<cf2)cfHigh++;
A[digits-1]=cfLow;
cfLow=cfHigh;
cfHigh=0;
}
}
/*---------------------------------------------
step3:调整 */
if(cfLow!=0 || NN_Cmp(A,m,digits)>=0)
NN_Sub(_A,A,m,digits);
else NN_Assign(_A,A,digits);
}
/* Computes a = b - c. Returns borrow.
Lengths: a[digits], b[digits], c[digits].
*/
NN_DIGIT NN_Sub (a, b, c, digits)
NN_DIGIT *a, *b, *c;
UINT digits;
{
NN_DIGIT ai, borrow;
UINT i;
borrow = 0;
for (i = 0; i < digits; i++) {
if ((ai = b[i] - borrow) > (NN_DIGIT)(MAX_NN_DIGIT - borrow))
ai = MAX_NN_DIGIT - c[i];
else if ((ai -= c[i]) >(NN_DIGIT) (MAX_NN_DIGIT - c[i]))
borrow = 1;
else
borrow = 0;
a[i] = ai;
}
return (borrow);
}
/*--------------------------------------
Montgomery约化求A= w*(R逆) mod m
R=(2^32)^t;
注意 w被修改过,w的长度为m的两倍
---------------------------------------*/
void MontMod(BIG _A,BIG2 w,BIG m,
NN_DIGIT mp,INT digits)
{
void NN_DigitMult();
NN_DIGIT cf0;
NN_DIGIT t[2],c;
NN_DIGIT carry,*wi;
INT i,j;
cf0=0;
for(i=0;i<digits;i++)
{
c=w[i]*mp; /* mod b */
carry = 0;
wi=w+i;
for (j = 0; j < digits; j++,wi++) {
NN_DigitMult (t, c, m[j]);
*wi+=carry;
if (*wi < carry)
carry =t[1]+1;
else
carry = t[1];
if (((*wi) += t[0]) < t[0])
carry++;
}
/*
----------------------------------------------------
carry=LOW(A)
if( CF ) adjust
*/
if(carry)
for (j=digits+i;j<digits*2;j++)
{
w[j]+=carry;
if(w[j]>=carry){carry=0;break;};
carry=1;
}
cf0+=carry;
}
NN_Assign(w,w+digits,digits);
/*调整*/
if(cf0>0 || NN_Cmp(w,m,digits)>=0)
NN_Sub(_A,w,m,digits);
else NN_Assign(_A,w,digits);
}
/* Assigns a = 0.
Lengths: a[digits].
*/
void NN_AssignZero (a, digits)
NN_DIGIT *a;
UINT digits;
{
UINT i;
for (i = 0; i < digits; i++)
a[i]=0;
}
/* Returns the significant length of a in digits.
Lengths: a[digits].
*/
UINT NN_Digits (a, digits)
NN_DIGIT *a;
UINT digits;
{
INT i;
for (i = digits - 1; i >= 0; i--)
if (a[i])
break;
return (i + (INT)1);
}
/* Returns the significant length of a in bits, where a is a digit.
*/
UINT NN_DigitBits (a)
NN_DIGIT a;
{
UINT i;
for (i = 0; i < NN_DIGIT_BITS; i++, a >>= 1)
if (a == 0)
break;
return (i);
}
/* Computes a = b * 2^c (i.e., shifts left c bits), returning carry.
Lengths: a[digits], b[digits].
Requires c < NN_DIGIT_BITS.
*/
NN_DIGIT NN_LShift (a, b, c, digits)
NN_DIGIT *a, *b;
UINT c, digits;
{
NN_DIGIT bi, carry;
UINT i, t;
if (c >= NN_DIGIT_BITS)
return (0);
t = NN_DIGIT_BITS - c;
carry = 0;
for (i = 0; i < digits; i++) {
bi = b[i];
a[i] = (bi << c) | carry;
carry = c ? (bi >> t) : 0;
}
return (carry);
}
/* Computes a = c div 2^c (i.e., shifts right c bits), returning carry.
Lengths: a[digits], b[digits].
Requires: c < NN_DIGIT_BITS.
*/
NN_DIGIT NN_RShift (a, b, c, digits)
NN_DIGIT *a, *b;
UINT c, digits;
{
NN_DIGIT bi, carry;
INT i;
UINT t;
if (c >= NN_DIGIT_BITS)
return (0);
t = NN_DIGIT_BITS - c;
carry = 0;
for (i = digits - 1; i >= 0; i--) {
bi = b[i];
a[i] = (bi >> c) | carry;
carry = c ? (bi << t) : 0;
}
return (carry);
}
/* Sets a = b / c, where a and c are digits.
Lengths: b[2].
Assumes b[1] < c and HIGH_HALF (c) > 0. For efficiency, c should be
normalized.
*/
void NN_DigitDiv (a, b, c)
NN_DIGIT *a, b[2], c;
{
NN_DIGIT t[2], u, v;
NN_HALF_DIGIT aHigh, aLow, cHigh, cLow;
cHigh = HIGH_HALF (c);
cLow = LOW_HALF (c);
t[0] = b[0];
t[1] = b[1];
/* Underestimate high half of quotient and subtract.
*/
if (cHigh == MAX_NN_HALF_DIGIT)
aHigh = HIGH_HALF (t[1]);
else
aHigh = (NN_HALF_DIGIT)(t[1] /(NN_DIGIT) (cHigh + 1));
u = (NN_DIGIT)aHigh * (NN_DIGIT)cLow;
v = (NN_DIGIT)aHigh * (NN_DIGIT)cHigh;
if ((t[0] -= TO_HIGH_HALF (u)) >(NN_DIGIT) (MAX_NN_DIGIT - TO_HIGH_HALF (u)))
t[1]--;
t[1] -= HIGH_HALF (u);
t[1] -= v;
/* Correct estimate.
*/
while ((t[1] > cHigh) ||
((t[1] == cHigh) && (t[0] >=(NN_DIGIT) TO_HIGH_HALF (cLow)))) {
if ((t[0] -= TO_HIGH_HALF (cLow)) >
(NN_DIGIT)( MAX_NN_DIGIT - TO_HIGH_HALF (cLow)))
t[1]--;
t[1] -= cHigh;
aHigh++;
}
/* Underestimate low half of quotient and subtract.
*/
if (cHigh == MAX_NN_HALF_DIGIT)
aLow = LOW_HALF (t[1]);
else
aLow =
(NN_HALF_DIGIT)
((NN_DIGIT)(TO_HIGH_HALF (t[1]) + HIGH_HALF (t[0])) /(NN_DIGIT) (cHigh + 1));
u = (NN_DIGIT)aLow * (NN_DIGIT)cLow;
v = (NN_DIGIT)aLow * (NN_DIGIT)cHigh;
if ((t[0] -= u) >(NN_DIGIT) (MAX_NN_DIGIT - u))
t[1]--;
if ((t[0] -= TO_HIGH_HALF (v)) >(NN_DIGIT) (MAX_NN_DIGIT - TO_HIGH_HALF (v)))
t[1]--;
t[1] -= HIGH_HALF (v);
/* Correct estimate.
*/
while ((t[1] > 0) || ((t[1] == 0) && t[0] >= c)) {
if ((t[0] -= c) >(NN_DIGIT) (MAX_NN_DIGIT - c))
t[1]--;
aLow++;
}
*a = TO_HIGH_HALF (aHigh) + aLow;
}
/* Computes a = b - c*d, where c is a digit. Returns borrow.
Lengths: a[digits], b[digits], d[digits].
*/
NN_DIGIT NN_SubDigitMult (a, b, c, d, digits)
NN_DIGIT *a, *b, c, *d;
UINT digits;
{
void NN_DigitMult();
NN_DIGIT borrow, t[2];
UINT i;
if (c == 0)
return (0);
borrow = 0;
for (i = 0; i < digits; i++) {
NN_DigitMult (t, c, d[i]);
if ((a[i] = b[i] - borrow) >(NN_DIGIT) (MAX_NN_DIGIT - borrow))
borrow = 1;
else
borrow = 0;
if ((a[i] -= t[0]) >(NN_DIGIT) (MAX_NN_DIGIT - t[0]))
borrow++;
borrow += t[1];
}
return (borrow);
}
/*
计算m'=-(m[0]逆) (mod 2^16)
此函数值为后面的约化函数使用
函数接口如下：
输入：大数 BIG _m
输出：一个整数，其值为_m[0]的逆，即其值与_m[0]的乘积模2^16余1
说明：
此函数调用很少，无须汇编优化
兼容性：
C语言可移植
*/
NN_DIGIT m2mp(BIG _m)
{
NN_DIGIT m0,mp,a,i;
m0=_m[0];
a=_m[0];
mp=1;
for(i=2;i!=(NN_DIGIT)0;i<<=1)
{
m0<<=1;
if(((m0+a)&i)==0){
a+=m0;
mp|=i;
}
}
return (NN_DIGIT)((NN_DIGIT)0-mp);
}
/* Computes a = b * c.
Lengths: a[2*digits], b[digits], c[digits].
Assumes digits < MAX_NN_DIGITS.
*/
void NN_Mult (a, b, c, digits)
NN_DIGIT *a, *b, *c;
UINT digits;
{
NN_DIGIT t[2*MAX_NN_DIGITS];
UINT bDigits, cDigits, i;
NN_DIGIT NN_AddDigitMult();
NN_AssignZero (t, 2 * digits);
bDigits = NN_Digits (b, digits);
cDigits = NN_Digits (c, digits);
for (i = 0; i < bDigits; i++)
t[i+cDigits] += NN_AddDigitMult (&t[i], &t[i], b[i], c, cDigits);
NN_Assign (a, t, 2 * digits);
}
/* Computes a = b * c, where b and c are digits.
Lengths: a[2].
*/
void NN_DigitMult (a, b, c)
NN_DIGIT a[2], b, c;
{
NN_DIGIT t, u;
NN_HALF_DIGIT bHigh, bLow, cHigh, cLow;
bHigh = HIGH_HALF (b);
bLow = LOW_HALF (b);
cHigh = HIGH_HALF (c);
cLow = LOW_HALF (c);
a[0] = (NN_DIGIT)bLow * (NN_DIGIT)cLow;
t = (NN_DIGIT)bLow * (NN_DIGIT)cHigh;
u = (NN_DIGIT)bHigh * (NN_DIGIT)cLow;
a[1] = (NN_DIGIT)bHigh * (NN_DIGIT)cHigh;
if ((t += u) < u)
a[1] += TO_HIGH_HALF (1);
u = TO_HIGH_HALF (t);
if ((a[0] += u) < u)
a[1]++;
a[1] += HIGH_HALF (t);
}
/* Computes a = b + c*d, where c is a digit. Returns carry.
Lengths: a[digits], b[digits], d[digits].
*/
NN_DIGIT NN_AddDigitMult (a, b, c, d, digits)
NN_DIGIT *a, *b, c, *d;
UINT digits;
{
NN_DIGIT carry, t[2];
UINT i;
if (c == 0)
return (0);
carry = 0;
for (i = 0; i < digits; i++) {
NN_DigitMult (t, c, d[i]);
if ((a[i] = b[i] + carry) < carry)
carry = 1;
else
carry = 0;
if ((a[i] += t[0]) < t[0])
carry++;
carry += t[1];
}
return (carry);
}
/* Compute a = 1/b mod c, assuming inverse exists.
Lengths: a[digits], b[digits], c[digits].
Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS.
*/
void NN_ModInv (a, b, c, digits)
NN_DIGIT *a, *b, *c;
UINT digits;
{
NN_DIGIT q[MAX_NN_DIGITS], t1[MAX_NN_DIGITS], t3[MAX_NN_DIGITS],
u1[MAX_NN_DIGITS], u3[MAX_NN_DIGITS], v1[MAX_NN_DIGITS],
v3[MAX_NN_DIGITS], w[2*MAX_NN_DIGITS];
INT u1Sign;
NN_DIGIT NN_Add();
/* Apply extended Euclidean algorithm, modified to avoid negative
numbers.
*/
NN_ASSIGN_DIGIT (u1, 1, digits);
NN_AssignZero (v1, digits);
NN_Assign (u3, b, digits);
NN_Assign (v3, c, digits);
u1Sign = 1;
while (! NN_Zero (v3, digits)) {
NN_Div (q, t3, u3, digits, v3, digits);
NN_Mult (w, q, v1, digits);
NN_Add (t1, u1, w, digits);
NN_Assign (u1, v1, digits);
NN_Assign (v1, t1, digits);
NN_Assign (u3, v3, digits);
NN_Assign (v3, t3, digits);
u1Sign = -u1Sign;
}
/* Negate result if sign is negative.
*/
if (u1Sign < 0)
NN_Sub (a, c, u1, digits);
else
NN_Assign (a, u1, digits);
}
/*Returns the significant length of a in bytes.
Lengths:a[bytes].
*/
unsigned char NN_Bytes(a,bytes)
unsigned char *a;
int bytes;
{
int i;
for(i=bytes-1;i>=0;i--)
{ if(a[i])
break;
}
return (unsigned char)(i+(int)1);
}
/* Computes a = b + c. Returns carry.
Lengths: a[digits], b[digits], c[digits].
*/
NN_DIGIT NN_Add (a, b, c, digits)
NN_DIGIT *a, *b, *c;
UINT digits;
{
NN_DIGIT ai, carry;
UINT i;
carry = 0;
for (i = 0; i < digits; i++) {
if ((ai = b[i] + carry) < carry)
ai = c[i];
else if ((ai += c[i]) < c[i])
carry = 1;
else
carry = 0;
a[i] = ai;
}
return (carry);
}
/* 生产随机大数 */
void erandbig(BIG a,INT ww)
{
extern NN_DIGIT exrandx();
INT i;
for(i=0;i<ww;i++)a[i]=exrandx();
}
/**********************************************
混同余生产随机数
X(i+1)=0x5deece66d*X(i)+11;
**********************************************/
static NN_DIGIT rand_seed[4]={1,2,3,4};
static NN_DIGIT rand_a[2]={0xdeece66d,0x5};
static NN_DIGIT rand_c[2]={11,0};
NN_DIGIT exrandx()
{
NN_DIGIT a;
void NN_Mult();
NN_DIGIT NN_Add();
NN_Mult(rand_seed,rand_seed,rand_a,2);
NN_Add(rand_seed,rand_seed,rand_c,2);
a=(rand_seed[0]>>16)^(rand_seed[1]<<16);
return a;
}
void InitData( )
{
static short highseed = 0x5533 ;
rand_seed[1] = highseed;
rand_seed[0] = time(NULL);
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -