Hi

Can somebody please explain to me, what are the uses and benefits of implementing and using polynomial addition or division routines. as compared to number operations.

isn't polynomial a number after all, what are uses of implementing shift and add method with bit operations when we could simply compute a*b and then convert them in polynomial form??

i am quite confused actually, because the units in ALU already treat numbers as polynomials on the hardware level, operating with bits iteratively

so where its important to add another layer of transformation on top of that??
Posted on 2010-09-26 05:17:55 by Turnip
Polynomials over GF(2m) aren't numbers, they're polynomials! ;)

In polynomial f(GF(2m)) = a0X0+a1X1++anXn coefficients ai are from GF(2m) and X has no determinate meaning (thus no carry between coefficients during polynomial operations).
Posted on 2010-09-26 10:07:09 by baldr
hi baldr

thanks for input

however it doesnt explain things much to me,

i always thought elements of gf2^m are just like numbers, cause its just ones or zeroes on different positions (like machine words),

Polynomial: x6 + x4 + x + 1
Binary: {01010011}
Hexadecimal: {53}

and addition/ subtraction is just xor

so i would like to know, what is the purpose of polynomial algorithms if we could use numbers instead

and any info as welcome cause i am quite lost
Posted on 2010-09-26 13:41:29 by Turnip
Elements of GF(2m) are indeed isomorphic to {0, 1, 2, 2m-1}. Polynomials over F2m (AKA GF(2m)) are different beasts. Do you have TAOCP vol. 3 ready? In second edition, that's pp. 399 thru 505.
Posted on 2010-09-26 16:25:12 by baldr
hello and thanks again for your valuable time,

but you seem to miss the question.

question goes: why it is important to treat elements of gf 2^m as polynomials ( polynomials over gf 2) when implementing operations on them?? Or is it??

to clear things even more i will explain why i ask. our instructor wants us to add and double dots on elliptic curve, and states we must treat coordinates of each dot ie x and y not as numbers, but as polynomials when implementing things like x3 + y1 etc.

as you yourself said they are isomorphic to machine words, so what i the benefit of using polynomial arithmetic functions instead of just using alu.



Posted on 2010-09-27 03:51:52 by Turnip
Turnip,

Your question was a pretty excuse for me to refresh my memory (like DRAM, it needs regular refresh ;)) on abstract algebra, so no time was lost in vain.

I repeat: elements of GF(2m) are isomorphic to {0, 1,, 2m-1}, thus we can treat them like numbers (addition/multiplication-like operations, identities, inverses and all those useful properties of any finite field).

Polynomials over GF(2m) are, by definition, polynomials with coefficients from GF(2m). Symbols Xi are independent (for example, if the polynomial is over GF(2), you can't think that Xi+Xi = Xi+1). Polynomials over ?2m aren't isomorphic to ?2m! More likely they're isomorphic to (infinite) set of row/column vectors of arbitrary dimensions with elements from ?2m (I'm not sure about this, though).

To recap all of this: +/ in polynomial has no relation to addition/multiplication, Xi is not a power of X.

Back to your problem: point (10, 20) can be represented as 10x+20y polynomial (remember, x and y are indeterminates here, and +/ doesn't mean regular addition/multiplication). If the coefficients are from ?, such binomials represent plane as good as Cartesian coordinate system does. For binomial over cyclic group they represent something similar to toroid skeleton (sphere is almost as good, but singularities at the poles break analogy).

Though I don't see how this apply to elliptic curves (yet, I hope). Can you provide an example of exercises instructor gave you?
Posted on 2010-09-27 10:44:45 by baldr
hi
let me first of all thank you for your methodical approach and readiness to help.

however, there is no need to go into Cartesian coordinates, and all this geometry, as i wont be able to follow you there i am afraid... ).

so here's the exercises (quite trivial, but...)

The elliptic curve over GF2^m given by the equation y^2 + xy = x^3 +ax^2 + b. we need to compute point addition or doubling

Input : P1 = (x1 , y1) , P2 = (x2 , y2).
Output : P3 = P1 + P2 = (x3 , y3).

1. If P1 = P2 (doubling)
x3 = L^2 +L + a,
y3 = x1^2 + (L+ 1) x3
where (L = x1 + y1 / x1 )

2. Else if P1 <> P2 (point addition)
x3 = L^2 + ? + x1 + x2 + a,
y3 = L(x1 + x3) + x3 + y1
where (L= ( y2 + y1 ) / ( x2 + x1 ) )

3. Return (x3 , y3)

now, here is the important part. as ec is over a field, our task is sort of pretty hard -

instead of calculating, say, y3 = L(x1 + x3) + x3 + y1

like this : (just abstraction)


load x1 in reg1
load x3 in reg3
add reg1, reg3
mul reg1, L
add reg1, reg3
add reg1, y1


we must use shift and add method (http://users.utcluj.ro/~baruch/book_ssce/SSCE-Shift-Mult.pdf) to add, say x1 and x3 as polynomials over gf 2.
long division (http://www.intag.org/downloads/ds_009.htm) or multiplying by multiplicative inverse, which nevertheless we have to find first.

so before undertaking this terrifying amount of studying i would like to know, is this approach worth it.

why bignum shift and add is better then bignum multiple adc on words?


appendix

shift and add polynomial multiplication, inverse, stuff
http://eref.uqu.edu.sa/files/Others/Elliptic%20Curves/Implementation%20of%20Elliptic%20Curve%20Cryptographic%20Coprocessor.pdf
Posted on 2010-09-27 12:50:03 by Turnip