Author: John

Monads and generalized elements

Paolo Perrone gives a nice, succinct motivation for monads in the introduction to his article on probability and monads. … a monad is like a consistent way of extending spaces to include generalized elements of a specific kind. He develops this idea briefly, and links to his dissertation where he gives a longer exposition (pages […]

Mixing error-correcting codes and cryptography

Secret codes and error-correcting codes have nothing to do with each other. Except when they do! Error-correcting codes Error correcting code make digital communication possible. Without some way to detect and correct errors, the corruption of a single bit could wreak havoc. A simple example of an error-detection code is check sums. A more sophisticated […]

US Army applying new areas of math

Many times on this blog I’ve argued that the difference between pure and applied math is motivation. As my graduate advisor used to say, “Applied mathematics is not a subject classification. It’s an attitude.” Traditionally there was general agreement regarding what is pure math and what is applied. Number theory and topology, for example, are […]

Riffing on mistakes

I mentioned on Twitter yesterday that one way to relieve the boredom of grading math papers is to explore mistakes. If a statement is wrong, what would it take to make it right? Is it approximately correct? Is there some different context where it is correct? Several people said they’d like to see examples, so […]

A genius can admit finding things difficult

Karen Uhlenbeck has just received the Abel Prize. Many say that the Fields Medal is the analog of the Nobel Prize for mathematics, but others say that the Abel Prize is a better analog. The Abel prize is a recognition of achievement over a career whereas the Fields Medal is only awarded for work done […]

Thermocouple polynomials and other sundries

I was looking up something on the NIST (National Institute of Standards and Technology) web site the other day and ran across thermocouple polynomials. I wondered what that could be, assuming “thermocouple” was a metaphor for some algebraic property. No, it refers to physical thermocouples. The polynomials are functions for computing voltage as a function […]

Digital signatures with oil and vinegar

“Unbalanced oil and vinegar” is a colorful name for a cryptographic signature method. This post will give a high-level description of the method and explain where the name comes from. The RSA encryption algorithm depends on the fact that computers can easily multiply enormous numbers, but they cannot efficiently factor the product of two enormous […]

Counting irreducible polynomials over finite fields

You can construct a finite field of order pn for any prime p and positive integer n. The elements are polynomials modulo an irreducible polynomial of degree n, with coefficients in the integers mod p. The choice of irreducible polynomial matters, though the fields you get from any two choices will be isomorphic. For example, […]

Scaling up differential privacy: lessons from the US Census

The paper Issues Encountered Deploying Differential Privacy describes some of the difficulties the US Census Bureau has run into while deploying differential privacy for the 2020 census. It’s not surprising that they would have difficulties. It’s surprising that they would even consider applying differential privacy on such an enormous scale. If your data project is […]

Average distance between planets

What is the closest planet to Earth? The planet whose orbit is closest to the orbit of Earth is clearly Venus. But what planet is closest? That changes over time. If Venus is between the Earth and the sun, Venus is the closest planet to Earth. But if Mercury is between the Earth and the […]

All elliptic curves over fields of order 2 and 3

Introductions to elliptic curves often start by saying that elliptic curves have the form y² = x³ + ax + b. where 4a³ + 27b² ≠ 0. Then later they say “except over fields of characteristic 2 or 3.” What does characteristic 2 or 3 mean? The order of a finite field is the number of […]

US Census Bureau embraces differential privacy

The US Census Bureau is convinced that traditional methods of statistical disclosure limitation have not done enough to protect privacy. These methods may have been adequate in the past, but it no longer makes sense to implicitly assume that those who would like to violate privacy have limited resources or limited motivation. The Bureau has […]

Efficient modular arithmetic technique for Curve25519

Daniel Bernstein’s Curve25519 is the elliptic curve y² = x³ + 486662x² + x over the prime field with order p = 2255 – 19. The curve is a popular choice in elliptic curve cryptography because its design choices are transparently justified [1] and because cryptography over the curve can be implemented very efficiently. This […]

Why isn’t CPU time more valuable?

Here’s something I find puzzling: why isn’t CPU time more valuable? I first thought about this when I was working for MD Anderson Cancer Center, maybe around 2002. Our research in adaptive clinical trial methods required bursts of CPU time. We might need hundreds of hours of CPU time for a simulation, then nothing while […]

Chaos + Chaos = Order

If you take these chaotic-looking values for your x-coordinates

and these chaotic-looking values for your y coordinates

you get this image that looks more ordered.

The image above is today’s exponential sum.

An attack on RSA with exponent 3

As I noted in this post, RSA encryption is often carried out reusing exponents. Sometimes the exponent is exponent 3, which is subject to an attack we’ll describe below [1]. (The most common exponent is 65537.) Suppose the same message m is sent to three recipients and all three use exponent e = 3. Each […]

Public key encryption based on squares and non squares

The RSA encryption algorithm depends indirectly on the assumption that factoring the product of large primes is hard. The algorithm presented here, invented by Shafi Goldwasser and Silvio Micali, depends on the same assumption but in a different way. The Goldwasser-Micali algorithm is more direct than RSA, thought it is also less efficient. One thing […]

An infinite product challenge

Gil Kalai wrote a blog post yesterday entitled “Test Your Intuition (or knowledge, or programming skills) 36.” The challenge is to evaluate the infinite product I imagine there’s an elegant analytical solution, but since the title suggested that programming might suffice, I decided to try a little Python. I used primerange from SymPy to generate […]

Base85 encoding

I’ve written about Base32 and Base64 encoding, and the less common Base58 encoding. For completeness I wanted to mention Base85 encoding, also known as Ascii85. Like Base64, the goal of Base85 encoding is to encode binary data printable ASCII characters. But it uses a larger set of characters, and so it can be a little […]

Base 58 encoding and Bitcoin addresses

A few weeks ago I wrote about base32 and base64 encoding. I’ll review these quickly then discuss base58 and its use in Bitcoin. Base32 and base64 All three methods have the goal of compactly representing large numbers while maintaining readability. Douglas Crockford’s base32 encoding is the most conservative: it’s case-insensitive and it does not use […]