Faster computation of quotient polynomial for large rotation sets

[jonathanpwang]

https://github.com/privacy-scaling-explorations/halo2/blob/246ce4e8e309138373ac32915654df5c463d5e70/halo2_proofs/src/poly/kzg/multiopen/shplonk/prover.rs#L25

The current division algorithm is O(N * R) where N is degree of polynomial and R is size of rotation set. For small R this is optimal, but as an improvement for larger R we may consider adding a separate FFT-based algorithm to do it in O(N log N). Just flagging this as a possibility, maybe in practice no one uses close to log N number of rotations.

Here's a random reference implementation with further references: https://stackoverflow.com/a/44854935

[CPerezz]

IIRC the max Rotation we have is 20something. Maybe this was reduced in the last months. @han0110 will be able to clarify.

From there we can judge whether to implement this or not.

[jonathanpwang]

In that case since N is around 2^20 anyways probably there's no immediate need. It'd only be potentially interesting if we have some gates that all access the same set of >20 rotation offsets (so the shplonk verification is cheap, and this would make prover computation cheap).

[CPerezz]

I completelly agree! And wouldn't be harmfull at all. So definitely worth exploring at some point. I'm not sure if we will prioritize this item. But definitely will be happy to recieve PRs implementing it!

[davidnevadoc]

It seems that this optimization wouldn't make an improvement in most common cases (where R< logN).