Zero Knowlege Proof of Compositeness
12 days ago
- #Cryptography
- #Mathematics
- #Zero Knowledge Proof
- A zero knowledge proof (ZKP) answers a question without revealing anything more than the answer.
- Example: Proving a drawn card is a spade without revealing which card by showing all other suits remain in the deck.
- Fermat’s primality test can act as a ZKP to show a number is composite without revealing its factors.
- Fermat’s little theorem states that if n is prime and b is not a multiple of n, then b^(n−1) ≡ 1 mod n.
- A base b where b^(n−1) ≠ 1 mod n proves n is composite.
- Fermat’s little theorem cannot prove a number is prime, only that it is probably prime.
- ZKPs can be applied beyond mathematics, such as in cryptocurrencies to verify transaction constraints without revealing details.
- Non-constructive proofs, like the intermediate value theorem, can be viewed as ZKPs as they prove existence without specifics.