[Libre-soc-bugs] [Bug 782] add galois field bitmanip instructions

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=782

--- Comment #34 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to Jacob Lifshay from comment #31)
> (In reply to Jacob Lifshay from comment #30)
> > since GF(2^n) is a field, invert should be `gfdiv(1, v)` (since 1 is the
> > multiplicative identity) for all GF(2^n) values `v`.
> > 
> > the gcd algorithm is used for gf(p) for prime p, but there the mul, div, etc
> > are all integer div, mul, etc, not GF(n) operations. afaict you confused it
> > again.

almost certainly :)  much of what i'm doing is "hunt-the-algorithm"
(guess-work), then running unit tests to compensate.  run that loop
iteratively, fast enough, and it's indistinguishable from knowing
what the hell you're doing in the first place :)

> you can also use gfmul to compute gfdiv(a, b) in gf(2^n) is gfmul(a,
> gfpow(b, 2^n - 1)), where gfpow can be implemented using the standard
> squaring algorithm, giving runtime O(n * gfmul_time).

i remember this.  it's one of the really important features of GF, that
if you multiply enough times you get back to the original.


(In reply to Jacob Lifshay from comment #33)
> I found a paper that references a VLSI-optimized version of gfinv:
> https://scholar.archive.org/work/ktlygagf6jhslhx42gpuwwzc44/access/wayback/
> http://acsel-lab.com/arithmetic/arith18/papers/ARITH18_Kobayashi.pdf
> (Algorithm 3, from [7])

nice.  i'm glad you can read it!
i dropped a copy here https://ftp.libre-soc.org/ARITH18_Kobayashi.pdf

>             S(x) := S(x) − R(x); # polynomial subtraction aka. xor
>             V(x) := V(x) − U(x); # polynomial subtraction aka. xor

v. helpful, the comments.

> (U(x) = A^−1(x))

what's this one?  A to the power of "-1(x)" ?  oh wait, that's just
a declaration, "U *is* the inverse of A".  got it.

(In reply to Jacob Lifshay from comment #32)
> also, one important point worth considering: for elliptic curve
> cryptography, it may use GF(2^n) where n is much larger than what fits in a
> single register -- several hundred. we are likely to have the same issue
> with GF(p) where p is much larger than 2^64.

yes, i'm not sure what's the best option there.

oh wow, apparently doing an FFT is one option! holy cow
https://github.com/popcornell/pyGF2/blob/master/pyGF2/gf2_mul.py
https://github.com/popcornell/pyGF2/blob/master/pyGF2/gf2_inv.py

*splutter*

hey guess what? we have hardware-assisted FFT.... :)

-- 
You are receiving this mail because:
You are on the CC list for the bug.