Zero Knowlege Proof of Compositeness
6 months ago
- #Cryptography
- #Mathematics
- #Zero Knowledge Proof
- 零知识证明（ZKP）能够在仅揭示答案本身的前提下回答问题。
- 示例：通过展示其他花色仍在牌堆中，证明抽出的牌是黑桃而不透露具体是哪张牌。
- 费马素性检验可作为ZKP来证明某数为合数，同时不泄露其因数。
- 费马小定理指出：若n为素数且b不是n的倍数，则b^(n−1) ≡ 1 mod n。
- 当存在基数b使得b^(n−1) ≠ 1 mod n时，即可证明n为合数。
- 费马小定理无法确证某数为素数，只能证明其可能为素数。
- 零知识证明可应用于数学之外的领域，例如加密货币中用于验证交易约束而不暴露细节。
- 非构造性证明（如介值定理）可视为ZKP，因其能在不提供具体信息的情况下证明存在性。