mrgf2m.c

miracl大数库 miracl大数库 miracl大数库

            return;
        }
    }
    if (n%2==0)
    {
        md=nd=n;
        md2=nd2=n/2;
    }
    else
    {
        nd=n+1;
        md=n-1;
        nd2=nd/2; md2=md/2;
    }

    for (m=0;m<nd2;m++)
    {
        z[m]=x[m];
        z[nd2+m]=y[m];
    }
    for (m=0;m<md2;m++)
    {
        z[m]^=x[nd2+m];
        z[nd2+m]^=y[nd2+m];
    }

    karmul2(nd2,&t[nd],z,&z[nd2],t); 
    karmul2(nd2,&t[nd],x,y,z);  

    for (m=0;m<nd;m++) t[m]^=z[m];

    karmul2(md2,&t[nd],&x[nd2],&y[nd2],&z[nd]);

    for (m=0;m<md;m++) t[m]^=z[nd+m];
    for (m=0;m<nd;m++) z[nd2+m]^=t[m];
}

#endif

/* this is time-critical, so use karatsuba here, since addition is cheap *
 * and easy (no carries to worry about...)                               */

/* #define CLAIRE */

void multiply2(_MIPD_ big x,big y,big w)
{

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

#ifdef MR_COMBA2
    comba_mult2(_MIPP_ x,y,w);
    return;
#else
    int i,j,xl,yl,ml;
#ifdef CLAIRE
    int d;
    mr_small hi,lo;
#endif
    mr_small p,q;

    big w0=mr_mip->w0;

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

    xl=x->len;
    yl=y->len;
    zero(w0);

#ifdef CLAIRE

/* Comba method */

    w0->len=xl+yl;
    d=1+mr_mip->M/MIRACL;
    hi=lo=0;
    for (i=0;i<d;i++)
    {
        for (j=0;j<=i;j++)
        {
            q=mr_mul2(x->w[j],y->w[i-j],&p);
            hi^=q; lo^=p;
        }
        w0->w[i]=lo; lo=hi; hi=0;
    }
    for (i=d;i<2*d-1;i++)
    {
        for (j=i-d+1;j<d;j++)
        {
            q=mr_mul2(x->w[j],y->w[i-j],&p);
            hi^=q; lo^=p;
        }
        w0->w[i]=lo; lo=hi; hi=0;
    }
    w0->w[2*d-1]=lo;
    mr_lzero(w0);
    copy(w0,w);

#else

/* recommended method as mr_mul2 is so slow... */

    if (xl>=MR_KARATSUBA && yl>=MR_KARATSUBA)
    { 
        if (xl>yl) ml=xl;
        else       ml=yl;
     
        karmul2(ml,mr_mip->w7->w,x->w,y->w,w0->w);

        mr_mip->w7->len=w0->len=2*ml+1;
        mr_lzero(w0);
        mr_lzero(mr_mip->w7);    
        copy(w0,w);
        return;
    }

    w0->len=xl+yl;
    for (i=0;i<xl;i++)
    { 
        for (j=0;j<yl;j++)
        {
            q=mr_mul2(x->w[i],y->w[j],&p); 
            w0->w[i+j]^=p;
            w0->w[i+j+1]^=q;
        } 
    }
    mr_lzero(w0);
    copy(w0,w);
#endif
#endif
}

void add2(big x,big y,big z)
{ /* XOR x and y */
    int i,lx,ly,lz,lm;
    mr_small *gx,*gy,*gz;

    if (x==y)
    {
        zero(z);
        return;
    }
    if (y==NULL)
    {
        copy(x,z);
        return;
    }
    else if (x==NULL) 
    {
        copy(y,z);
        return;
    }

    if (x==z)
    {
        gy=y->w; gz=z->w;
        ly=y->len; lz=z->len;
        lm=lz; if (ly>lz) lm=ly;
        for (i=0;i<lm;i++)
            gz[i]^=gy[i];
        z->len=lm;
        if (gz[lm-1]==0) mr_lzero(z);
    }
    else
    {
        gx=x->w; gy=y->w; gz=z->w;
        lx=x->len; ly=y->len; lz=z->len;
        lm=lx; if (ly>lx) lm=ly;

        for (i=0;i<lm;i++)
            gz[i]=gx[i]^gy[i];
        for (i=lm;i<lz;i++)
            gz[i]=0;
        z->len=lm;
        if (gz[lm-1]==0) mr_lzero(z);
    }
}

static void remain2(_MIPD_ big y,big x)
{ /* generic "remainder" program. x%=y */
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    int my=numbits(y);
    int mx=numbits(x);
    while (mx>=my)
    {
        copy(y,mr_mip->w7);
        shiftleftbits(mr_mip->w7,mx-my);
        add2(x,mr_mip->w7,x);    
        mx=numbits(x);
    }
    return;
}

void gcd2(_MIPD_ big x,big y,big g)
{
#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif
    if (size(y)==0) 
    {
        copy(x,g);
        return;
    }
    copy(x,mr_mip->w1);
    copy(y,mr_mip->w2);
    forever
    {
        remain2(_MIPP_ mr_mip->w2,mr_mip->w1);
        if (size(mr_mip->w1)==0) break;
        copy(mr_mip->w1,mr_mip->w3);
        copy(mr_mip->w2,mr_mip->w1);
        copy(mr_mip->w3,mr_mip->w2);
    }
    copy(mr_mip->w2,g);
}


/* See "Elliptic Curves in Cryptography", Blake, Seroussi & Smart, 
   Cambridge University Press, 1999, page 20, for this fast reduction
   routine - algorithm II.9 */

void reduce2(_MIPD_ big y,big x)
{ /* reduction wrt the trinomial or pentanomial modulus        *
   * Note that this is linear O(n), and thus not time critical */
    int k1,k2,k3,k4,ls1,ls2,ls3,ls4,rs1,rs2,rs3,rs4,i;
    int M,A,B,C;
    int xl;
    mr_small top,*gx,w;

#ifdef MR_OS_THREADS
    miracl *mr_mip=get_mip();
#endif

    if (x!=y) copy(y,x);
    xl=x->len;
    gx=x->w;

    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;

 
/* If optimizing agressively it makes sense to make this code specific to a particular field
   For example code like this can be optimized for the case 
   m=163. Note that the general purpose code involves lots of branches - these cause breaks in 
   the pipeline and they are slow. Further loop unrolling would be even faster...

   Version 5.10 - optimal code for 32-bit processors and for some NIST curves added
   Version 5.22 - some code for a 16-bit processor..

   Version 5.23 - Use findbase.cpp to find "best" irreducible polynomial
   Version 5.23 - Use utility irp.cpp to automatically generate optimal code for insertion here
*/

#if MIRACL == 8

    if (M==163 && A==7 && B==6 && C==3)
    {
        for (i=xl-1;i>=21;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-19]^=(w>>4)^(w>>5);
            gx[i-20]^=(w>>3)^(w<<4)^(w<<3)^w;
            gx[i-21]^=(w<<5);
        }   /* XORs= 7 shifts= 6 */
        top=gx[20]>>3;
        gx[0]^=top;
        top<<=3;
        gx[0]^=(top<<4)^(top<<3)^top;
        gx[1]^=(top>>4)^(top>>5);
        gx[20]^=top;
        x->len=21;
        if (gx[20]==0) mr_lzero(x);
        return;
    }

    if (M==271 && A==201)
    {
        for (i=xl-1;i>=34;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-8]^=(w>>6);
            gx[i-9]^=(w<<2);
            gx[i-33]^=(w>>7);
            gx[i-34]^=(w<<1);
        }   /* XORs= 4 shifts= 4 */
        top=gx[33]>>7;
        gx[0]^=top;
        top<<=7;
        gx[24]^=(top<<2);
        gx[25]^=(top>>6);
        gx[33]^=top;
        x->len=34;
        if (gx[33]==0) mr_lzero(x);
        return;
    }

    if (M==271 && A==207 && B==175 && C==111)
    {
        for (i=xl-1;i>=34;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-8]^=w;
            gx[i-12]^=w;
            gx[i-20]^=w;
            gx[i-33]^=(w>>7);
            gx[i-34]^=(w<<1);
        }   /* XORs= 5 shifts= 2 */
        top=gx[33]>>7;
        gx[0]^=top;
        top<<=7;
        gx[13]^=top;
        gx[21]^=top;
        gx[25]^=top;
        gx[33]^=top;
        x->len=34;
        if (gx[33]==0) mr_lzero(x);
        return;
    }

#endif

#if MIRACL == 16

    if (M==163 && A==7 && B==6 && C==3)
    {
        for (i=xl-1;i>=11;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-10]^=(w>>3)^(w<<3)^(w<<4)^w;
            gx[i-11]^=(w<<13);
            gx[i-9]^=(w>>12)^(w>>13);
        }
        top=gx[10]>>3;
        gx[0]^=top;
        top<<=3;

        gx[1]^=(top>>12)^(top>>13);
        gx[0]^=(top<<4)^(top<<3)^top;

        gx[10]^=top;
        x->len=11;
        if (gx[10]==0) mr_lzero(x);
        
        return;
    }

    if (M==271 && A==201 && B==0)
    {
        for (i=xl-1;i>=17;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-17]^=(w<<1);
            gx[i-16]^=(w>>15);
            gx[i-5]^=(w<<10);
            gx[i-4]^=(w>>6);
        }
        top=gx[16]>>15;
        gx[0]^=top;
        top<<=15;
        gx[12]^=(top>>6);
        gx[11]^=(top<<10);

        gx[16]^=top;
        x->len=17;
        if (gx[16]==0) mr_lzero(x);

        return;
    }

    if (M==271 && A==207 && B==175 && C==111)
    {
        for (i=xl-1;i>=17;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-4]^=w;
            gx[i-6]^=w;
            gx[i-10]^=w;
            gx[i-16]^=(w>>15);
            gx[i-17]^=(w<<1);
        }   /* XORs= 5 shifts= 2 */
        top=gx[16]>>15;
        gx[0]^=top;
        top<<=15;
        gx[6]^=top;
        gx[10]^=top;
        gx[12]^=top;
        gx[16]^=top;
        x->len=17;
        if (gx[16]==0) mr_lzero(x);
        return;
    }

#endif

#if MIRACL == 32

    if (M==127 && A==63)
    {
        for (i=xl-1;i>=4;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-2]^=w;
            gx[i-3]^=(w>>31);
            gx[i-4]^=(w<<1);
        }   /* XORs= 3 shifts= 2 */
        top=gx[3]>>31; gx[0]^=top; top<<=31;
        gx[1]^=top;
        gx[3]^=top;
        x->len=4;
        if (gx[3]==0) mr_lzero(x);
        return;
    }

    if (M==163 && A==7 && B==6 && C==3)
    {
        for (i=xl-1;i>=6;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-5]^=((w>>3)^(w<<4)^(w<<3)^w);
            gx[i-6]^=(w<<29);              
            gx[i-4]^=((w>>28)^(w>>29));
        }
        top=gx[5]>>3;
        
        gx[0]^=top;
        top<<=3;
        gx[1]^=(top>>28)^(top>>29);
        gx[0]^=top^(top<<4)^(top<<3);

        gx[5]^=top;
        
        x->len=6; 
        if (gx[5]==0) mr_lzero(x);
        
        return;
    }

    if (M==163 && A==99 && B==97 && C==3)
    {
        for (i=xl-1;i>=6;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-2]^=w^(w>>2);
            gx[i-3]^=(w<<30);
            gx[i-5]^=(w>>3)^w;
            gx[i-6]^=(w<<29);
        } 
        top=gx[5]>>3;
        gx[0]^=top;
        top<<=3;
        gx[0]^=top;
        gx[2]^=(top<<30);
        gx[3]^=top^(top>>2);
        gx[5]^=top;
        x->len=6;
        if (gx[5]==0) mr_lzero(x);
        return;
    }

    if (M==233 && A==74 && B==0)
    {
        for (i=xl-1;i>=8;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-8]^=(w<<23);
            gx[i-7]^=(w>>9);
            gx[i-5]^=(w<<1);
            gx[i-4]^=(w>>31);
        }
        top=gx[7]>>9;
        gx[0]^=top;
        gx[2]^=(top<<10);
        gx[3]^=(top>>22);
        gx[7]&=0x1FF;

        x->len=8;
        if (gx[7]==0) mr_lzero(x);
        return;
    }

    if (M==233 && A==159 && B==0)
    {
        for (i=xl-1;i>=8;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-2]^=(w>>10);
            gx[i-3]^=(w<<22);
            gx[i-7]^=(w>>9);
            gx[i-8]^=(w<<23);
        }   
        top=gx[7]>>9;
        gx[0]^=top;
        top<<=9;
        gx[4]^=(top<<22);
        gx[5]^=(top>>10);
        gx[7]^=top;
        x->len=8;
        if (gx[7]==0) mr_lzero(x);
        return;
    }

    if (M==233 && A==201 && B==105 && C==9)
    {
        for (i=xl-1;i>=8;i--)
        {
            w=gx[i]; gx[i]=0;
            gx[i-1]^=w;
            gx[i-4]^=w;
            gx[i-7]^=(w>>9)^w;
            gx[i-8]^=(w<<23);
        }   
        top=gx[7]>>9;
        gx[0]^=top;
        top<<=9;
        gx[0]^=top;
        gx[3]^=top;
        gx[6]^=top;
        gx[7]^=top;
        x->len=8;
        if (gx[7]==0) mr_lzero(x);