Implement GF16 compatible basis for GF256 implementation

w3f / rs-ec-perf

3 stars 3 forks source link

Implement GF16 compatible basis for GF256 implementation #4

Open drskalman opened 3 years ago

drskalman commented 3 years ago

Given

The minimal polynomial of $latex GF16=Z/2Z[x]/p(x)$.
The minimal polynomial of $latex GF256=Z/2Z[y]/q(y)$.

The function should compute

[ ] Embedding map $latex phi:GF16\to GF256$ such that $phi x \mapsto phi*(y)$
[ ] A new basis $\latex B'$ such that of $latex GF256 = <B'>$ where $latex B' := {1, phi(x), phi(x)^2, phi(x)^3, y_1, y_2, y_3, y_4}$
[ ] Compute a new multiplication table base on $<B'>$.
[ ] The new multiplication table should pass the current embedding test in the code.

drskalman commented 3 years ago

[X] branch out of the current branch.
- [X] merge into field_trait branch
- [X] research best way of finding phi*: find the subfield generator instead
- [X] Implement enough linear algebera to compute determinant to make sure we are having a basis.
- [X] Implement the embed map

drskalman commented 3 years ago

Compiling and resolve errors, hit an error that look likes coming from merge. letting @burdges resolving it: e2ea89f

drskalman commented 3 years ago

ef3b617 passes embedded_gf16 test for minpoly 0x1D (GFNI) and 0x2D (gf-complete, clmul), the two other test minpolys (0x71 and 0x2B) fails to generate cantor basis so I can't test. I'll remerge with @burdges new commits and test again.