Thread: multiplication function in Binary Field, please help

Hi everyone,

I am trying to make a multiplication function in Binary Field with GF2m, f(x)=x^1279 + x^319 + x^127 + x^63 + 1.

Unfortunately, It does not work properly. I don't know why. Could you please show me if I miss something in my code.

Code:

In my f initialization:
 f[19]=f[19]|(1ULL <<63); //set 1279th bit to 1
 f[4]=f[4]| (1ULL << 63);  // set 319th bit to 1
 f[1]=f[1]| (1ULL << 63); //set 127th bit to 1
 f[0]=f[0]| (1ULL << 63); // set 63rd bit to 1
 f[0]=f[0]|1ULL;  //set 1st bit to 1

in my shiftleft:
  unsigned char a,b=0;
   int i;
   b=x[19]& (1ULL<<63); 
   for (i=19;i>=0;i--){
     a=x[i] & (1ULL<<63) ;
     x[i]=x[i]<<1ULL;
     if (i!=19) if(b) x[i]|=1;     
     b=a;      
  }
in my ff_mul:
   copy b to b1
   if (a[0] & 1) //if the lowest bit of a is 1
       for (i=0;i<20;i++) c[i]=b1[i];
  for (i=1;i<1279;i++){   
       k=(b1[19] & (1ULL<<63)); //get the highest bit of b1
       shiftleft(b1); //shiftleft b1 by 1
      if(k) 
      for(j=0;j<20;j++) b1[j]^=f[j]; // f=x^1279 + x^319 + x^127 + x^63 + 1 
      if(a[i / 64] >> (i % 64) & 1) //if the lowest bit of a is 1 
      for(j=0;j<20;j++) c[j]^=b1[j];

Actually, when I checked each function separately, I saw they are true. However, it still fail when I combine them. Thank you so much.

I am confused by your shift code. If it is a left-shift (x[i] = x[i] << 1), why does the carry move to the right? (I.e., overflow on byte 18 gets put on the right side of byte 17, and overflow on byte 17 gets put on the right side of byte 16, etc.) The original overflow check just gets thrown away, but that's probably on purpose (since I would suspect the whole point is that you should never have x^1279 turned on, since the reduction equation will allow you to reduce it).

Originally Posted by tabstop

I am confused by your shift code. If it is a left-shift (x[i] = x[i] << 1), why does the carry move to the right? (I.e., overflow on byte 18 gets put on the right side of byte 17, and overflow on byte 17 gets put on the right side of byte 16, etc.) The original overflow check just gets thrown away, but that's probably on purpose (since I would suspect the whole point is that you should never have x^1279 turned on, since the reduction equation will allow you to reduce it).

Thanks for your reply. Do you mean that I should turn off the 1279th bit?

Is there any problem in my leftshift? Please tell me.

Originally Posted by lovesunset21

Thanks for your reply. Do you mean that I should turn off the 1279th bit?

Is there any problem in my leftshift? Please tell me.

I'm pretty sure that you've got some right-shift mixed into your left-shift. Think about how your carries should work, and then look at what you've got.

And the usual use of the reduction equation is to reduce, right? You've got x^1279 + x^319 + x^127 + x^63 + 1 = 0, which means x^1279 = -(x^319 + x^127 + x^63 + 1), and since you're in GF2, -1 = 1 so you can treat the right side as positive, so you can "reduce" x^1279 into those smaller terms. After all, at least if your loops are correct, you only keep 20 elements in your array o' coefficients, right? The only reason you can stop there is your reduction equation allows you to get rid of any x^1279 powers (which means they never get any higher, by the same token).

Originally Posted by tabstop

I'm pretty sure that you've got some right-shift mixed into your left-shift. Think about how your carries should work, and then look at what you've got.

And the usual use of the reduction equation is to reduce, right? You've got x^1279 + x^319 + x^127 + x^63 + 1 = 0, which means x^1279 = -(x^319 + x^127 + x^63 + 1), and since you're in GF2, -1 = 1 so you can treat the right side as positive, so you can "reduce" x^1279 into those smaller terms. After all, at least if your loops are correct, you only keep 20 elements in your array o' coefficients, right? The only reason you can stop there is your reduction equation allows you to get rid of any x^1279 powers (which means they never get any higher, by the same token).

When I try to print the result of my shiftleft, it is for example:

Code:

before:
0110011001011101001100110010100100011010010101000100100111010000   0110101110000101111110111100001001011111100000110000011000011000

x^1+x^2+x^5+x^6+x^9+x^11+x^12+x^13+x^15+x^18+x^19+x^22+x^23+x^26+x^28+x^31+x^35+x^36+x^38+x^41+x^43+x^45+x^49+x^52+x^55+x^56+x^57+x^59   +x^65+x^66+x^68+x^70+x^71+x^72+x^77+x^79+x^80+x^81+x^82+x^83+x^84+x^86+x^87+x^88+x^89+x^94+x^97+x^99+x^100+x^101+x^102+x^103+x^104+x^110+x^111+x^117+x^118+x^123+x^124

After:

0011001100101110100110011001010010001101001010100010010011101000   0011010111000010111111011110000100101111110000011000001100001100

x^2+x^3+x^6+x^7+x^10+x^12+x^13+x^14+x^16+x^19+x^20+x^23+x^24+x^27+x^29+x^32+x^36+x^37+x^39+x^42+x^44+x^46+x^50+x^53+x^56+x^57+x^58+x^60   +x^66+x^67+x^69+x^71+x^72+x^73+x^78+x^80+x^81+x^82+x^83+x^84+x^85+x^87+x^88+x^89+x^90+x^95+x^98+x^100+x^101+x^102+x^103+x^104+x^105+x^111+x^112+x^118+x^119+x^124+x^125

I wonder if it is right or wrong. Thanks so much.

In order to test whether your carry works, you need to pick a sample *that has a carry in it*. Try shifting x^63+x^191+x^447 and see what happens.

Amazing, why does it become all 0 after shiftleft? My shiftleft is wrong....

I rewrite my shiftleft and it seems correct. However, my program still works inaccurately.

Code:

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

Again, you need to add one for the carry if the previous eight-byte-thing had a one at the extreme left, not if the current eight-byte-thing has a one at the extreme left. So you need to deal with a and b like you did before. Also at the end you will need to work your reduction scheme if the absolute top bit is set (unless you have a separate routine that does that).

My problem is that when I tried shifleft function above. It seems right. I cannot find the wrong. Oh, I am going to be crazy

00000000000000000000000000000000000000000000000000 00000000000001 00000000000000000000000000000000000000000000000000 00000000000000 00000000000000000000000000000000000000000000000000 00000000000001

after shift

00000000000000000000000000000000000000000000000000 00000000000000 100000000000000000000000000000000000000000000000000 0000000000000 00000000000000000000000000000000000000000000000000 00000000000000

So you need to add one for the carry if the previous eight-byte-thing had a one at the extreme left. You are checking if the current eight-byte-thing has a one at the extreme left, and if so, putting a 1 at the end. In other words, you're making it into a cycle. You need to go from 0 to 1, from 1 to 2, etc. So you should

1. Check whether there's a 1 on the extreme left of 0 and, if so, make a note to carry.
2. Shift 0 to the left.
3. Now, look at whether there's a 1 on the extreme left of 1 and, if so, make a note to carry (in a different place as before -- let's call it "pending" instead of "current").
4. Shift 1 to the left.
5. Add carry if necessary, and turn the pending note-to-carry into the current note-to-carry.
6. Now, look at whether there's a 1 on the extreme left of 2 and, if so, make a (pending) note to carry.
7. Shift 2 to the left.
8. Add carry if necessary, and turn the pending note-to-carry into the current note-to-carry.

etc.

In the shiftleft above, I do as followed:

1. shift 0 to left

2. check if the extreme left of 1 is 1, make a note.

3. shift 1 to left

4. if it is noted, set the extreme right of 0 to 1.

5. check if the extreme left of 2 is 1, make a note.

6. shift 2 to left

7. if it is noted, set the extreme right of 1 to 1.

Is this correct? By the way, what is carry? Thank you so much.

Originally Posted by lovesunset21

In the shiftleft above, I do as followed:

1. shift 0 to left

2. check if the extreme left of 1 is 1, make a note.

3. shift 1 to left

4. if it is noted, set the extreme right of 0 to 1.

5. check if the extreme left of 2 is 1, make a note.

6. shift 2 to left

7. if it is noted, set the extreme right of 1 to 1.

Is this correct? By the way, what is carry? Thank you so much.

That is what you do, and it makes no sense. If you shift something to the left of position 127, why would you put it at position 0 instead of position 128? The thing you shift off the left end of p[0] is going to go at the right end of p[1], not the other way around.

I am so sorry. I understand the rule to shift the bit to the left but I am really confused about the bit position. That's the reason why I do something stupid in my code. Let's me explain my code and please give me a comment. Honestly, I am totally a dummy with that thing.

f

Code:

or (i=0;i<20;i++){
    a=x[i]>>63 & 1;                        // Get the most left bit of current element
    x[i]=x[i]<<1;                             // shift element to the left
    if (i!=0) if(a) x[i-1]|=1ULL;        //set the most right bit of the previous element to 1 if the  most left bit of current element is 1. 
}

For example:

01111010 10000010 10001100

after shift 11110101 00000101 00011000

I know what I have done is wrong. But I don't know exactly why it is wrong in the code. Please help me. Thank you very much.

Because the previous element [i-1] is to the RIGHT of where you are. (Remember, up at the top? The x^1279, the leftmost thing, was at f[19], while x^0, the rightmost thing, was at f[0].) If you want to shift to the left, then you had better be moving to the left.