Hi there! I’m trying to implement a modular exponentiation algorithm for the BGV ciphertexts. The idea is to be able to extend this algorithm for computing Fermat’s Little Theorem.

I have successfully implemented the algorithm for Plaintext Modulus p=65537 for up to a multiplicative depth of 13 iterations. For Fermat’s Little Theorem I need to compute a^65536, but this implicitly needs a multiplicative depth of 16 or 17. However, if I try to increase the multipicative depth, the following error arises:

Please provide a primeModulus(q) and a cyclotomic number(m) satisfying the condition: (q-1)/m is an integer. The values of primeModulus = 65537 and m = 131072 do not satisfy this condition

Related to this, is there any ‘list of suitable prime numbers’ to use in OpenFHE? It would be great to have this list of primes with their maxDepth, for developers to know what prime to choose deoending on the operations to be done on the ciphertexts.

You are using ultra-large parameters that we do not generally recommend. The default plaintext modulus used in the example should support reasonable ring dimensions.
Look at the last paragraph in this post. It should give you an idea about how to choose your prime modulus.

@dcousins - As long as the ring dimension is set appropriately (which is done automatically in OpenFHE), then there should be security issues. What I meant by not recommended settings above was merely based on the performance aspect.