Author: John

Moessner’s Magic

Posted on by John

The sum of the first n odd numbers is n². For example,

1 + 3 + 5 + 7 + 9 = 25 = 5²

Here’s another way to say the same thing. Start with the list of positive integers, remove every second integer from the list, and take the cumulative sum. The resulting list is the list of squares.

We begin with

1, 2, 3, 4, 5, …

then have

1, 3, 5, 7, 9, …

and end up with

1, 4, 9, 16, 25, …

Cubes

Now start over with the list of positive integers. We’re going to remove every third integer, take the cumulative sum, then remove every second integer, and take the cumulative sum. The result is a list of cubes.

Here are the steps described above for the positive integers up to 20:

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, …, 20
1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20
1, 3, 7, 12, 19, 27, 37, 48, 61, 75, 91, 108, 127, 147
1, 7, 19, 37, 61, 91, 127
1, 8, 27, 64, 125, 216, 343

General case

In general, given an integer k we remove every kth element, take the cumulative sum. Then we reduce k by 1 and repeat. We keep doing this until k = 1, in which case we stop. The end result will be the list of kth powers.

The result at the top of the post, corresponding to k = 2, has been known since ancient times. The generalization to larger k wasn’t known until Alfred Moessner observed it in 1951. Oskar Perron proved Moessner’s conjecture later the same year. The result has been called Moesnner’s theorem or Moesnner’s magic.

Python implementation

A little Python code will make it easier to play with Moessner’s process for larger numbers.

from numpy import cumsum

def moessner(N, k):
    x = range(1, N+1)
    while k > 1:
        x = [x[n] for n in range(len(x)) if n % k != k - 1]
        # print(x)
        x = cumsum(x)
        # print(x)
        k = k - 1
    return x

To see the intermediate steps, uncomment the print statements.

If we run the following code

for k in [2, 3, 4, 5]:
    print( moessner(25, k) )

we get the following.

[1   4   9  16  25  36  49  64  81 100 121 144 169]
[1   8  27  64 125 216 343 512 729]
[1   16   81  256  625 1296 2401]
[1   32  243 1024 3125]

Related posts

Equivalence between commonly used elliptic curves

Posted on by John

The elliptic curves Curve25519 and Ed25519 are both commonly used in applications. For example, Curve25519 is used in Proton Mail and Ed25519 is used in SSH.

The two curves are related, as the numerical parts in their names suggest. The two curves are equivalent in some sense that we will describe below.

An algebraic geometer would say that Curve25519 and Ed25519 are not isomorphic, but a cryptographer would say that they are isomorphic. That’s because the algebraic geometer cares about more structure than the cryptographer does.

Curve25519 is given by

M: v² = u³ + 486662u² + u

over the field Fq where q = 2255 − 19.

Ed25519 is given by

E: y² − x² = 1 − (121665/121666) x² y²

over the same field. The “25519” part of both names comes from q.

We use M for Curve25519 because it is a Montgomery curve, named after Peter Montgomery. We use E for Ed25519 because it is a twisted Edwards curve, named after Harold Edwards.

The algebraic geometer would say M and E are not isomorphic as algebraic curves [1] because the curves are not the same in all their structure. However, the cryptographer isn’t interested in elliptic curves per se, only the additive group that is defined on elliptic curves, and these groups are isomorphic. The isomorphism can be given by

x = √486664 u/v

y = (u − 1)/(u + 1)

Here √486664 is a square root mod q and division means multiplication by the multiplicative inverse mod q.

Even though the group isomorphism is simple and explicit, it’s not simple to prove that it is a group isomorphism. For a proof, see [2].

So if the additive groups of the two curves are isomorphic, why use one in some applications rather than the other? Each is used where its implementation is more efficient. Ed25519 is typically used in digital signatures (for example, in Monero) and Curve25519 is typically used in key exchange (for example, in secure web pages).

Related posts

[1] The map between (u, v) and (x, y) does serve as an isomorphism between the group structures. But it is a “birational equivalence” rather than an isomorphism because it has singularities at (−1, 0) and (0, 0).

[2] Daniel J. Bernstein, Tanja Lange, Faster addition and doubling on elliptic curves, in Asiacrypt 2007 [49] (2007), 29–50. URL: http://eprint.iacr.org/2007/286.

Monero’s elliptic curve

Posted on by John

Monero logo
Digital signatures often use elliptic curves. For example, Bitcoin and Ethereum use the elliptic curve secp256k1 [1]. This post will discuss the elliptic curve Ed25519 [2] using in Monero and in many other applications.

Ed25519 has the equation

y² − x² = 1 + d x² y²

over the finite field Fq where q = 2255 − 19 and d = −121665/121666. The general form of the equation above makes Ed25519 a “twisted Edwards curve.”

The expression for d is not the rational number it appears to be. Think of it as

d = −121665 × 121666−1

where the multiplication and the multiplicative inverse are calculated mod q.

We could calculate d in Python as follows.

>>> q = 2**255 - 19
>>> d = (-121665*pow(121666, -1, q)) % q
>>> d 
37095705934669439343138083508754565189542113879843219016388785533085940283555

The equation above does not look like an elliptic curve if you think of an elliptic curve having the form

y² = x³ + ax + b.

But that form, known as Weierstrass form, is not the most general definition of an elliptic curve. Elliptic curves can be written in that form [3] but they do not have to be. There are computational advantages to writing curves in the form

y² − x² = 1 + d x² y²

when possible rather than in Weierstrass form [4].

Elliptic curve digital signatures require a specified base point. The Monero whitepaper describes the base point simply as

G = (x, −4/5).

That’s leaving out a fair bit of detail. First of all, 4/5 is interpreted as 4 times the multiplicative inverse of 5 mod q, similar to the calculation for d above.

>>> y = (-4*pow(5, -1, q)) % q; y
11579208923731619542357098500868790785326998466564056403945758400791312963989

Now we have two tasks. How do we solve for x, and which solution do we take?

We need to solve

x² = (y² − 1)/(1 + d y²) mod q.

We can do this in Python as follows.

>>> from sympy import sqrt_mod
>>> roots = sqrt_mod((y**2 - 1)*pow(1 + d*y**2, -1, q), q, all_roots=True)
>>> roots 
[15112221349535400772501151409588531511454012693041857206046113283949847762202,
42783823269122696939284341094755422415180979639778424813682678720006717057747]

So which root to we choose? The convention is to use the even solution, the first one above. (The two roots add to 0 mod q; one will be odd and one will be even because q is odd.)

We can verify that (x, y) is on the Ed25519 elliptic curve:

>>> ((y**2 - x**2) - (1 + d*x**2 * y**2)) % q
0

Related posts

[1] The name secp256k1 was created as follows. The “sec” comes from “Standards for Efficient Cryptography,” referring to the group that specified the curve parameters. The “p” means the curve is over a finite field of prime order. The order of the curve is slightly less than 2256. The “k” indicates that this is a Koblitz curve.

[2] The “Ed” part of the name refers to Harold Edwards, the mathematician who studied the family of elliptic curves now known as Edwards curves. The “25519” part of the name refers to the fact that the curve is over the finite field with 2255 − 19 elements.

[3] Provided the elliptic curve is not over a field of characteristic 2 or 3.

[4] Group operations can be implemented more efficiently and the point at infinity can be handled without exception logic.

Retrofitting error detection

Posted on by John

Bitcoin addresses include a checksum. The Base58Check algorithm uses the first four bytes of a hash function as a checksum before applying Base58 encoding.

Ethereum addresses did not include a checksum, but it became apparent later that a checksum was needed. How can you retroactively fit a checksum into an address without breaking backward compatibility? Here’s what Ethereum did in adopting the EIP-55 proposal.

Ethereum addresses are the last 20 bytes (40 hexadecimal characters) of the Keccak-256 hash of the public key. The protocol allowed the letters in hexadecimal addresses to be either upper or lower case. This option provided the wiggle room to retrofit a checksum. You could mix upper and lower case letters deliberately to encode an extra message (i.e. a checksum) on top of the key. This is sorta like steganography, except that it’s out in the open rather than hidden.

Hexadecimal notation uses 10 digits and 6 letters, and so the probability that a hexadecimal character is a letter is 6/16. On average a string of 40 hexadecimal characters will contain 15 letters. This means you could add 15 bits of information to an Ethereum address, on average, by alternating the case of the letters.

It’s conceivable that an address won’t contain any letters, or will consist entirely as letters. The number of letters in a random string of 40 hexadecimal characters is a binomial random variable with parameters n = 40 and p = 3/8, and this is approximately a normal random variable with mean 15 and standard deviation 3. This says the number of letters in an Ethereum address will be fairly tightly clustered around 15, rarely more than 21 or less than 9.

OK, but how do you take advantage of an average of 15 bits of freedom? You can’t encode a 15-bit number because you might not have 15 bits at your disposal.

Here’s what EIP-55 did. Left-align the address and the Keccek-256 hash of the address (which was itself a hash: there are two hashes going on) and capitalize all letters in the address that align with a character in the hash greater than or equal to 8.

As an example, let’s suppose our address is

    7341e5e972fc677286384f802f8ef42a5ec5f03b

This address contains 13 letters, which would not be unusual. Now let’s compute its hash.

    >>> from Crypto.Hash import keccak
    >>> kh = keccak.new(digest_bits=256)
    >>> kh.update(b"7341e5e972fc677286384f802f8ef42a5ec5f03b").hexdigest()
    'd8e8fcb225fb835fdb89a5918e736820ec75b3efaf3cbb229f03cdc41bf9f254'

Now we line up the address and its hash.

    341e5e972fc677286384f802f8ef42a5ec5f03b
    d8e8fcb225fb835fdb89a5918e736820ec75b3e...

The characters in the address that line up with a hash character of 0x8 through 0xf are highlighted red. The digits will be left alone, but the red letters will be turned to upper case.

    341E5E972fc677286384F802F8ef42a5EC5f03B

Related posts

A bank note with 21 implicit zeros

Posted on by John

When I wrote about hyperinflation the other day I included an image of a 100 trillion dollar note from Zimbabwe. This is almost a cliché: everyone using this image when talking about hyperinflation.

But Zimbabwe’s 1014 dollar note was not the largest denomination ever used. In 1946, Hungary circulated at 100 quintillion (1020) pengő note. It also printed, but did not circulate, a sextillion (1021) pengő note.

Hungarian quintillion note

The note from Hungary doesn’t have the shock value of the one from Zimbabwe because the zeros are not explicitly written out. The note is for one millard (109) b. pengő, where the “b” stands for “billion,” which in the Hungarian use of the word is 1012. It’s understandable that a state would avoid making the worthlessness of its currency explicit by writing out the number

1,000,000,000,000,000,000,000.

Seven years and one day ago, I wrote about names for extremely large numbers. I looked at the frequency of use for words like quintillion and sextillion, and they are rare, as you’d expect. More interesting is the fact that frequency drops off almost linearly on a log scale.

Frequency of large number names on log scale

Related posts

Taylor Series and the Argentine Peso

Posted on by John

A few days ago I wrote about now  hyperinflation changes everything. I’d like to follow up with another example of hyperinflation breaking implicit assumptions.

Something I was reading this week gave the approximation for present value

v = 1/(1 + i) ≈ 1 − i + i²

This implicitly assumes that the interest rate i is fairly small. The approximation comes from expanding 1/(1 + i) in a power series. The error in the truncated series is on the order of i³, which is negligible when, say, i = 0.1.

The approximation is absurd under hyperinflation when i > 100. Even for a high rate of inflation less than hyperinflation, the approximation is still bad.

When Javier Milei became president of Argentina in December 2023, the annual rate of inflation that year was 211%.

If you used the approximation above with i = 2.11, you would estimate that that the value of an Argentine Peso (ARS) would triple in value rather than being cut in third. You would predict deflation rather than inflation.

At the time of writing the annual inflation rate in Argentina is 39%. If you used the approximation above, you’d calculate the present value of 1 ARS a year from now to be 0.76 ARS when the actual value is 0.72 ARS. The approximation isn’t very accurate since it implicitly assumes an interest rate less than 39%, but even so it’s not too bad.

Analogs of binomial coefficients

Posted on by John

There are several numbers that are analogous to binomial coefficients and, at least in Donald Knuth’s notation, are written in a style analogous to binomial coefficients. And just as binomial coefficients can be arranged into Pascal’s triangle, these numbers can be arranged into similar triangles.

In Pascal’s triangle, each entry is the sum of the two above it. Specifically,

\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}

The q-binomial coefficients satisfy two similar identities.

\begin{align*} \binom{n}{k}_q &= q^k \binom{n-1}{k}_q + \binom{n-1}{k-1}_q \\ &= \binom{n-1}{k}_q + q^{n-k}\binom{n-1}{k-1}_q \end{align*}

Here are the analogous theorems for Stirling numbers of the first

\left[ \begin{matrix} n \\ k \end{matrix} \right] = (n-1) \left[ \begin{matrix} n-1 \\ k \end{matrix} \right] + \left[ \begin{matrix} n-1 \\ k-1 \end{matrix} \right]

and second

\left\{ \begin{matrix} n \\ k \end{matrix} \right\} = k \left\{ \begin{matrix} n-1 \\ k \end{matrix} \right\} + \left\{ \begin{matrix} n-1 \\ k-1 \end{matrix} \right\}

kinds.

And finally, here is the corresponding theorem for Eulerian numbers.

\left\langle \begin{matrix} n \\ k \end{matrix} \right\rangle = (k+1) \left\langle \begin{matrix} n-1 \\ k \end{matrix} \right\rangle + (n-k) \left\langle \begin{matrix} n-1 \\ k-1 \end{matrix} \right\rangle

 

Annuity and factorial notation

Posted on by John

Actuarial mathematics makes frequent use of a notation that as far as I know isn’t used anywhere else, and that is a bracket enclosing the northeast corner of a symbol.

\angln

This is used as subscript of another symbol, such as an a or an s, and there may be other decorations such more superscripts or subscripts.

\ddot{a}_{\angln i}

For typesetting in LaTeX, the bracket is the only part that’s not standard. If you can put a bracket around a symbol, you can make the bracketed symbol a subscript just as you’d make anything else a subscript. LaTeX package actuarialangle lets you do this.

The angle notation that actuaries use for annuity-related calculations is not used anywhere else that I know of, but a variation was once used for factorials back in the 1800s, putting a bracket around the southwest corner of a symbol rather than the northeast. You can see examples here, including one use by David Hilbert.

snippet of paper by David Hilbert

Related post: Floor, ceiling, bracket

Base58 versus Base85 encoding

Posted on by John

Base58 encoding and Base85 encoding are used to represent binary data in a human-friendly way. Base58 uses a smaller character set and so is more conservative. Base85 uses a larger character set and so is more efficient.

There is a gotcha in that “base” means something different in Base58 compared to Base85. More on that below.

Base58

Base58 encoding is primarily used as part of the Bitcoin system. It is part of the Base58Check protocol used for encoding addresses and keys.

Base58 encoding is essentially the same as mathematical base 58 encoding, with a specific character set. The symbols for the “digits” 0 through 57 are chosen to avoid typographically similar letters. We’ll give that character set in the examples below.

There is only one version of Base58 in common use as far as I know, unlike Base85.

Base85

Base85 is a more compact alternative to Base64 encoding. The former encodes 4 bytes in 5 characters while the latter requires 6 characters. Base85 is used inside the PDF format. It is also used in the patch encoding for git.

Base85 encoding is analogous to binary-coded decimal (BCD). In some early computer systems, integers would not be expressed in binary per se. Instead, each digit would be represented as by four bits. So to represent a number like 427, you’d express 4, 2, and 7 in binary: 0100 0010 0111. If you were to express 427 in binary you’d get 110101011.

Base85 breaks bits into 32-bit words, then expresses each word in base 85. So you might say it’s base 85-encoded 32-bit words by analogy to binary coded decimal.

There are variations on Base85 encoding that use different alphabets, and so two software packages that say they do Base85 encoding might produce different results.

Base85 is more efficient than Base58 in the sense that it represents data using fewer symbols. It is also more computationally efficient because each 32-bit word is encoded independently.

Examples

We give four examples below: Base58 and Base85 applied to four bytes of data and eight bytes of data. The data length matters for Base85.

Base58, four bytes

Let n = CAFEBABEhex = 3405691582ten. This is the “magic number” at the beginning of Java class files, a pun on “java” as a slang for coffee.

In base 58 this number would be

5:10:55:3:26:22

We can verify this as follows:

    >>> 5*58**5 + 10*58**4 + 55*58**3 + 3*58**2 + 26*58 + 22
    3405691582
    >>>  hex(_)
    '0xcafebabe'

The Base58 alphabet is

    123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

and so the Base58 encoding of 0xCAFEBABE would be the 5th, 10th, 55th, … elements of this alphabet (with zero-based index) which results in 6Bx4TP.

Note that the Base58 alphabet contains the digit 1 but not the letter l. It contains the lower case letter o but not the capital letter 0 or the digit 0.

Base85, four bytes

Now suppose we want to encode n using Base85. Now we would get

65:20:50:84:67

If we use the alphabet

    !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstu

then the “digits” above become b5Sud.

Note that the Base85 alphabet contains characters that could be confused, such as 0 (zero), O (capital letter), o (lower case letter). The characters were chosen to be printable ASCII characters, not necessarily visually distinct.

Base58, eight bytes

Now suppose n = CAFEBABECAFEBABEhex = 14627333968358193854ten.

We convert n to base 58 to get

33:55:17:43:49:44:3:47:49:44:26

which becomes axJkrm4prmT in the Base58 alphabet.

Base85, eight bytes

To encode CAFEBABECAFEBABEhex in Base85 we do not convert the number to base 85. Instead, we convert each 4-byte word to base 85. So we get two copies of CAFEBABEhex and so the encoding is b5Sudb5Sud.

If we were to wrongly convert n to base 85, we’d get

63:13:1:27:77:35:57:62:38:49

which becomes `."<nDZ_GR which is not the correct encoding.

Related posts

Hyperinflation changes everything

Posted on by John

Zimbabwe one hundred trillion dollar note

My two latest blog posts have been about compound interest. I gave examples of interest rates of 6% up to 18% per year.

Hyperinflation, with rates of inflation in excess of 50% per month, changes everything. Although many economists accept 50% per month as the threshold of hyperinflation, the world has seen worse. Zimbabwe, for example, faced 98% inflation per day. With hyperinflation lots of implicit assumptions and approximations break down.

One take away from the previous posts is that at moderate interest rates, the frequency of compounding doesn’t make that much difference. A nominal interest rate of 12%, compounded continuously, is effectively a 12.75% interest rate. Compound less than continuously, say monthly or daily, and the effective rate will be somewhere between 12% and 12.75%.

But now say interest is 50% per month. Simple interest would be 600% a year, but nobody would accept simple interest. Compounded every month, the effective interest rate would be 12975%. Compounded daily it would be 38433%. And compounded continuously it would be 40343%.

In the numerical post, I said that the difference between continuous interest and interest compounded n times per year was approximately r² / 2n. That works fine when r is say 0.12. When r = 10 it’s off by two orders of magnitude. The implicit assumption that r² < r breaks down when r > 1.

Hyperinflation causes unusual behavior, such as paying for a meal before you eat it rather than afterward, because by the end of the meal the price will be appreciably higher.

What I find hardest to understand about hyperinflation is that people continue to use hyperinflated currency far longer than I would imagine. Once you start using a clock rather than a calendar when doing interest calculations, I would think that people would abandon the inflated currency in favor of something harder, like gold or silver, or even cigarettes. And eventually people do, but “eventually” is further out than I would imagine. It’s absurd to haul paper money in a wheel barrow, and yet people do it.