2025-11-30 00:53:35
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.
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.
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.
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.
[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.
The post Zero knowlege proof of compositeness first appeared on John D. Cook.2025-11-29 05:23:32
Monero has a way of generating new addresses analogous to the way HD wallets generate new addresses for Bitcoin. In both cases, the recipient’s software can generate new addresses to receive payments that others cannot link back to the recipient.
Monero users have two public/private keys pairs: one for viewing and one for spending. Let Ks and ks be the public and private spending keys, and let Kv and kv be the public and private viewing keys. Then the user’s ith subaddress is given by
Here G is a generator for the elliptic curve Ed25519 and H is a hash function. The hash function output and kv are integers; the public keys, denoted by capital Ks with subscripts and superscripts, are points on Ed25519. The corresponding private keys are
As with hierarchical wallets, the user scans the blockchain to see which of his addresses have received funds.
A user may choose to give a different subaddress for each transaction for added security, or to group transactions for accounting purposes.
Note that in addition to subaddresses, Monero uses stealth addresses. An important difference between subaddresses and stealth addresses is that recipients generate subaddresses, and senders generate stealth addresses. Someone could send you money to the same subaddress twice, failing to create a new stealth address. This is not possible if you give the sender a different subaddress each time.
2025-11-29 01:53:05
In spherical geometry, the interior angles of a triangle add up to more than π. And in fact you can determine the area of a spherical triangle by how much the angle sum exceeds π. On a sphere of radius 1, the area equals the triangle excess
Area = E = interior angle sum − π.
Small triangles have interior angle sum near π. But you could, for example, have a triangle with three right angles: put a vertex on the north pole and two vertices on the equator 90° longitude apart.
In hyperbolic geometry, the sum of the interior angles of a triangle is always less than π. In a space with curvature −1, the area equals the triangle defect, the difference between π and the angle sum.
Area = D = π − interior angle sum.
Again small triangles have an interior angle sum near π. Both spherical and hyperbolic geometry are locally Euclidean.
The interior angle sum can be any value less than π, and so as the angle sum goes to 0, the triangle defect, and hence the area, goes to π. Since the minimum angle sum is 0, the maximum area of a triangle is π.
The figure below has interior angle sum 0 and area π in hyperbolic geometry.
Strictly speaking this is an improper triangle because the three hyperbolic lines (i.e. half circles) don’t intersect within the hyperbolic plane per se but at ideal points on the real axis. But you could come as close to this triangle as you like, staying within the hyperbolic plane.
Note that the radii of the (Euclidean) half circles doesn’t change the area. Any three semicircles that intersect on the real line as above make a triangle with the same area. Note also that the triangle has infinite perimeter but finite area.
2025-11-28 22:54:46
Let ℍ be the upper half plane, the set of complex real numbers with positive imaginary part. When we measure distances the way we’ve discussed in the last couple posts, the geometry of ℍ is hyperbolic.
What is a circle of radius r in ℍ? The same as a circle in any geometry: it’s the set of points a fixed distance r from a center. But when you draw a circle using one metric, it may look very different when viewed from the perspective of another metric.
Suppose we put on glasses that gave us a hyperbolic perspective on ℍ, draw a circle of radius r centered at i, then take off the hyperbolic glasses and put on Euclidean glasses. What would our drawing look like?
In the previous post we gave several equivalent expressions for the hyperbolic metric. We’ll use the first one here.
Here the Fraktur letter ℑ stands for imaginary part. So the set of points in a circle of radius r centered at i is
Divide the expression for d(x + iy, i) by 2, apply sinh, and square. This gives us
which is an equation for a Euclidean circle. If we multiply both sides by 4y and complete the square, we find that the center of the circle is (0, cosh(r)) and the radius is sinh(r).
So to recap, if we put on our hyperbolic glasses and draw a circle, then switch out these glasses for Euclidean glasses, the figure we drew again looks like a circle.
To put it another way, a hyperbolic viewer and a Euclidean viewer would agree that a circle has been draw. However, the two viewers would disagree where the center of the circle is located, and they would disagree on the radius.
Both would agree that the center is on the imaginary axis, but the hyperbolic viewer would say the imaginary part of the center is 1 and the Euclidean viewer would say it’s cosh(r). The hyperbolic observer would say the circle has radius r, but the Euclidean observer would say it has radius sinh(r).
For small r, the hyperbolic and Euclidean viewpoints nearly agree because
cosh(r) = 1 + O(r²)
and
sinh(r) = r + O(r³)
Note that if you asked a Euclidean observer to draw a circle of radius 100, centered at (0, 1), he would say that the circle will extend outside of the half plane. A hyperbolic observer would disagree. From his perspective, the real axis is infinitely far away and so he can draw a circle of any radius centered at any point and stay within the half plane.
Now what if we looked at circles centered somewhere else? The hyperbolic metric is invariant under Möbius transformations, and so in particular it is invariant under
z ↦ x0 + y0z.
This takes a circle with hyperbolic center i to a circle centered at x0 + i y0 without changing the hyperbolic radius. The Euclidean center moves from cosh(r) to y0 cosh(r) and the radius changes from sinh(r) to y0 sinh(r).
The post A circle in the hyperbolic plane first appeared on John D. Cook.2025-11-27 21:14:40
The previous post described a metric for the Poincaré upper half plane. The development is geometrical rather than analytical. There are also analytical formulas for the metric, at least four that I’ve seen.
It’s not at all obvious that the four equations are equivalent, or that any of them matches the expression in the previous post.
There are equations for expressing arcsinh, arccosh, and arctanh in terms of logarithms and square roots. See the bottom of this post. You could use these identities to show that the metric expressions are equal, but I don’t know of a cleaner way to do this than lots of tedious algebra.
Before diving into the calculations, you might want some assurance that you’re trying to prove the right thing. Here’s some Python code that generates random pairs of complex numbers and shows that the four expressions give he same distance.
import numpy as np
def d1(z1, z2):
return 2*np.arcsinh( abs(z1 - z2) / (2*(z1.imag * z2.imag)**0.5) )
def d2(z1, z2):
return np.arccosh(1 + abs(z1 - z2)**2 / (2*z1.imag * z2.imag) )
def d3(z1, z2):
return 2*np.arctanh( abs( (z1 - z2)/(z1 - np.conjugate(z2)) ) )
def d4(z1, z2):
return 2*np.log( (abs(z2 - z1) + abs(z2 - np.conjugate(z1)))/(2*np.sqrt(z1.imag * z2.imag)) )
np.random.seed(20251127)
for n in range(100):
z1 = np.random.random() + 1j*np.random.random()
z2 = np.random.random() + 1j*np.random.random()
assert( abs(d1(z1, z2) - d2(z1, z2)) < 1e-13 )
assert( abs(d2(z1, z2) - d3(z1, z2)) < 1e-13 )
assert( abs(d3(z1, z2) - d4(z1, z2)) < 1e-13 )
Perhaps you’re convinced that the four expressions are equal, but why should any of them be equivalent to the definition in the previous post?
The previous post pointed out that the metric is invariant under Möbius transformations. We can apply such a transformation to move any pair of complex numbers to the imaginary axis. There you can see that the cross ratio reduces to the ratio of the two numbers.
More generally, if two complex numbers have the same real part, the distance between them is the log of the ratio of their imaginary parts. That is, if
then
if x, y1, and y2 are real and y2 > y1 > 0.
Here’s a little Python code that empirically shows that this gives the same distance as one of the expressions above.
def d5(z1, z2):
assert(z1.real == z1.real)
return abs( np.log( z1.imag / z2.imag ) )
for n in range(100):
x = np.random.random()
z1 = x + 1j*np.random.random()
z2 = x + 1j*np.random.random()
assert( abs(d1(z1, z2) - d5(z1, z2)) < 1e-13 )
So now we have five expressions for the metric, all of which look different. You could slug out a proof that they’re equivalent, or get a CAS like Mathematica to show they’re equivalent, but it would be more interesting to find an elegant equivalence proof.
Update: Although the four expressions at the top of the post are analytically equal, they are not all equally accurate for numerical evaluation. I did a little testing and found the arctahn method to be the least accurate and the rest roughly equally accurate.
The post Equal things that don’t look equal first appeared on John D. Cook.2025-11-27 02:28:14
One common model of the hyperbolic plane is the Poincaré upper half plane ℍ. This is the set of points in the complex plane with positive imaginary part. Straight lines are either vertical, a set of points with constant imaginary part, or arcs of circles centered on the real axis. The real axis is not part of ℍ. From the perspective of hyperbolic geometry these are ideal parts, infinitely far away, and not part of the plane itself.
We can define a metric on ℍ as follows. To find the distance between two points u and v, draw a line between the two points, and let a and b be the ideal points at the end of the line. By a line we mean a line as defined in the geometry of ℍ, what we would see from our Euclidean perspective as a half circle or a vertical line. Then the distance between u and v is defined as the absolute value of the log of the cross ratio (u, v; a, b).
Cross ratios are unchanged by Möbius transformations, and so Möbius transformations are isometries.
Another common model of hyperbolic geometry is the Poincaré disk. We can use the same metric on the Poincaré disk because the Möbius transformation
maps the upper half plane to the unit disk. This is very similar to how the Smith chart is created by mapping a grid in the right half plane to the unit disk.
Update: See the next post for four analytic expressions for the metric, direct formulas involving u and v but not the ideal points a and b.
The post Hyperbolic metric first appeared on John D. Cook.
