## Now reading

Finished reading about multiplier over $GF(2^n)$ – polynomial bases.
Now moving on to multiplier for Optimal Normal Basis Type II.
1. An Efficient Optimal Normal Basis Type II Multiplier, B. Sunar, C. K. Koc
2. Brief Contributions – An Efficient Optimal Normal Basis Type II Multiplier, B. Sunar, C. K. Koc

Next will be designing multiplier for composite field and implement it in vhdl.

• #### Fernando Urbano 10:09 pm on November 7, 2010 Permalink | Reply

Greetings, I tried to implemented these multiplier for 233 bits, a Type II ONB, but I hadn’t success. Could you did it? If so, could you tell me how? Thanks!!!! Very nice blog I like it a lot of.

• #### CG 5:25 am on November 8, 2010 Permalink | Reply

hello fernando, thx for visiting the blog. i’m now still trying to implement multiplier for 299bits, using PB. maybe after successfully implement PB version (assuming that it’s easier than ONB II) then i will start using Type II ONB.

do you implement it using vhdl too?

• #### Fernando Urbano 12:00 pm on November 8, 2010 Permalink | Reply

yes, I did. But I think that something ws wrong with the permutage stage (changing base) to reconvert the result at the ONB again. I think that is very large multiplier compare with others. What kind of PB muliplier are you trying to implement?

• #### CG 12:13 pm on November 8, 2010 Permalink | Reply

we have developed conversion algorithm from PB – ONB1 and vice versa but not yet for PB – ONB2. what is your consideration of using ONB2? i’m trying to implement the two-step classic multiplication. i need a classic multiplication method to be compared to multiplication for composite field in PB representation. do you have any experiences with composite field?

• #### Fernando Urbano 11:37 pm on November 12, 2010 Permalink | Reply

We considere, OB2 because it’s the only one in these base from the five (m = 163, 233, 283, 409, 571) recommended by NIST for elliptic curve digital signature algorithm.

• #### CG 6:48 am on November 13, 2010 Permalink | Reply

oh i see. you’re referring NIST for choosing the curve. have you published any papers related to what you’re working on now? i’d like to read if there’s any 🙂 thx

## 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.]

## Desperate Log

The existing algorithm for $GF((2^n)^m)$ is only for $n = 2^i$ and $m = 2^j$.
And GF with those restrictions don’t have ONB2 representation.

Oh well.

## Selecting composite field that have ONBII representation

…is not that easy.

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