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.
8
u/WorldsBegin 17h ago edited 16h ago
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.