[RSA Accumulator] Use Fermat Primality Test for verifying prime number

[hskang9]

Instead of testing with listed primes like this solidity prime tester, I propose other primality test here.

Fermat's Primality Test

in Fermat's primality test, if p is prime and a is an random integer,

a**(p-1) mod p = 1

For example, if a = 2, p = 17,

2**(17 - 1) mod 17 = 1 (prime)

Whereas a = 2, p = 16,

2**(16 - 1) mod 16 = 0 (not prime)

I just set a = 2 without varying it.

Conclusion

All I am worried for this algorithm is when calculating exponents which are bigger than uint256 can handle, but I see there is already functions for handling that.

Is there any way that we can implement this algorithm? If there is a blocking, what is it?

Cute Animal Picture

[nrryuya]

@hskang9
Thank you!

Is there any way that we can implement this algorithm? If there is a blocking, what is it?

Nothing! I'm welcome to your pull-request ;)
As I mentioned in #71, it might suffer from the code size problem.
It'd be better to have another isPrime.vy contract.

[nrryuya]

This seems good.
https://ethresear.ch/t/log-coins-sized-proofs-of-inclusion-and-exclusion-for-rsa-accumulators/3839/2

[hskang9]

Thank you for your acceptance and information! Please review this PR I made.