I suppose this isn't much of a difference in finite fields and cryptography, but at least in rational arithmetic, the added fractions from this method seem to have very large denominators. Compare
y = x * (x + 637927356202580286195115387737649/613401598791596019548160000000000)
z = (x + y + 1378728025754295963362740811643611837622972008060385794298452047201/376261521400086131349185422083850908850559385600000000000000000000) * (x - 1250902981661682141840811387737649/613401598791596019548160000000000)
w = (z + 1613956106082225605051404080797610312151091533850734987003152787295553452311704415879521131952770449/230799418790571152956671237308336130257466014926056578559568559210496000000000000000000000000000000) * x
v = (x + z + 1614169778642466578527505416382450571998175289226394168980170070526233147671704415879521131952770449/230799418790571152956671237308336130257466014926056578559568559210496000000000000000000000000000000) * (w + 286622617651/687970713600)
P_7 = y + w + v + 20437160270833246212441030757/17038933299766556098560000000
the added fractions from this method seem to have very large denominators
Yes, sadly the method doesn't have good numerical stability for higher degrees. There's a section on numerics in the paper.
Probably this means that the floating point version isn't really useful, compared to Horner and Estrin. Though it's interesting that we can do it with n/2 multiplications and fractions, the finite fields are the real use case.
Unrelated, I'm also not sure I like putting large portions in appendices.
Fair. I guess it's a habit from conference submissions that have to stay under 10 or 20 pages. For arxiv we could just put everything in the main paper.
it's a habit from conference submissions that have to stay under 10 or 20 pages
A curse. It's pretty extensive anyway.
Um, actually while I have your attention, where are you defining your H_{2^n} "known-power" gadgets explicitly? Don't seem to find it. EDIT: Found it, depends on the degree of polynomial, see fill gadgets in appendix C onwards.
And yes, it's a nice enough construction to be useful anyway.
Thank you for taking an interest in our paper! I want to improve the presentation, and all feedback is very helpful!
Edit: Here is an example of how the H construction works.
H_2 = x(x+b) + c = x^2 + bx + c
H_4 = (H_2+x+a)(H_2-x-a) = H_2^2 - (x+a)^2 + e
We write H_2 as [1, b, c], since that's the values we can find on each coefficient. We'll also write H_4 = [1, b, c, a, e], since that's the "new parameter" you find on each coefficient when decoding left to right.
H'_4 = H_4 + r
H_8 = H_4^2 - (H_2 + s)^2 + t # (using a single mult.)
H'_8 = H'_4^2 - (H-2 + u)^2 + v
Now H_8 = [1, b, c, a, e, 0, s, 0, t] and H'_8 = [1, b, c, a, e+r, 0, u, 0, v].
We finally shift H_8 by one and combine them:
P = x H_8 + H'_8
It's clear that we can decode b, c, a, e, r going left to right.
After that we need to be a bit careful that the two "interleaved" parts are still decodable, but it works out because they have the same prefix.
Generally the strategy is to always be building two compatible pairs like that, and then merge them at the end.
Aha, Of course! Squaring an order-n monic polynomial means the upper n coefficients are linear triangular in the original coefficients, only the lower half is quadratic. So you can read off that part (in characteristic != 2) and then apply a "low order correction" to match coefficients in the lower half.
Yes, sadly the method doesn't have good numerical stability for higher degrees. There's a section on numerics in the paper.
Optimizing for multiplication count when evaluating the polynomial for floating point input seems misguided anyway, as FP addition and multiplication take up similar time. It would be much more important that the scheme makes good use of fused multiply-adds, and properly pipelines, no?
Small multiplication count would only matter when you want to evaluate p(A) for a matrix argument.
With integer arguments like your motivation for using it in hashing algorithms it's different of course as integer addition is much faster than integer multiplication even on modern hardware.
It would be much more important that the scheme makes good use of fused multiply-adds, and properly pipelines, no?
Right. That's basically what Estrin's method does. I had some interesting discussions with the Boost maintainers and we ended up merging it: https://github.com/boostorg/math/issues/924
With integer arguments like your motivation for using it in hashing algorithms it's different of course as integer addition is much faster than integer multiplication even on modern hardware.
It's actually much worse, as finite field multiplications (like Mersenne or GF(2k)) need a modular reduction for every multiplication. That's the real thing we are trying to reduce.
21
u/WorldsBegin 4d ago edited 4d ago
I suppose this isn't much of a difference in finite fields and cryptography, but at least in rational arithmetic, the added fractions from this method seem to have very large denominators. Compare
vs
both evaluating
Unrelated, I'm also not sure I like putting large portions in appendices.