Thread: multiplication function in Binary Field, please help

What happen if I try the code like this? Is this correct?

Code:

void shiftleft(uint64_t *x)
{
   unsigned char a,b=0;
   int i;
    b=x[19]& (1ULL<<63); 
    for (i=19;i>=0;i--){
     a=x[i] & (1ULL<<63) ; // Get the most left bit of current element, save it to a
     x[i]=x[i]<<1;               //shift left
     if (i!=19) if(b) x[i]|=1ULL;   //set the most right bit of the previous element to 1 if the  most left bit of current element is 1.  
     b=a;      // save the most left bit of current element to b
   }
}

Is that Ok?

Again, you are carrying from 19 to 18, from 18 to 17, from 17 to 16, etc. This is backwards. You need to carry the extra bit from 0 into 1, from 1 into 2, from 2 into 3, from 3 into 4, etc.

So:

Code:

unsigned char a, b = 0;
int i;
for (i=0; i < 20; ++i) {
    a = x[i] & (1ULL << 63); //Check whether left-most bit needs to be carried
    x[i] = x[i] << 1;
    if (i != 0) if(b) x[i] |= 1ULL;  //Set carry bit at right if needed
    b = a;
}

Thanks for your code, I understood. In case I want to shift right, I write the code like that:

Code:

void shiftright(uint64_t *x)
{
   int i;
   unsigned char a,b=0;
   b=x[0]&1;
   for (i=0;i<20;++i){
    a=x[i]&1;
    x[i]=x[i]>>1;
    if (i!=0) if(b) x[i]|=1ULL<<63;
    b=a;      
 }
}

And my mul function:

Code:

for (i=0;i<20;i++) c[i]=0ULL;
for (i=0;i<1279;i++){   
    
    if(a1[0]&1) for(j=0;j<20;j++) c[j]^=b1[j]; //if the bit of smallest power is 1  
    
    k=(b1[19] & (1ULL<<63)); //get the bit of largest power of b1
    
    shiftleft(b1); 
    
    if(k)  //if the bit of largest power is 1
    for(j=0;j<20;j++) b1[j]^=f[j]; 
    
    shiftright(a1);               	
}
if (c[19] & (1ULL<<63))
for(j=0;j<20;j++) c[j]^=f[j];

I still don't get the expected outcome. Did I miss something?

Oh my head hurts. If left goes from 0 to 20, then how can right also go from 0 to 20? Wouldn't right have to be the opposite direction from left?

You need to do your reduction after you shift b1, not before.