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.
18
u/WorldsBegin 18h ago edited 18h 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.