This issue serves as a note on EMP-ZK for a prime field that is not of a Mersenne prime, but with a high two-arity (aka, p - 1 has a large k for 2^k).

This is needed in some situations:

• Integration with SPDZ using HE-based preprocessing, where the homomorphic encryption is based on ring-LWE, and the plaintext field (where QuickSilver may integrate) has some 2-arity.
• Other situations probably involving ring LWE/SIS problems.

The code in this secret gist (https://gist.github.com/weikengchen/ac6de8086f2144bd3677e2771aaf015c) is an example of a prime field:

p = 2^{62} - 2^{26} - 2^{25} + 1

So it has a high two-arity of ~25.

The code in this secret gist (https://gist.github.com/weikengchen/1d7dbe19706f1c229741933323d00a8a) is an example of a prime field:

p = 2^{62} - 2^{16} + 1

So it has a high two-arity of ~16.

The second one is about 2.5x slower than the Mersenne prime, which may improve if we batch x >= p? x - p : x with vector instructions, which appears to contribute to a large part of the overhead. These two gists did not apply a few optimizations in the original version (which may be indeed worthwhile to look into).