2025-10-09 08:27:24
Here’s a differential equation from [1] that’s interesting to play with.
Even though it’s a nonlinear system, it has a closed-form solution, namely
where (a, b, c) is the solution at t = 0 and Δ = 1 + a² + b² + c².
The solutions lie on the torus (doughnut). If m and n are coprime integers then the solutions form a closed loop. If the ratio m/n is not rational then the solutions are dense on the torus.
Here’s an example with parameters a = 1, b = 1, c = 3, m = 3, and m = 5.
And now with parameters a = 1, b = 1, c = 0.3, m = 4, and m = 5.
And finally with parameters a = 1, b = 1, c = 0.3, m = π, and m = 5.
[1] Richard Parris. A Three-Dimensional System with Knotted Trajectories. The American Mathematical Monthly, Vol. 84, No. 6 (Jun. – Jul., 1977), pp. 468–469
The post Differential equation on a doughnut first appeared on John D. Cook.2025-10-08 21:41:26
My interest in cryptocurrency is primarily technical, and privacy coins are the most technically interesting. The math behind coins like Monero and Zcash is far more sophisticated than the math behind Bitcoin.
I’m also interested in the privacy angle since I work in data privacy. The zero-knowledge proof (ZKP) technology developed for and tested in privacy coins is applicable outside of cryptocurrency.
I don’t follow the price of privacy coins, but I heard about the price of Zcash doubling recently.
I’d like to understand why that happened, especially why it happened so suddenly, though I’m very skeptical of post hoc explanations of price changes. I roll my eyes when I hear reporters say the stock market moved up or down by some percent because of this or that event. Any explanation for the aggregate behavior of a complex system that fits into sound byte is unlikely to contain more than a kernel of truth.
Naval Ravikant said on October 1
Bitcoin is insurance against fiat.
ZCash is insurance against Bitcoin.
This was after Zcash had started rising, so Naval’s statement wasn’t the cause of the rise. But the idea behind his statement was in the air before he crystalized it. Maybe the recent increase in the price of Bitcoin led to the rise of Zcash as a hedge against Bitcoin falling. It’s impossible to know. Traders don’t fill out questionnaires explaining their motivations.
It has been suggested that more people are interested in using Zcash as a privacy-preserving currency, not just buying it for financial speculation. It’s plausible that this could be a contributing factor in the rise of Zcash, though interest in financial privacy is unlikely to spike over the course of one week, barring something dramatic like FDR’s confiscation of private gold in 1933.
The price of Monero increased along with Zcash, though not as by nearly as much.
This suggests there may be increased interest in privacy coins more generally and not just in Zcash.
It would be interesting to see how people are using Zcash and Monero—how much is being spent on goods and services and how much is just being traded as an investment—but this would be difficult since privacy coins obscure the details of transactions by design.
2025-10-07 22:43:02
Typically RSA public keys are the product of two large primes, n = pq. But there’s no reason they couldn’t be the product of say three primes, n = pqr, or more primes, as long as φ(n), or λ(n), is calculated correctly.
Encryption is done the same way. Decryption could be done the same way, except there is the opportunity for it to be more efficient. The trick is to use the CRT (Chinese Remainder Theorem) in a way similar to Garner’s algorithm. This is why RSA with multiple primes is sometimes used for digital signatures.
The difficulty of factoring n using the GNFS algorithm doesn’t change depending on the number of factors n has, as long as all the factors are sufficiently large, far too large to find using trial division.
Daniel Bernstein’s post-quantum RSA paper was based on keys that are the product of a large number of 4096-bit primes. This way all the arithmetic is carried out modulo 4096-bit primes, not modulo terabyte primes.
The post RSA with multiple primes first appeared on John D. Cook.2025-10-07 01:09:19
In an inflationary economy, the purchasing power of your currency continually deteriorates. If you have an investment that grows slower than your purchasing power shrinks, you’re actually losing value over time. The true rate of growth is the rate of change in the purchasing power of your investiment.
If the inflation rate is r and the rate of growth from your investment is i, then intuitively the true rate of growth is
g = i − r.
But is it? That depends on whether your investment and inflation compound periodically or continuously [1].
If you start with an investment P, the amount of currency in the investment after compounding n times will be
P(1 + i)n.
But the purchasing power of that amount will be
P(1 + i)n (1 + r)−n.
If the principle were invested at the true rate of growth, its value at the end of n periods would be
P(1 + g)n.
So setting
P(1 + i)n (1 + r)−n = P(1 + g)n
gives us
g = (i − r) / (1 + r).
The true rate of growth is less than what intuition would suggest. To achieve a true rate of growth g, you need i > g, i.e.
i = g + rg + r.
With continuous compounding, an invent of P for time T becomes
P exp(iT)
and has purchasing power
P exp(iT) P exp(−rT).
If
P exp(iT) P exp(−rT) = P exp(gT)
then
g = i − r
as expected.
It’s mathematically interesting that discrete and continuous compounding work differently when inflation is taken into account. But there are practical consequences.
Someone astutely commented that inflation really compounds continuously. It does, and not at a constant rate, either. But suppose we find a value of the monthly inflation rate r equivalent to the true annual rate. And suppose you’re in some sort of contract that pays monthly interest i. Then your true rate of growth is (i − r) / (1 + r), not (i − r).
If r is small, the difference between (i − r) / (1 + r) and (i − r) is small. But the larger r is, the bigger the difference is. As I’ve written about before, hyperinflation is counterintuitive. When r is very large, (i − r) / (1 + r) is much less than (i − r).
[1] Robert C. Thompson. The True Growth Rate and the Inflation Balancing Principle. The American Mathematical Monthly, Vol. 90, No. 3 (Mar., 1983), pp. 207–210
The post True growth rate accounting for inflation first appeared on John D. Cook.2025-10-06 21:25:33
An RSA public key is a pair of numbers (e, n) where e is an exponent and n = pq where p and q are large prime numbers. The original RSA paper said choose a private key d and compute e. In practice now we choose e and compute d. Furthermore, e is now almost always 65537 for reasons given here. So the public key is essentially just n.
The relationship between the exponent and the private decryption key in the original RSA paper was
ed = 1 mod φ(n).
It is easy to compute e given d, or d given e, when you know Euler’s totient function of n,
φ(n) = (p − 1)(q − 1).
The security of RSA encryption rests on the assumption that it is impractical to compute φ(n) unless you know p and q.
Gradually over the course of several years, the private key d changed from being the solution to
ed = 1 mod φ(n)
to being the solution to
ed = 1 mod λ(n)
where Euler‘s totient function φ(n) was replaced with Carmichael‘s totient function λ(n).
The heart of the original RSA paper was Euler’s generalization of Fermat’s little theorem which says if a is relatively prime to m, then
aφ(n) = 1 (mod n)
Carmichael’s λ(n) is defined to be the smallest number that can replace φ(n) in the equation above. It follows that λ(n) divides φ(n).
Using Carmichael’s totient rather than Euler’s totient results in smaller private keys and thus faster decryption. When n = pq for odd primes p and q,
λ(n) = lcm( (p − 1), (q − 1) ) = (p − 1)(q − 1) / gcd( (p − 1), (q − 1) )
so λ(n) is smaller than φ(n) by a factor of gcd( (p − 1), (q − 1) ). At a minimum, this factor is at least 2 since p − 1 and q − 1 are even numbers.
However, an experiment suggests this was a trivial savings. When I generated ten RSA public keys the gcd was never more than 8.
from sympy import randprime, gcd
for _ in range(10):
p = randprime(2**1023, 2**1024)
q = randprime(2**1023, 2**1024)
print(gcd(p-1, q-1))
I repeated the experiment with 100 samples. The median of the gcd’s was 2, the mean was 35.44, and the maximum was 2370. So the while gcd might be moderately large, but it is usually just 2 or 4.
The efficiency gained from using Carmichael’s totient is minimal. More efficiency can be gained by using Garner’s algorithm.
The post A quiet change to RSA first appeared on John D. Cook.2025-10-06 06:43:05
The nth Fermat number is defined by
Pierre Fermat conjectured that the F(n) were prime for all n, and they are for n = 0, 1, 2, 3, and 4, but Leonard Euler factored F(5), showing that it is not prime.
The nth tangent number is defined by the Taylor series for tangent:
Another way to put it is that the exponential generating function for T(n) is tan(z).
Here’s a remarkable connection between Fermat numbers and tangent numbers, discovered by Richard McIntosh as an undergraduate [1]:
F(n) is prime if and only if F(n) does not divide T(F(n) − 2).
That is, the nth Fermat number is prime if and only if it does not divide the (F(n) − 2)th tangent number.
We could duplicate Euler’s assessment that F(5) is not prime by showing that 4294967297 does not divide the 4294967295th tangent number. That doesn’t sound very practical, but it’s interesting.
Update: To see just how impractical the result in this post would be for testing whether a Fermat number is prime, I found an asymptotic estimate of tangent numbers on OEIS, and estimated that the 4294967295th tangent number has about 80 billion digits.
[1] Richard McIntosh. A Necessary and Sufficient Condition for the Primality of Fermat Numbers. The American Mathematical Monthly, Vol. 90, No. 2 (Feb., 1983), pp. 98–99
The post Fermat primes and tangent numbers first appeared on John D. Cook.
