Faster exponentiations

[dvdplm]

The idea is described in Multiplication/exponentiation speed-ups, step 4: when the exponent is big and the totient is known it's faster to do x^(y mod phi(N)) mod N than x^y mod N.

I added a synthetic benchmark to check the speedup and it's substantial, roughly 2x, so it looked like this is indeed something worth investigating.

Next task was to find spots in the code where the exponent is larger than N and I landed on RPParams::commit because here we're doing two exponentiations, the totient is known and exponents are large. I added a benchmark for this to have a proper baseline. In hindsight it would perhaps have been better to find a different place in the code, but this is what I did.

Original code:

    /// Creates a commitment for a secret `value` with a secret `randomizer`.
    pub fn commit<V, R>(&self, value: &V, randomizer: &R) -> RPCommitment<P>
    where
        P::UintMod: Exponentiable<V> + Exponentiable<R>,
    {
        RPCommitment(self.base_value.pow(value) * self.base_randomizer.pow(randomizer))
    }

The commit method is called with different types: SecretSigned, SecretUnsigned and PublicSigned, each wrapping an Integer of different sizes. I found it very tricky to juggle the trait bounds to make an Exponentiable reducible by a P::Uint. I spent two days on various approaches here, adding a pow_with_totient() method to the Exponentiable trait, adding a new PowWithTotient trait etc. I ultimately failed to get anything even vaguely satisfying (or even working).

At this point I did not even know if it'd be worth the effort to make the optimization, so I decided to go dirty and add a reduce_by method to each of the three types (SecretSigned, SecretUnsigned and PublicSigned) and then manually check which calls to commit use which types and which ones can be reduced.
This works, although it'd need cleanup to be worthwhile considering to merge, and requires a new public trait RemMixed in crypto-bigint to expose rem_wide_vartime that lets us reduce a bigger operand by a smaller one (pretty odd this is not exposed already tbh?). EDIT: a new RemMixed trait was accepted in #746.

FacProof benchmark results

The FacProof benchmark results of this hacky approach are a bit odd. Constructing the proof is marginally faster, 2-5%, but verifying is ~30% faster and note that I did not change any code at all in the verify code. My best guess is that the commitments are smaller and quicker to process?

Exponent mod-totient

fac proof/prove         time:   [56.432 ms 56.558 ms 56.689 ms]
                        change: [-1.8506% -1.4611% -1.0478%] (p = 0.00 < 0.05)
                        Performance has improved.
fac proof/verify        time:   [28.068 ms 35.863 ms 43.869 ms]
                        change: [-27.909% -0.2881% +38.566%] (p = 0.98 > 0.05)
                        No change in performance detected.



Unoptimized

fac proof/prove         time:   [59.434 ms 59.612 ms 59.846 ms]
                        change: [+4.9976% +5.3997% +5.8940%] (p = 0.00 < 0.05)
                        Performance has regressed.
fac proof/verify        time:   [45.566 ms 47.685 ms 49.706 ms]
                        change: [+8.1607% +32.964% +70.969%] (p = 0.01 < 0.05)
                        Performance has regressed.

Avenues to explore further

• Build a more comprehensive proof generation/verification benchmark suite. I picked FacProof for this work, but that was a random choice. Do the speedups hold for the other proofs? [Benchmarks for ZK proofs #173], but need to check if reduce_by helps here at all.
• The RPParams::commit method seems like it could be a candidate for multi-exponention: it's literally doing x1 ^ k1 * ... * xn ^ kn, but I suspect it'd take some annoying trait bounds-fiddling to make it work. Worth it?
• At the outset I looked for big exponents to test out the mod totient idea and landed on RPParams::commit but perhaps there are other more promising places I should look at?
• Are our bounds always as tight as they can be? Could we for instance look closer at random_in_exp_range_scaled and see if we can trim it down? EDIT: Investigated this and it's a dead end
• Check with Tony A if he'd be open to a RemWide trait EDIT: Done in #746.