- How to convert from polynomial to normal bases?
- For what conditions ONB representation is available?
Updates from January, 2009 Toggle Comment Threads | Keyboard Shortcuts
Yes, right. ONB (Optimal Normal Basis) is so appealing 😀
If we take some element in the field , the polynomial representation is:
A normal basis can be formed using the set:
Any element in a field can be represented in a normal basis format. An element , can be written in a normal basis as:
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:
That’s why squaring is very fast in normal basis! Will post more about this.
Have just finished reading Chapter 4 from “Finite Fields for Computer Scientists and Engineers – Robert J. McEliece”.
I’ve been away from the computer and spend the whole morning scribbling some calculation on constructing a field. Me now understand that when we have an Euclidean domain with for example , that is irreducible because and , so has no zeroes in .
But I’d like to post this tables here just for a quick reminder for me, it’s unfinished but I’ve got the idea so keeping it up here will be useful someday when I forgot about this stuff 😀
Target : to embed plaintext to points in elliptic curve
What to do first : solving quadratic equation of the elliptic curve.
Problems : a quadratic equations only has a solution when the Trace of is 0
by converting the right-hand side to a simple form, say , then bring that over to the left-hand side to become :
then substitute it to the previous equation so it becomes:
Multiply the entire equation by , so we get:
Once we know the , we can solve for . It turns out is also a solution. So let be one solution and be another solution. After we find one solution, the other one is trivial. After the two solutions are recovered, then our data can be embedded on the curve.
[rewrite from this book]
[… deep thinking …]
Is that true that embedding plaintext on elliptic curve is as trivial as porting “Hello World!” in some programming language to another programming language?
[… digging deeper while thinking even deeper … ]
about Trace function for finite fields. Going to write more about that, but doing this for solving quadratic equations in binary fields, to finally embed the data to the points in the elliptic curve.
I did a minor modification on the string-to-bigint function :
So the result is like this :
Next to do :
Convert those big numbers representation into some points in elliptic curve 😉
Have just debug this block of code:
of this book, and found out that this only works fine for string numbers. It cannot represent all of characters. Characters with the last 4 bits bigger than 10, to be exact.
“A” = 65 = 0100 0001 = 1
“B” = 66 = 0100 0010 = 2
“I” = 73 = 0100 1001 = 9
“J” = 74 = 0100 1010 = ???
I think I’m going to find a way to modify this a little bit, because if it works for characters, I don’t have to convert it to numbers manually like I did before.
I’m now writing a handbook for helping the students learning java programming. The tutorial has been done but I’m going to make some revisions and add some stuff.