Tagged: normal basis Toggle Comment Threads | Keyboard Shortcuts

  • CG 2:15 pm on February 7, 2009 Permalink | Reply
    Tags: normal basis,   

    From one basis to another 

    Apparently converting from one basis to another like from polynomial to normal basis is not as easy as I thought, hmm… have spent days scribbling, thinking, frustated, madly curious, and end up browsing several papers about that and being succesfully diverted from the main target of doing paper on plaintext embedding, oh my!

    Let me digest some more papers I have just downloaded 30secs ago, and will post something useful here as soon as possible 😉

    [big headache continues…]

  • CG 2:38 pm on February 2, 2009 Permalink | Reply
    Tags: normal basis,   

    Answer for #1 

    Again, from here:

    1. How to convert from polynomial to normal bases?

    GF element can be represented in Polynomial Basis (PB) or Normal Basis (NB).

    For example we have polynomial p(x)=x^{3}+x^{2}+1

    The PB representation in GF\left (2^{3} \right ) is

    If GF\left (p^{m} \right ) be a field with p^{m} elements and \beta an element of it such that m elements \left \{\beta ,\beta ^{p}, ... , \beta ^{p^{m-1}} \right \} are linearly dependent. Then this set forms a normal basis for GF\left (p^{m} \right )

    The NB representation of elements in GF\left (2^{3} \right ) will only use 3 elemens \beta , \beta ^{2} dan \beta ^{4} .

  • CG 1:58 pm on February 2, 2009 Permalink | Reply
    Tags: , normal basis,   

    Answer for #2 

    Answering #2 from here:

    2. For what conditions ONB representation is available?

    Answer: One condition is when the p(x) generates GF elements which are linearly independent.

  • CG 6:41 pm on January 29, 2009 Permalink | Reply
    Tags: normal basis,   

    Normal basis: squaring is fast 

    Yes, right. ONB (Optimal Normal Basis) is so appealing 😀

    If we take some element \beta in the field F_{p^{m}} , the polynomial representation is:
    \beta =a_{n}x^{n}+ ... + a_{1}x + a_{0}
    where n < m

    A normal basis can be formed using the set:
    \left \{\beta ^{p^{m-1}},... \beta ^{p^{2}}, \beta ^{p}, \beta  \right \}

    Any element in a field F_{p^{m}} can be represented in a normal basis format. An element e , can be written in a normal basis as:
    e = e_{m-1}\beta ^{2^{m-1}} + ... + e_{2}\beta ^{2^{2}} + e_{1}\beta ^{2} + e_{0}\beta

    It seems complex but the implementation in the computer is as simple as using only AND, OR and ROTATE!

    The most interesting thing is that this representation allow squaring with just a number amounts of rotation!

    Here are some proves:

    1. \left (\beta ^{2^{i}} \right )^{2}=\beta ^{2^{i+1}}
    2. \beta ^{2^{m}}=\beta

    That’s why squaring is very fast in normal basis! Will post more about this.

    • Budi Rahardjo 11:19 pm on January 29, 2009 Permalink | Reply

      Choosing whether you want to use ONB (and other[s]) depends on many things; (1) the number of different operations that you want to do; (2) the cost of each operation. Squaring is fast, but what about addition and multiplication? Can they also be done easily (hardware wise)? And how easy can you transform from polynomial representation to ONB? …
      sorry, lots of questions 🙂

    • CG 9:23 am on January 30, 2009 Permalink | Reply

      botak deh! 😀

      jawab pertanyaannya dicicil ya? good questions… and hard ones! 😀

      • Minnalkodi 10:12 am on February 6, 2013 Permalink | Reply

        How to convert binary values to normal basis plz anybody tell

Compose new post
Next post/Next comment
Previous post/Previous comment
Show/Hide comments
Go to top
Go to login
Show/Hide help
shift + esc