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??

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??

Polynomials over GF(2

In polynomial f(GF(2

^{m}) aren't numbers, they're… polynomials! ;)In polynomial f(GF(2

^{m})) = a_{0}X^{0}+a_{1}X^{1}+…+a_{n}X^{n}coefficients a_{i}are from GF(2^{m}) and X has no determinate meaning (thus no carry between coefficients during polynomial operations).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

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

Elements of GF(2

^{m}) are indeed isomorphic to {0, 1, 2,… 2^{m}-1}. Polynomials over F_{2m}(AKA GF(2^{m})) are different beasts. Do you have TAOCP vol. 3 ready? In second edition, that's pp. 399 thru 505.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.

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.

**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(2**are isomorphic to {0, 1,…, 2

^{m})^{m}-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(2**are, by definition, polynomials with coefficients from

^{m})**GF(2**. Symbols

^{m})**X**are independent (for example, if the polynomial is over GF(2), you can't think that

^{i}**X**).

^{i}+X^{i}= X^{i+1}__Polynomials over__! More likely they're isomorphic to (infinite) set of row/column vectors of arbitrary dimensions with elements from

**?**aren't isomorphic to_{2m}**?**_{2m}**?**(I'm not sure about this, though).

_{2m}To recap all of this:

**+**/

**·**in polynomial has no relation to addition/multiplication,

**X**is not a power of

^{i}**X**.

Back to your problem: point (10, 20)

*can*be represented as 10·x+20·y 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?

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)

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

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