mrecgf2m.c

miracl-大数运算库,大家使用有什么问题请多多提意见

#endif

    if (x==NULL || y==NULL)
    {
        zero(w);
        return;
    }

    if (x==y)
    {
        modsquare2(_MIPP_ x,w);
        return;
    }

    if (y->len==0)
    {
        zero(w);
        return;
    }

    if (y->len==1)
    {
        if (y->w[0]==1)
        {
            copy(x,w);
            return;
        }
    } 
    
    multiply2(_MIPP_ x,y,mr_mip->w0);
    reduce2(_MIPP_ mr_mip->w0,mr_mip->w0);
    copy(mr_mip->w0,w);
}

#endif
#endif

/* Will be *much* faster if M,A,(B and C) are all odd */

void sqroot2(_MIPD_ big x,big y)
{ 
    int i,M,A,B,C;
    int m,k,n,h,s,a,aw,ab,bw,bb,cw,cb;
 #if MIRACL != 32
    int mm,j;
 #endif
    mr_small *wk,w,we,wo;
    BOOL slow;
    static const mr_small odds[16]=
    {0,0,1,1,0,0,1,1,2,2,3,3,2,2,3,3};
    static const mr_small evens[16]=
    {0,1,0,1,2,3,2,3,0,1,0,1,2,3,2,3};

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    M=mr_mip->M;
    A=mr_mip->AA;
    if (A==0)
    {
        mr_berror(_MIPP_ MR_ERR_NO_BASIS);
        return;
    }
    B=mr_mip->BB;
    C=mr_mip->CC;

    slow=FALSE;
    if (B)
    {
        if (M%2!=1 || A%2!=1 || B%2!=1 || C%2!=1) slow=TRUE;
    }
    else
    {
        if (M%2!=1 || A%2!=1) slow=TRUE;
    }

    if (slow)
    {
        copy(x,y);
        for (i=1;i<mr_mip->M;i++)
            modsquare2(_MIPP_ y,y);
        return;
    }

/* M, A (B and C) are all odd - so use fast
   Fong, Hankerson, Lopez and Menezes method */

    if (x==y)
    {
        copy (x,mr_mip->w0);
        wk=mr_mip->w0->w;
    }
    else
    {
        wk=x->w;
    }
    zero(y);

    k=1+(M/MIRACL);
    h=(k+1)/2;

    a=(A+1)/2;
    aw=a/MIRACL;
    ab=a%MIRACL;

    if (B)
    {
        a=(B+1)/2;
        bw=a/MIRACL;
        bb=a%MIRACL;

        a=(C+1)/2;
        cw=a/MIRACL;
        cb=a%MIRACL;
    }

    y->len=k;
    s=h*MIRACL-1-(M-1)/2;

    for (i=0;i<k;i++)
    {
        n=i/2;
        w=wk[i];
       
#if MIRACL == 32
        m=w&0xF;
        we=evens[m];
        wo=odds[m];
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<2;
        wo|=odds[m]<<2;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<4;
        wo|=odds[m]<<4;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<6;
        wo|=odds[m]<<6;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<8;
        wo|=odds[m]<<8;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<10;
        wo|=odds[m]<<10;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<12;
        wo|=odds[m]<<12;
        w>>=4;

        m=w;
        we|=evens[m]<<14;
        wo|=odds[m]<<14;

#else
        mm=0; we=wo=0;
        for (j=0;j<MIRACL/4;j++)
        {
            m=w&0xF; 
            we|=(evens[m]<<mm);
            wo|=(odds[m]<<mm);
            mm+=2; w>>=4;
        }
#endif
        i++;
        if (i<k)
        {
            w=wk[i];
#if MIRACL == 32
        m=w&0xF;
        we|=evens[m]<<16;
        wo|=odds[m]<<16;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<18;
        wo|=odds[m]<<18;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<20;
        wo|=odds[m]<<20;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<22;
        wo|=odds[m]<<22;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<24;
        wo|=odds[m]<<24;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<26;
        wo|=odds[m]<<26;
        w>>=4;

        m=w&0xF;
        we|=evens[m]<<28;
        wo|=odds[m]<<28;
        w>>=4;

        m=w;
        we|=evens[m]<<30;
        wo|=odds[m]<<30;
#else
            for (j=0;j<MIRACL/4;j++)
            {
                m=w&0xF; 
                we|=(evens[m]<<mm);
                wo|=(odds[m]<<mm);
                mm+=2; w>>=4;
            }
#endif
        }
        y->w[n]^=we; 

        if (s==0) y->w[h+n]=wo;
        else
        {
            y->w[h+n-1]^=wo<<(MIRACL-s); 
            y->w[h+n]^=wo>>s;     /* abutt odd bits to even */
        }
        if (ab==0) y->w[n+aw]^=wo;
        else
        {
            y->w[n+aw]^=wo<<ab; 
            y->w[n+aw+1]^=wo>>(MIRACL-ab);
        }
        if (B)
        {
            if (bb==0) y->w[n+bw]^=wo;
            else
            {
                y->w[n+bw]^=wo<<bb; 
                y->w[n+bw+1]^=wo>>(MIRACL-bb);
            }
            if (cb==0) y->w[n+cw]^=wo;
            else
            {
                y->w[n+cw]^=wo<<cb; 
                y->w[n+cw+1]^=wo>>(MIRACL-cb);
            }
        }
    }

    if (y->w[k-1]==0) mr_lzero(y);
}

void power2(_MIPD_ big x,int m,big w)
{ /* w=x^m mod f. Could be optimised a lot, but not time critical for me */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    copy(x,mr_mip->w1);
    
    convert(_MIPP_ 1,w);
    forever
    {
        if (m%2!=0)
            modmult2(_MIPP_ w,mr_mip->w1,w);
        m/=2;
        if (m==0) break;
        modsquare2(_MIPP_ mr_mip->w1,mr_mip->w1);
    }
}

/* Euclidean Algorithm */

BOOL inverse2(_MIPD_ big x,big w)
{
    mr_small bit;
    int i,j,n,n3,k,n4,mb,mw;
    big t;
    BOOL newword;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (size(x)==0) return FALSE;
 
    convert(_MIPP_ 1,mr_mip->w1);     
    zero(mr_mip->w2);                 
    copy(x,mr_mip->w3);               
    copy(mr_mip->modulus,mr_mip->w4); 

    n3=numbits(mr_mip->w3);
    n4=mr_mip->M+1;

    while (n3!=1)
    {
        j=n3-n4;
        
        if (j<0)
        { 
            t=mr_mip->w3; mr_mip->w3=mr_mip->w4; mr_mip->w4=t;
            t=mr_mip->w1; mr_mip->w1=mr_mip->w2; mr_mip->w2=t;
            j=-j; n=n3; n3=n4; n4=n;
        }
       
        mw=j/MIRACL; mb=j%MIRACL;
        
        if (n3<MIRACL)
        {
            mr_mip->w3->w[0]^=mr_mip->w4->w[0]<<mb;
            n3--; 
            
            bit=((mr_small)1<<((n3-1)%MIRACL));

            while (!(mr_mip->w3->w[0]&bit))
            {
                n3--;
                bit>>=1;
            }
        }
        else
        {
            k=mr_mip->w3->len;
            if (mb==0)
            {
                for (i=mw;i<k;i++)
                {
                    mr_mip->w3->w[i]^=mr_mip->w4->w[i-mw];
                }
            }
            else
            {
                mr_mip->w3->w[mw]^=mr_mip->w4->w[0]<<mb;
                for (i=mw+1;i<k;i++)
                {
                    mr_mip->w3->w[i]^=( (mr_mip->w4->w[i-mw]<<mb) | (mr_mip->w4->w[i-mw-1]>>(MIRACL-mb)));
                }
            }

            newword=FALSE;
            while (mr_mip->w3->w[k-1]==0) {k--; newword=TRUE;}
            
            if (newword)
            {           
                bit=TOPBIT;
                n3=k*MIRACL;
            }
            else
            {
                n3--;
                bit=((mr_small)1<<((n3-1)%MIRACL));
            }
            while (!(mr_mip->w3->w[k-1]&bit))
            {
                n3--;
                bit>>=1;         
            }
            mr_mip->w3->len=k;
        }

        k=mr_mip->w2->len+mw+1;
        if ((int)mr_mip->w1->len>k) k=mr_mip->w1->len;
        
        if (mb==0)
        {
            for (i=mw;i<k;i++)
            {
                mr_mip->w1->w[i]^=mr_mip->w2->w[i-mw];
            }
        }
        else
        {
            mr_mip->w1->w[mw]^=mr_mip->w2->w[0]<<mb;
            for (i=mw+1;i<k;i++)
            {
                mr_mip->w1->w[i]^=((mr_mip->w2->w[i-mw]<<mb) | (mr_mip->w2->w[i-mw-1]>>(MIRACL-mb)));
            }
        }  
        while (mr_mip->w1->w[k-1]==0) k--;
        mr_mip->w1->len=k;
    }

    copy(mr_mip->w1,w);
    return TRUE;
}

/* Schroeppel, Orman, O'Malley, Spatscheck    *
 * "Almost Inverse" algorithm, Crypto '95     *
 * More optimization here and in-lining would *
 * speed up AFFINE mode. I observe that       *
 * pentanomials would be more efficient if C  *
 * were greater                               */

/*
BOOL inverse2(_MIPD_ big x,big w)
{
    mr_small lsw,*gw;
    int i,n,bits,step,n3,n4,k;
    int k1,k2,k3,k4,ls1,ls2,ls3,ls4,rs1,rs2,rs3,rs4;
    int M,A,B,C;
    big t;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (size(x)==0) return FALSE;

    M=mr_mip->M;
    A=mr_mip->AA;
	if (A==0)
	{
        mr_berror(_MIPP_ MR_ERR_NO_BASIS);
        return FALSE;
	}
 
    B=mr_mip->BB;
    C=mr_mip->CC;
    convert(_MIPP_ 1,mr_mip->w1);     
    zero(mr_mip->w2);                 
    copy(x,mr_mip->w3);               
    copy(mr_mip->modulus,mr_mip->w4); 

    bits=zerobits(mr_mip->w3);
    shiftrightbits(mr_mip->w3,bits);
    k=bits;    
    n3=numbits(mr_mip->w3);
    n4=M+1;

    if (n3>1) forever
    {
        if (n3<n4)
        { 
            t=mr_mip->w3; mr_mip->w3=mr_mip->w4; mr_mip->w4=t;
            t=mr_mip->w1; mr_mip->w1=mr_mip->w2; mr_mip->w2=t;
            n=n3; n3=n4; n4=n;
        }
        
        add2(mr_mip->w3,mr_mip->w4,mr_mip->w3); 
 
        add2(mr_mip->w1,mr_mip->w2,mr_mip->w1);

        if (n3==n4) n3=numbits(mr_mip->w3);
        bits=zerobits(mr_mip->w3);
        k+=bits;    
        n3-=bits;
        if (n3==1) break;
        shiftrightbits(mr_mip->w3,bits);
        shiftleftbits(mr_mip->w2,bits);
   }

    copy(mr_mip->w1,w);

    if (k==0) 
    {
        mr_lzero(w);
        return TRUE;
    }
    step=MIRACL;

    if (A<MIRACL) step=A;
    
    k1=1+M/MIRACL;  
    rs1=M%MIRACL;
    ls1=MIRACL-rs1;

    k2=1+A/MIRACL;  
    rs2=A%MIRACL;
    ls2=MIRACL-rs2;

    if (B)
    { 
        if (C<MIRACL) step=C;

        k3=1+B/MIRACL;
        rs3=B%MIRACL;
        ls3=MIRACL-rs3;

        k4=1+C/MIRACL;
        rs4=C%MIRACL;
        ls4=MIRACL-rs4;
    }

    gw=w->w;
    while (k>0)
    {
        if (k>step) n=step;
        else        n=k;
 
        if (n==MIRACL) lsw=gw[0];
        else           lsw=gw[0]&(((mr_small)1<<n)-1);

        w->len=k1;
        if (rs1==0) gw[k1-1]^=lsw;
        else
        {
            w->len++;
            gw[k1]^=(lsw>>ls1);
            gw[k1-1]^=(lsw<<rs1);
        }
        if (rs2==0) gw[k2-1]^=lsw;
        else
        {
            gw[k2]^=(lsw>>ls2);
            gw[k2-1]^=(lsw<<rs2);
        }
        if (B)
        {
            if (rs3==0) gw[k3-1]^=lsw;
            else
            {
                gw[k3]^=(lsw>>ls3);
                gw[k3-1]^=(lsw<<rs3);
            }
            if (rs4==0) gw[k4-1]^=lsw;
            else
            {
                gw[k4]^=(lsw>>ls4);
                gw[k4-1]^=(lsw<<rs4);
            }
        }
        shiftrightbits(w,n);
        k-=n;
    }
    mr_lzero(w);
    return TRUE;
}

*/

BOOL multi_inverse2(_MIPD_ int m,big *x,big *w)
{ /* find w[i]=1/x[i] mod f, for i=0 to m-1 */
    int i;
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (m==0) return TRUE;
    if (m<0) return FALSE;

    if (x==w)
    {
        mr_berror(_MIPP_ MR_ERR_BAD_PARAMETERS);
        return FALSE;
    }
    if (m==1)
    {
        inverse2(_MIPP_ x[0],w[0]);
        return TRUE;