John D. Cook

Kevin Kelly is one of the most optimistic people writing about technology, but there’s a nuance to his optimism that isn’t widely appreciated. Kelly sees technological progress as steady and inevitable, but not monotone. He has often said that new technologies create almost as many problems as they solve. Maybe it’s 10 steps forward and […]

RSA setup Recall the setup for RSA encryption given in the previous post. Select two very large prime numbers p and q. Compute n = pq and φ(n) = (p – 1)(q – 1). Choose an encryption key e relatively prime to φ(n). Calculate the decryption key d such that ed = 1 (mod φ(n)). Publish e and n, and keep d, p, and q secret. φ is Euler’s totient function, defined here. There’s a complication in the first […]

Imagine this conversation. “Could you tell me your social security number?” “Absolutely not! That’s private.” “OK, how about just the last four digits?” “Oh, OK. That’s fine.” When I was in college, professors would post grades by the last four digits of student social security numbers. Now that seems incredibly naive, but no one objected […]

The big idea of public key cryptography is that it lets you publish an encryption key e without compromising your decryption key d. A somewhat surprising detail of RSA public key cryptography is that in practice e is nearly always the same number, specifically e = 65537. We will review RSA, explain how this default e was chosen, and discuss why […]

FAS posted an article yesterday explaining how blurring military installations out of satellite photos points draws attention to them, showing exactly where they are and how big they are. The Russian mapping service Yandex Maps blurred out sensitive locations in Israel and Turkey. As the article says, this is an example of the Streisand effect, […]

I recently got a review copy of Scientific Computing: A Historical Perspective by Bertil Gustafsson. I thought that thumbing through the book might give me ideas for new topics to blog about. It still may, but mostly it made me think of numerical methods I’ve already blogged about. In historical order, or at least in the […]

As mentioned in the previous post, Latanya Sweeney estimated that 87% of Americans can be identified by the combination of zip code, sex, and birth date. We’ll do a quick-and-dirty estimate and a simulation to show that this result is plausible. There’s no point being too realistic with a simulation because the actual data that […]

In 1997 Latanya Sweeney dramatically demonstrated that supposedly anonymized data was not anonymous. The state of Massachusetts had released data on 135,000 state employees and their families with obvious identifiers removed. However, the data contained zip code, birth date, and sex for each individual. Sweeney was able to cross reference this data with publicly available […]

How do you evaluate the sine of a large number in floating point arithmetic? What does the result even mean? Sine of a trillion Let’s start by finding the sine of a trillion (1012) using floating point arithmetic. There are a couple ways to think about this. The floating point number t = 1.0e12 can only […]

I just discovered the web site Six Degrees of Wikipedia. It lets you enter two topics and it will show you how few hops it can take to get from one to the other. Since the mathematical equivalent of Six Degrees of Kevin Bacon is Six degrees of Paul Erdős, I tried looking for the […]

Mersenne primes have the form 2p -1 where p is a prime. The graph below plots the trend in the size of these numbers based on the 50 Mersenne primes currently known. The vertical axis plots the exponents p, which are essentially the logs base 2 of the Mersenne primes. The scale is logarithmic, so […]

This post will look at the triangle behind North Carolina’s Research Triangle using Mathematica’s geographic functions. Spherical triangles A spherical triangle is a triangle drawn on the surface of a sphere. It has three vertices, given by points on the sphere, and three sides. The sides of the triangle are portions of great circles running […]

The image below is a static screen shot of an interactive visualization of the world’s biggest data breaches. The site lets you filter the data by industry and type of breach. See the site for credits and the raw data.

There’s an ancient tradition of construction workers putting a Christmas tree on top of a building when it reaches its full height. I happened to drive by a recently topped out building this morning.

Here’s something that comes up occasionally, a case where I have to tell someone “It doesn’t work that way.” I’ll write it up here so next time I can just send them a link instead of retyping my explanation. Rules for exponents The rules for manipulating expressions with real numbers carry over to complex numbers […]

Sam Walters posted something interesting on Twitter yesterday I hadn’t seem before: The sines of the positive integers have just the right balance of pluses and minuses to keep their sum in a fixed interval. (Not hard to show.) #math pic.twitter.com/RxeoWg6bhn — Sam Walters ☕️ (@SamuelGWalters) November 29, 2018 If for some reason your browser […]

I ran into The Google Cemetery the other day, a site that lists Google products that have come and gone. Google receives a lot of criticism when they discontinue a product, which is odd for a couple reasons. First, the products are free, so no one is entitled to them. Second, it’s great for a […]

Erlingsson et al give a poetic description of privacy-preserving analysis in their RAPPOR paper [1]. They say that the goal is to … allow the forest of client data to be studied, without permitting the possibility of looking at individual trees. Related posts What is differential privacy? Data privacy consulting [1] Úlfar Erlingsson, Vasyl Pihur, and […]

The nth Mersenne number is Mn = 2n – 1. A Mersenne prime is a Mersenne number which is also prime. So far 50 have been found [1]. A necessary condition for Mn to be prime is that n is prime, so searches for Mersenne numbers only test prime values of n. It’s not sufficient for n to be prime […]

Fermat numbers have the form Fermat numbers are prime if n = 0, 1, 2, 3, or 4. Nobody has confirmed that any other Fermat numbers are prime. Maybe there are only five Fermat primes and we’ve found all of them. But there might be infinitely many Fermat primes. Nobody knows. There’s a specialized test for […]

We all live on an oblate spheroid [1], so it could be handy to know a little about oblate spheroids. Eccentricity Conventional notation uses a for the equatorial radius and c for the polar radius. Oblate means a > c. The eccentricity e is defined by For a perfect sphere, a = c and so e = 0. The eccentricity for earth is […]

Pete White contacted me in response to a blog post I wrote enumerating musical scales. He has written a book on the subject, with audio, that he is giving away. He asked if I would host the content, and I am hosting it here. Here are a couple screen shots from the book to give […]

To first approximation, Earth is a sphere. But it bulges at the equator, and to second approximation, Earth is an oblate spheroid. Earth is not exactly an oblate spheroid either, but the error in the oblate spheroid model is about 100x smaller than the error in the spherical model. Finding the distance between two points […]

In my previous post I illustrated the Levenshtein edit distance by comparing the opening paragraphs of Finnegans Wake by James Joyce and a parody by Adam Roberts. In this post I’ll show how to align two sequences using the sequence alignment algorithms of Needleman-Wunsch and Hirschberg. These algorithms can be used to compare any sequences, though they […]

I ran into a delightfully strange blog post today called Finnegans Ewok that edits the first few paragraphs of Finnegans Wake to make it into something like Return of the Jedi. The author, Adam Roberts, said via Twitter “What I found interesting here was how little I had to change Joyce’s original text. Tweak a couple […]

Differential privacy, specifically ε-differential privacy, gives strong privacy guarantees, but it can be overly cautious by focusing on worst-case scenarios. The generalization (ε, δ)-differential privacy was introduced to make ε-differential privacy more flexible. Rényi differential privacy (RDP) is a new generalization of ε-differential privacy by Ilya Mironov that is comparable to the (ε, δ) version but has several […]

The most common way of measuring information is Shannon entropy, but there are others. Rényi entropy, developed by Hungarian mathematician Alfréd Rényi, generalizes Shannon entropy and includes other entropy measures as special cases. Rényi entropy of order α If a discrete random variable X has n possible values, where the ith outcome has probability pi, then the Rényi entropy […]

Curry-Howard-Lambek is a set of correspondences between logic, programming, and category theory. You may have heard of the slogan proofs-as-programs or propositions-as-types. These refer to the Curry-Howard correspondence between mathematical proofs and programs. Lambek’s name is appended to the Curry-Howard correspondence to represent connections to category theory. The term Curry-Howard isomorphism is often used but is an overstatement. Logic […]

Scott Hanselman interviewed attorney Gary Nissenbaum in show #647 of Hanselminutes. The title was “How GDPR is effecting the American Legal System.” Can Europe pass laws constraining American citizens? Didn’t we settle that question in 1776, or at least by 1783? And yet it is inevitable that European law effects Americans. And in fact Nissembaum […]

Let p be a prime. If the repeating decimal for the fraction a/p has even period, the the second half of the decimals are the 9’s complement of the first half. This is known as Midy’s theorem. For a small example, take 1/7 = 0.142857142857… and notice that 142 + 857 = 999. That is, 8, 5, […]

The General Conference on Weights and Measures voted today to redefine the kilogram. The official definition no longer refers to the mass of the International Prototype of the Kilogram (IPK) stored at the BIPM (Bureau International des Poids et Measures) in France. The Coulomb, kelvin, and mole have also been redefined. The vote took place today, 2018-11-16, and […]

Deep learning has spurred interest in novel floating point formats. Algorithms often don’t need as much precision as standard IEEE-754 doubles or even single precision floats. Lower precision makes it possible to hold more numbers in memory, reducing the time spent swapping numbers in and out of memory. Also, low-precision circuits are far less complex. […]

One of my most popular posts on Twitter was an implicit criticism of the cliché “work smarter, not harder.” Productivity tip: Work hard. — John D. Cook (@JohnDCook) October 8, 2015 I agree with the idea that you can often be more productive by stepping back and thinking about what you’re doing. I’ve written before, […]

Last week Bujanda et al published a paper [1] that gives new expansions for the confluent hypergeometric function. I’ll back up explain what that means before saying more about the new paper. Hypergeometric functions Hypergeometric functions are something of a “grand unified theory” of special functions. Many functions that come up in application are special […]

How does big data impact privacy? Which is a bigger risk to your privacy, being part of a little database or a big database? Rows vs Columns People commonly speak of big data in terms of volume—the “four v’s” of big data being volume, variety, velocity, and veracity—but what we’re concerned with here might better be […]

The idea of proof of work (PoW) was first explained in a paper Cynthia Dwork and Moni Naor [1], though the term “proof of work” came later [2]. It was first proposed as a way to deter spam, but it’s better known these days through its association with cryptocurrency. If it cost more to send […]

The Hagia Sophia (Greek for “Holy Wisdom”) was a Greek Orthodox cathedral from 537 to 1453. When the Ottoman Empire conquered Constantinople the church was converted into a mosque. Then in 1935 it was converted into a museum. No musical performances are allowed in the Hagia Sophia. However, researchers from Stanford have modeled the acoustics […]

There are several things in math and statistics named gamma. Three examples are the gamma function the gamma constant the gamma distribution This post will show how these are related. We’ll also look at the incomplete gamma function which connects with all the above. The gamma function The gamma function is the most important function […]

In 1999, Harvard law professor Lawrence Lessig stated that software is a kind of law. The algorithms of tech giants have an influence comparable to, and maybe in some ways greater than, statutory law. The code is law. … Activists concerned with defending liberty, privacy or access must watch the code coming from the Valley—call […]

Differential privacy is a strong form of privacy protection with a solid mathematical definition. Roughly speaking, a query is differentially private if it makes little difference whether your information is included or not. This intuitive idea can be made precise as follows. Queries and algorithms First of a differential privacy is something that applies to queries, […]

I stopped posting to the @FormalFact Twitter account last July, but I didn’t deactivate the account. Now I’m going to restart it. Unlike my other Twitter accounts, I don’t plan to have a regular posting schedule. I may not post often. We’ll see how it goes. I’ve changed the account name from @FormalFact to @LogicPractice. The […]

Every rational number can be expanded into a continued fraction with positive integer coefficients. And the process can be reversed: given a sequence of positive integers, you can make them the coefficients in a continued fraction and reduce it to a simple fraction. In 1954, Arthur Porges published a one-page article pointing out that continued fractions […]

There’s an old saying that if you want to hide a tree, put it in a forest. An analogous principle in privacy is that a record preserves privacy if it’s like a lot of other records. k-anonymity The idea of k-anonymity is that every database record appears at least k times when you restrict your attention to […]

Since integration is the inverse of differentiation, you can think of integration as “dividing” by d. J. P. Ballantine [1] shows that you can formally divide by d and get the correct integral. For example, he arrives at using long division! [1] J. P. Ballantine. Integration by Long Division. The American Mathematical Monthly, Vol. 58, […]

A few weeks ago I wrote about how there are many ways to summarize the operating characteristics of a test. The most basic terms are accuracy, precision, and recall, but there are many others. Nobody uses all of them. Each application area has their own jargon. Biometric security has its own lingo, and it doesn’t […]

In the previous post, I mentioned that modal logic has a lot of interpretations and a lot of axiom systems. It can also have a lot of operators. This post will look at Security Logic, a modal logic for security applications based on a seminal paper by Glasgow et al [1]. It illustrates how modal and […]

Modal logic extends propositional logic with two new operators, □ (“box”) and ◇ (“diamond”). There are many interpretations of these two symbols, the most common being necessity and possibility respectively. That is, □p means the proposition p is necessary, and ◇p means that p is possible. Another interpretation is using the symbols to represent things a person knows to […]

Many encryption algorithms rely on the difficulty of factoring a large number n. If you want to make n hard to factor, you want it to have only two factors. Otherwise, the more factors n has, the smaller the smallest factor must be. So if you want n to be the product of two large primes, p and q, you want […]

“There is no point in being precise when you don’t know what you’re talking about.” — John Tukey It’s a familiar trope in science fiction that the smartest character will answer questions with excess precision. On Star Trek, Scottie might give a number to one significant figure and Spock will correct him giving the same […]

The idea of format-preserving encryption is to encrypt data while keeping its form, a sort of encryption in kind. An encrypted credit card number would look like a credit card number, a string of text would be replaced with a string of text, etc. Format preserving encryption (FPE) is useful in creating a test or demo […]