search

LayerXcom / verified-vyper-contracts

FVyper: A collection of useful Vyper contracts developed with formal methods
Apache License 2.0
55 stars 15 forks source link

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

Open hskang9 opened 5 years ago

hskang9 commented 5 years ago

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

bird

nrryuya commented 5 years ago

@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 commented 5 years ago

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

hskang9 commented 5 years ago

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