## Weekend Read

Hardware Implementation of Finite-Field Arithmetic – Jean Pierre Deschamps, Jose Luis Imana, Gustavo D. Sutter, Chapter 7.

Going to learn about all multiplier for finite fields. And think how can a non-finite field multiplier be applied for finite field applications.

## Now reading

1. Efficient Normal Basis Multipliers in Composite Fields – Sangho Oh, Chang Han Kim, Jongin Lim, and Dong Hyeon Cheon
2. Modular Construction of Low Complexity Parallel Multipliers for a Class of Finite Fields $GF(2^n)$ – M. A. Hasan, M. Z. Wang and V. K. Bhargava
3. A Modified Massey-Omura Parallel Multiplier for a Class of Finite Fields – M. A. Hasan, M. Z. Wang and V. K. Bhargava

## Affine vs Projective Plane

Summary:

1. Projective Plane requires less multiplication compared to Affine Plane
2. No invers operation in Projective Plane
3. Projective Plane requires more memory as more temporary results to be saved
4. In defining point of infinity, Projective Plane gives a more natural way to programmer to deal with it

• #### CG 9:21 pm on August 10, 2010 Permalink | Reply

and i decided to use Lopez-Dahab 🙂

## Now reading

1. Arithmetic Operations in GF(2^m), G.B. Agnew, T. Beth, R.C. Mullin and Scott A. Vanstone, Journal of Cryptology, 1993.
2. VLSI Designs for Multiplication over Finite Fields GF(2^m), Eduardo D. Mastrovito.

• #### Fernando Urbano 2:28 am on December 10, 2010 Permalink | Reply

Hello. I need to ask you for a favor. I had been looking for these papers (from above) I’ll be very grateful if you can send it to my e-mail. Thanks!

• #### CG 4:56 am on December 10, 2010 Permalink | Reply

ok i will send them to your email 🙂

• #### Fernando Urbano 9:43 pm on December 10, 2010 Permalink | Reply

Thanks, my e-mail is: faurbano@gmail.com.

• #### rohani syawaliah 10:16 pm on December 15, 2010 Permalink | Reply

postingannya walaupun saya nggak ngeh apa yang kamu baca itu

ternyata dengan cara seperti ini memberikan manfaat juga ya buat orang laen?

bagus banget

## Table of Low-Weight Binary Irreducible Polynomials

A very useful list of irreducible trinomial and pentanomial of degree n 2 <= n <= 10000.

• #### Rn Colvard 2:26 am on July 17, 2010 Permalink | Reply

Need GF(2^64) & GF(2^32) irreducible polynomials

## Reading list

1. Comparison of Galois Fields Multipliers in Standard and Composite Fields Architectures, Petrus Mursanto, Proceedings of National Conference on Computer Science and Information Technology 2007, January 29-30, 2007, Faculty of Computer Science, University of Indonesia.
2. A Scalable Dual-Field Elliptic Curve Cryptographic Processor, Akashi Satoh and Kohji Takano, IEEE TRANSACTIONS ON COMPUTERS, VOL. 52, NO. 4, APRIL 2003.
3. Eﬃcient Methods for Composite Field Arithmetic, E. Savas and C.  K. Koc, Technical Report, December 1999.
4. Implementation Options for Finite Field Arithmetic for Elliptic Curve Cryptosystems, Christof Paar, 1999.
5. Hardware Implementation of Eﬃcient Modiﬁed Karatsuba Multiplier Used in Elliptic Curves, Sameh M. Shohdy, Ashraf B. El-Sisi, and Nabil Ismail (Corresponding author: Sameh M. Shohdy), International Journal of Network Security, Vol.11, No.3, PP.138–145, Nov. 2010.
6. http://www.computer.org/portal/web/csdl/abs/html/trans/tc/2003/11/t1391.htm

## Groups, fields, finite fields, zzzzz…

I’m admiring mathematicians for the consistency, strictness and clarity in defining and extracting patterns into definitions and theorems.

The good thing about math is to learn about discipline and consistency, and I’m still working hard on digesting those symbols that appear so similar yet define totally different thing.

I always get confused when I ask myself what’s the difference between $Z_{p}$, $F_{p}$ and $F_{p^m}$ and $GF(p^m)$.

Here’s the definitions, thank God I finally found this, from the same book:

There are also $F_{q}$ and $F_{q}^*$. Uffhhh, it’s amazing how one symbol could represent so many things…

• #### yuti 9:12 pm on March 22, 2009 Permalink | Reply

the first time I entered those subject was by learning to read 🙂

## Why finite fields?

Eh, there are still some questions left, and I’m posting it here to remind me that I have to move forward from this point 😉

Question:

Why finite fields? Does it has something to do with “reversible”? Is that a requirement for only elliptic curve? Is it possible for elliptic curve without finite fields?

## Finite Fields

Simply said, a field is a place where you can add, substract, multiply and divide, without leaving the set.

A field has several properties:

1. The rules of addition apply, and the field contains an additive identitive element

2. The rules of multiplication apply, and the field contains a multiplicative identity element

3. Every element in a field has an inverse

The set of integers is not a field, because integers don’t include fractions and so do not have multiplicative inverses.

The underlying set of a field determines whether a field is finite or infinite. If the set F is finite, then the field is said to be finite.

Infinite fields are not of particular interest in cryptographic applications, yet finite fields play a crucial role in many cryptographic algorithm.

Examples of infinite fields includes the real number, the rational numbers, the complex numbers and rational functions over a field.

The simplest finite field is modulo prime arithmetic.

Zp = {0, 1, …, p-1}, arithmetic mod p, where p is a prime, is a (finite) field

Examples:

Notice that Z4 (arithmetic mod 4) is not a field, since 2 has no inverse (look at the division table), there is no element x such that 2x = 1 (mod 4).

[Will post more on Finite Fields for Cryptographic Applications]

• #### Budi Sulistyo 2:49 am on April 22, 2008 Permalink | Reply

Apa ya syaratnya agar sebuah ring integer modulo n merupakan field?

• #### chikaradirghsa 10:50 am on April 22, 2008 Permalink | Reply

jawabannya nanti di update posting ini ya 🙂
ini belum lengkap.

tanya2x terus aja biar tambah lengkap, hihihihi

• #### Tommi 1:20 pm on April 22, 2008 Permalink | Reply

I haven’t taken any relevant courses yet, so pardon the stupid question: In what sense are the rational numbers or the real numbers finite, or did you mean to say that they are infinite fields? If they are indeed finite, what would be an example of an infinite one?

• #### chikaradirghsa 2:02 pm on April 22, 2008 Permalink | Reply

@tommi: thx for visiting and asking such an interesting questions 🙂

yes! thx for pointing me the error. i was going to imply that rational and real numbers are indeed INFINITE fields [correction is going to be made after this]!!!

thx again, tommi!

• #### temannya_intan 8:04 am on May 5, 2008 Permalink | Reply

Sorry yah……iseng menanggapi comment no 1, sambil ngetes latex.

Akan dibuktikan bahwa $\mathbb{Z}_n$ adalah field jikka (iff) $n$ adalah bilangan prima. Misalkan $\mathbb{Z}_n$ adalah field. Jika $n$ tidak prima maka kita bisa tulis $n=ab$ dengan $\latex 1<a,b<n$. Akibatnya $latex[a][b]=[ab]=0\in \mathbb{Z}_n$. It follows (upon multiplying by the inverse of a, $[b]=0$. So $b$ is a multiple of n (contradiction!).
Coversely, suppose $n$ is prime. If $a then a=1 or $(a,n)=1$. In the first case,then a has an inverse in Z_n and in the later case we have $x,y$ such that $ax+by=1$, which implies that x is the multiplicative inverse of a in Z_n. So Z_n is a field.

• #### chikaradirghsa 10:14 am on May 5, 2008 Permalink | Reply

@5 hello temennya intan, makasih banyak ya udah ngelengkapin keterangannya. HARUS mampir dan iseng comment lagi ya!!!

btw satu pertanyaan penting: ITU NEMPELIN FORMULA LATEX KE COMMENT GIMANA CARANYA YA? seneng deh liatnya rapi…

thx!

• #### temannya_intan 1:04 pm on May 5, 2008 Permalink | Reply

Sorry, latexnya gak rapi. Gak biasa dengan penulisan syntax latex di wordpress. Untuk menuliskan latex tulis $latex\sqrt{b^2-4ac}$ (harusnya ada space diantara latex dan math formula). Hasilnya akan seperti ini $\sqrt{b^2-4ac}$. Jadi perbedaannya dengan syntax latex yang biasa hanya di ruas kiri yg biasanya hanya dollar saja ($) diganti dengan$latex.

• #### chikaradirghsa 2:15 pm on May 5, 2008 Permalink | Reply

ok, thx tipsnya, yang jadi masalah, saya ga hafal perintah2x latex, kebiasaan pake lyx, he he he. kayaknya musti dibiasain sekarang ya. atau pake tools kayak di sini http://www.codecogs.com/components/equationeditor/equationeditor.php

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