Prime verification in const context
Opened this issue · 3 comments
It would be useful to be able to check if a number is prime or not in a const context.
Currently, the library const-primes provides such a feature, but only for built-in integer types. Would it be feasible to have this feature in this library for use with crypto-bigint::Uint ?
It's tricky to have an implementation which is both generic (i.e. over Uint and BoxedUint) as well as const fn-friendly, at least until impl const Trait lands. Not impossible (it requires using concrete types everywhere for the const fns) but tricky.
I'm curious what the use case is?
I al working on a pure rust implementation of CSIDH (which is a post-quantum algorithm for secret key exchange.) CSIDH is not yet standardized.
The parameters of the key exchange is any small set of (small, ie ~<500) prime numbers, such that p = (4 times their product minus 1) is prime. I woulk like to provide an API allowing anyone to define such parameters for their use-case (especially research purpose such as side-channel attacks), with a compile-time validation of the parameters.
To the best of my knowledge, doing this as I want would require multiple features of crypto-bigint and/or the Rust language. One of the features I would like is the const primality check of p, which is generally an integer of around 512 bits in CSIDH.
Another problem besides the const trait thing is that the current primality test requires an RNG. This perhaps can be worked around by seeding an RNG with a hash of the number being tested, but some research is needed to make sure it's actually safe to do. Primality certificates (see #9) are generally non-random, but will take more time to generate (although they could be pre-generated and hardcoded alongside primes, and tested during compilation).