Updates from January, 2009 Toggle Comment Threads | Keyboard Shortcuts

  • CG 10:14 am on January 30, 2009 Permalink | Reply
    Tags: normal bases,   

    Questions on polynomial and normal bases 

    1. How to convert from polynomial to normal bases?
    2. For what conditions ONB representation is available?
     
  • CG 6:41 pm on January 29, 2009 Permalink | Reply
    Tags: ,   

    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

  • CG 3:11 pm on January 29, 2009 Permalink | Reply
    Tags:   

    Constructing a field 

    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 D=F_{2}\left [x \right ] with for example p\left (x \right )=x^{4}+x+1 , that p is irreducible because p\left (0 \right )=1 and p\left (1 \right )=1 , so p\left (x \right ) has no zeroes in F_{2} .

    bla bla bla bla … i have many pages of scribbles…

    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 F_{2}^{m} stuff 😀

     
    • soni 6:46 pm on January 29, 2009 Permalink | Reply

      wow! CG with paper and pen! 😀
      sudah lama tidak begini.
      kalau tidak salah, terakhir waktu mac-nya rusak ya? hahaha.

      boleh minta dijelasin lagi tentang ini?
      biar saya ikutan ngerti, blink blink.

      biasanya kalo lagi ada ide, CG suka kerja sambil ngejelasin.
      tapi tadi keliatan asik uprek sendiri, jadi ga tega nge-distract-nya 😀

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

      jadi F 2 pangkat 3 beda dengan F 8 ya? masih belum mengerti bedanya (terutama di bagian sebelah kanan mod itu).
      terus, yang F 2 pangkat 3 itu ada inversenya?

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

      F_{2^{3}} sama dengan F_{8} hanya kalau F_{8} elementnya 0, 1, … 7.

      F_{2^{3}} ada inverse-nya.

  • CG 11:33 am on January 28, 2009 Permalink | Reply  

    Trace function 

    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 c is 0

    Example:
    E=y^{2}+xy=x^{3}+x^{2}+1

    by converting the right-hand side to a simple form, say f\left (x \right ) , then bring that over to the left-hand side to become :
    y^{2}+xy+f\left (x \right )=0

    Now let
    y = xz

    then substitute it to the previous equation so it becomes:
    \left (xz \right )^{2}+x^{2}z+f\left (x \right )=0

    Multiply the entire equation by x^{-2} , so we get:
    z^{2}+z+c=0

    where:
    c=f\left (x \right ).x^{-2}

    Once we know the Trace\left (c \right )=0 , we can solve for z . It turns out z+1 is also a solution. So let z be one solution and z{}' 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]

     
  • CG 8:51 am on January 28, 2009 Permalink | Reply
    Tags: thoughts   

    "Hello World!" Expert 

    [… 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 … ]

     
    • Budi Rahardjo 8:46 pm on January 28, 2009 Permalink | Reply

    • CG 5:29 am on January 29, 2009 Permalink | Reply

      @BR: thank you! I’m curious about hello world in verilog and vhdl, ha ha ha haia…

      the second link is hilarious! thanks!

    • mehobbes 5:38 pm on January 29, 2009 Permalink | Reply

      i teased with this posting.

      i don’t think create a ‘hello world program’ is just easy as we imagine,
      it need big effort, especially for someone who intend to learn programming.

      i dig the keyword ’embedding plaintext on elliptic curve’, and i found a paper from journal of communication and computer vol 3 no 3 2006. the paper entitled “problems of plaintext on elliptic curve and their applications’.

      i don’t think such problem which is submitted to the journal is a trivial problem.
      why are you bothered about this? is there something or someone annoying you?

  • CG 5:38 am on January 28, 2009 Permalink | Reply
    Tags: trace function   

    now reading… 

    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.

     
  • CG 9:28 pm on January 27, 2009 Permalink | Reply
    Tags: , ,   

    string to bigint – modified 

    I did a minor modification on the string-to-bigint function :

    picture-3

    So the result is like this :

    picture-2

    Next to do :

    Convert those big numbers representation into some points in elliptic curve 😉

     
  • CG 7:00 pm on January 27, 2009 Permalink | Reply
    Tags: , ,   

    modifying string to bigint 

    Have just debug this block of code:
    picture-1

    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.
    Like this:
    “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.

     
  • CG 3:24 pm on January 27, 2009 Permalink | Reply  

    GPA 4.0 

     
  • CG 4:01 pm on January 22, 2009 Permalink | Reply
    Tags: ,   

    tutorial and handbook 

    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.

     
    • Budi Rahardjo 7:32 pm on January 23, 2009 Permalink | Reply

      the handbook is excellent!

    • CG 2:45 pm on January 25, 2009 Permalink | Reply

      @BR: aaaaaaaa, do you think it is? thaaank yoouuuu!
      btw the one you saw was the tutorial. the handbook is still in progress 😀

    • Budi Rahardjo 4:12 pm on January 25, 2009 Permalink | Reply

      oh that was the tutorial? great …

    • iffata 1:17 pm on January 28, 2009 Permalink | Reply

      Maaaaauuuu !!! 😀

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