Zero knowlege proof of compositeness

Skip to content
MATH

PROBABILITY
SIGNAL PROCESSING
NUMERICAL COMPUTING
SEE ALL …

STATS

EXPERT TESTIMONY
WEB ANALYTICS
FORECASTING
RNG TESTING
SEE ALL …

PRIVACY

HIPAA
SAFE HARBOR
CRYPTOGRAPHY
DIFFERENTIAL PRIVACY
PRIVACY FAQ

WRITING

BLOG
RSS FEED
TWITTER
SUBSTACK
ARTICLES
TECH NOTES

ABOUT

CLIENTS
ENDORSEMENTS
TEAM
SERVICES

(832) 422-8646
Contact

Zero knowlege proof of compositeness

Posted on 29 November 2025 by John

A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key.
Here’s another example, one that’s more concrete than a digital signature. Suppose you have a deck of 52 cards, 13 of each of spades, hearts, diamonds, and clubs. If I draw a spade from the deck, I can prove that I drew a spade without showing which card I drew. If I show you that all the hearts, diamonds, and clubs are still in the deck, then you know that the missing card must be a spade.
Composite numbers
You can think of Fermat’s primality test as a zero knowledge proof. For example, I can convince you that the following number is composite without telling you what its factors are.
n = 244948974278317817239218684105179099697841253232749877148554952030873515325678914498692765804485233435199358326742674280590888061039570247306980857239550402418179621896817000856571932268313970451989041
Fermat’s little theorem says that if n is a prime and b is not a multiple of n, then
bn−1 = 1 (mod n).
A number b such that bn−1 ≠ 1 (mod n) is a proof that n is not prime, i.e. n is composite. So, for example, b = 2 is a proof that n above is composite. This can be verified very quickly using Python:
>>> pow(2, n-1, n)
10282 ... 4299

I tried the smallest possible base [1] and it worked. In general you may have to try a few bases. And for a few rare numbers (Carmichael numbers) you won’t be able to find a base. But if you do find a base b such that bn−1 is not congruent to 1 mod n, you know with certainty that b is composite.
Prime numbers
The converse of Fermat’s little theorem is false. It can be used to prove a number is not prime, but it cannot prove that a number is prime. But it can be used to show that a number is probably prime. (There’s some subtlety as to what it means for a number to probably be prime. See here.)
Fermat’s little theorem can give you a zero knowledge proof that a number is composite. Can it give you a zero knowledge proof that a number is prime? There are a couple oddities in this question.
First, what would it mean to have a zero knowledge proof that a number is prime? What knowledge are you keeping secret? When you prove that a number is composite, the prime factors are secret (or even unknown), but what’s the secret when you say a number is prime? Strictly speaking a ZKP doesn’t have to keep anything secret, but in practice it always does.
Second, what about the probability of error? Zero knowledge proofs do not have to be infallible. A ZKP can have some negligible probability of error, and usually do.
It’s not part of the definition, but n practice ZKPs are supposed to be easier to verify than the direct approach to what they prove. So you could have something like a primality certificate that takes far less computation to verify than the computation needed to determine from scratch that a number is prime.
Proving other things
You could think of non-constructive proofs as ZKPs. For example, you could think of the intermediate value theorem as a ZKP: it proves that a function has a zero in an interval without giving you any information about where that zero may be located.
What makes ZKPs interesting in application is that they can prove things of more general interest than mathematical statements [2]. For example, cryptocurrencies can provide ZKPs that accounting constraints hold without revealing the inputs or outputs of the transaction. You could prove that nobody tried to spend a negative amount and that the sum of the inputs equals the sum of the outputs.
Related posts

Lewis Carroll and ZKP
Primality certificates
Proof of optimization

[1] You could try b = 1, but then bn−1 is always 1. This example shows that the existence of a base for which bn−1 = 1 (mod n) doesn’t prove anything.
[2] You might object that accounting rules are mathematical statements, and of course they are. But they’re of little interest to mathematicians and of great interest to the parties in a transaction.

Categories : MathTags : Number theoryBookmark the permalink

Post navigation
Previous PostMonero subaddresses

Leave a ReplyYour email address will not be published. Required fields are marked *Comment * Name *
Email *
Website

Δ

Search for:

John D. Cook, PhD

My colleagues and I have decades of consulting experience helping companies solve complex problems involving data privacy, applied math, and statistics.
Let’s talk. We look forward to exploring the opportunity to help your company too.

John D. Cook
© All rights reserved.

Search for:

(832) 422-8646

EMAIL

Zero knowledge proof of compositeness

A zero-knowledge proof (ZKP) demonstrates the validity of a statement without revealing any additional information beyond the fact that the statement is true. This concept is illustrated through various examples, including digital signatures and verification of properties within mathematical systems. A concrete example involves demonstrating the compositeness of a number, such as the large number presented: n = 244948974278317817239218684105179099697841253232749877148554952030873515325678914498692765804485233435199358326742674280590888061039570247306980857239550402418179621896817000856571932268313970451989041. The principle relies on Fermat’s Little Theorem, which states that if *n* is a prime number and *b* is not divisible by *n*, then *b*^*n* - 1 = 1 (mod *n*). A composite number can be demonstrated by selecting a base *b* for which *b*^*n* - 1 is not congruent to 1 modulo *n*. For instance, attempting to use *b* = 2 produces a result where *b*^*n* - 1 is not congruent to 1 mod *n*, providing definitive proof of the number’s compositeness. This verification is efficiently achieved through Python, where `pow(2, n-1, n)` returns 10282...4299, confirming the non-congruence. The selection of a base *b* is crucial; attempting *b* = 1 yields a consistent result of 1, demonstrating that the existence of a base that satisfies the theorem does not provide specific information about *n*.

The concept extends to broader applications of zero-knowledge proofs. Non-constructive proofs, such as the Intermediate Value Theorem, can be viewed as ZKPs, proving the existence of a zero in a given interval without revealing its precise location. The interest in ZKPs arises from their ability to simplify verification processes. Specifically, a primality certificate – a proof that a number is likely prime – can be verified much more quickly than performing the computationally intensive calculations required to determine primality from scratch. This efficiency has significant implications for applications like cryptocurrencies, where ZKPs can demonstrate that transaction constraints are upheld (e.g., preventing negative spending amounts) without revealing the details of those transactions.

Furthermore, ZKPs represent a powerful tool beyond traditional mathematical proofs. They can be employed to verify properties of greater practical relevance, such as those found in accounting, where the confidentiality of transaction data is paramount. The utility of ZKPs hinges on their capacity to provide assurance without divulging sensitive information, offering a novel approach to security and data integrity across diverse fields.