Tagged: onb1 Toggle Comment Threads | Keyboard Shortcuts

  • CG 8:34 am on August 20, 2010 Permalink | Reply
    Tags: , hardware architecture, onb1, ,   

    Choosing n and m for composite field 

    Referring to “Efficient Normal Basis Multipliers in Composite Fields” – Sangho Oh, Chang Han Kim, Jongin Lim, and Dong Hyeon Cheon, there is classification of hardware-applicable composite fields:

    1. Type I composite field where a subfield GF(2^n) in ONB2 and an extension field GF(2^{nm}) in ONB1
    2. Type II composite field where a subfield GF(2^n) in ONB1 and an extension field GF(2^{nm}) in ONB2
    3. Type III composite field where a subfield GF(2^n) in ONB2 and an extension field GF(2^{nm}) in ONB2

    This is different with composite fields presented in “Efficient Methods for Composite Field Arithmetic” – E. Sava ̧s and C ̧. K. Koc, where the selection of n and m  does not put their normal basis types (ONB1 or ONB2) into consideration.

    Now the questions are:

    1. Would it be better if we choose n , m and nm in ONB1/ONB2?
    2. Which polynomial irreducible to be used? With degree = n , or degree = m or degree = nm ?

    [pounding headache, and without answering these questions i wouldnt be able to start the hw design.]

    Advertisements
     
  • CG 10:14 pm on February 12, 2010 Permalink | Reply
    Tags: , onb1   

    More on ONB1 identity element 

    “Application of Finite Fields”  page 98:

    For a type I optimal normal basis, its minimal polynomial is obviously x x^n + ... + x + 1, which is irreducible over F_q if and only if n + 1 is a prime and q is primitive in Z_{n+1}

    For n = 4,
    x^4+x^3+x^2+x = 1
    x^5 = 1
    x^6 = x
    x^7 = x^2
    x^8 = x^3
    x^9 = x^4

    Ex :
    Let’s prove that 1111 is the identity element of ONB1 n = 4.

    1010 x 1111 = (x^8+x^2) x (x^8+x^4+x^2+x)
    = x^{16}+x^{12}+x^{10}+x^9+x^{10}+x^6+x^4+x^3
    = x^{16}+x^{12}+x^9+x^6+x^4+x^3
    = x + x^2 + x^4 + x + x^4 + x^3
    = x^2 + x^3
    = x^2 + x^8
    = x^8 + x^2
    = 1010

     
  • CG 9:19 pm on February 12, 2010 Permalink | Reply
    Tags: , onb1,   

    ONB1 identity element 

    Rosing wrote on page 144:

    In an optimal normal basis, adding 1 is the same as taking a complement

    And finally figuring this out after finding out that the identity element of ONB1 is x^{2^{n-1}}+...+x^{2^{1}}+x^{2^{0}}. If we have n = 4, the identity element or “1” is 1111 (x^{8}+x^{4}+x^{2}+x).

    That’s why if we have 0011 in normal basis (x^2+x), adding it with “1” so it becomes 0011 + 1111 = ((x^2+x) + (x^8+x^4+x^2+x) = x^8+x^4 = 1100.

    Hoooraaaay!

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel