Comments aligning FFT code to paper

burdges commented 3 years ago

Issue that still require understanding:

[ ] (19) page 6286 in the proof of Lemma 4. Also some details of Lemma 2 I guess.
[x] Indexing by \omega_{j 2^{i-1}}
[ ] Why skip that loop when skew != MODULUS not skew != 0?
[ ] Only one skew factor is required per j interdependent of r, probably (19) here. https://github.com/catid/leopard/issues/16#issuecomment-780984320
[ ] Layout of SKEW_FACTOR, like it only being field sized, not field sized times log of field size, probably (19) here too.
[ ] Computation of SKEW_FACTOR

burdges commented 3 years ago

At least I've found the definition of \omega_{j 2^{i-1}} now: Section II A on page 6285 defines \omega_i = i_0 v_0 + i_1 v1 + ... i{m-1} v_{m-1} where i=i_0 + 2 i1 + .. + 2^{m-1} i{m-1}. So \omega_{j 2^{i-1}} means exactly this but with j left shifted by i-1 bits, which corresponds to the range the code's j takes.

As we never touch index, the code can only be correct if \bar{s}i(\omega) = \bar{s}{i-1}(\omega), which seems transparently false for s_i. It's true \bar{s}_i(v_i) = 1, do this would make them identically 1, and this it's transparently false for s_i. This looks like a bug.

burdges commented 3 years ago

I'm not 100% sure about renaming base to field base in 02b3b517cfccb7326532bd61a4cd1a567186bca0 but what might happen there is they work in an altered base to compute the s_j using (8).

drahnr / rs-ec-perf

Comments aligning FFT code to paper #2