multiplication function in Binary Field, please help

This is a discussion on multiplication function in Binary Field, please help within the C Programming forums, part of the General Programming Boards category; Hi everyone, I am trying to make a multiplication function in Binary Field with GF2m, f(x)=x^1279 + x^319 + x^127 ...

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    37

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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).

  3. #3
    Registered User
    Join Date
    Oct 2010
    Posts
    37
    Quote Originally Posted by tabstop View Post
    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.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by lovesunset21 View Post
    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).

  5. #5
    Registered User
    Join Date
    Oct 2010
    Posts
    37
    Quote Originally Posted by tabstop View Post
    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.

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  7. #7
    Registered User
    Join Date
    Oct 2010
    Posts
    37
    Amazing, why does it become all 0 after shiftleft? My shiftleft is wrong....

  8. #8
    Registered User
    Join Date
    Oct 2010
    Posts
    37
    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;
         
       }
    }

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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).

  10. #10
    Registered User
    Join Date
    Oct 2010
    Posts
    37

    Unhappy

    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

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  12. #12
    Registered User
    Join Date
    Oct 2010
    Posts
    37
    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.

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by lovesunset21 View Post
    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.

  14. #14
    Registered User
    Join Date
    Oct 2010
    Posts
    37
    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.

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM
  2. <Gulp>
    By kryptkat in forum Windows Programming
    Replies: 7
    Last Post: 01-14-2006, 12:03 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 09:18 AM
  5. I need help with passing pointers in function calls
    By vien_mti in forum C Programming
    Replies: 3
    Last Post: 04-24-2002, 10:00 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21