Semantics of ext2mul

[Al-Kindi-0]

Currently, ext2mul is implemented as a sequence of 3 VM operations: EXT2MUL DROP DROP where EXT2MUL works as follows:

Inputs:  [b1, b0, a1, a0, ...]
Outputs: [b1, b0, c1, c1, ...]

Where (c0, c1) is the result of an extension field multiplication of (a0, a1) and (b0, b1). Basically, after the multiplication, (b0, b1) stays on the stack while (a0, a1) is overwritten with the result of the multiplication.

Having access to the raw MUL2EXT operation, some of the operations in the Falcon signature verification algorithm could be improved significantly. @bobbinth estimates a reduction in the overall cycle count in the order of 4K - 6K cycles for the whole Falcon verification procedure

Originally posted by @bobbinth in #1000 (comment)