John D. Cook

Given an integer n, suppose you want to compute n, the greatest integer less than or equal to the square root of n. One reason you may want to compute n is to know when you can stop trial division when factoring n. Similarly, n gives you a starting point for Fermat's factorization algorithm. With [...]The post Computing square root floor first appeared on John D. Cook.

This time last year I wrote about groups of order 2023 and now I'd like to do the same for 2024. There are three Abelian groups of order 2024, and they're not hard to find. We can factor 2024 = 8 * 11 * 23 and so the Abelian groups of order 2024 are of [...]The post Groups of order 2024 first appeared on John D. Cook.

Two of the first things you learn in cryptography are that simple substitution ciphers are very easy to break, and that security by obscurity is a bad idea. This post will revisit both of these ideas. Security depends on your threat model. If the threat you want to protect against is a human reading your [...]The post Weak encryption and surveillance first appeared on John D. Cook.

Yesterday I wrote about a way to memorize a random 256-bit encryption key. This isn't trivial, but it's doable using memory techniques. There's a much easier way to create a memorable encryption key: start with something memorable, then apply a hash function. Why not just do that? There are two conflicting criteria to satisfy: cryptographic [...]The post Randomize, then humanize first appeared on John D. Cook.

Here is an introduction to manifolds (PDF, 23 MB) unlike any I've seen before. These notes by Brian Beckman devote a substantial amount of time to thinking about the problem of describing a location on a manifold, including an unexpected diversion into What3Words. The notes are in the form of a Mathematica notebook. The link [...]The post An unusual introduction to manifolds first appeared on John D. Cook.

There are techniques that can enable anyone to memorize much more than may seem possible. This post will show how I generated and memorized a 256-bit encryption key this morning using the approach explained here. TANSTAAFL There ain't no such thing as a free lunch. This saying is abbreviated TANSTAAFL in Heinlein's novel The Moon [...]The post Example of memorizing a 256-bit private key first appeared on John D. Cook.

These were the most popular posts I wrote in 2023. Privacy and encryption First names and Bayes' theorem What is the point of a public key fingerprint? RSA encryption in practice Geometry A pentagon, hexagon, and decagon walk into a bar (source of the image above) Calculating the intersection of two circles Number theory Every [...]The post Top twelve posts of 2023 first appeared on John D. Cook.

John Conway's Doomsday" rule observes that that every year, the dates 4/4, 6/6, 8/8, 10/10, 12/12, 5/9, 9/5, 7/11, and 11/7 fall on the same day of the week. In 2024 all these dates fall on a Thursday. These dates are easy to memorize because they break down in double pairs of even digits-4/4, 6/6, [...]The post Doomsday 2024 first appeared on John D. Cook.

The last couple blog posts have been about Dixon elliptic functions, functions which are analogous in some ways to sine and cosine functions. Whereas sine and cosine satisfy a Pythagorean identity the Dixon functions sm and cm satisfy what you might call a Fermat identity alluding to Fermat's last theorem. The functions sm and cm [...]The post Addition theorems for Dixon functions first appeared on John D. Cook.

The Fermat curve of ordern is the set of points satisfying xn + yn = 1 for a positive integer n. Fermat's last theorem is equivalent to saying there are no non-trivial rational points on the Fermat curve of order n > 2. (The trivial points have x or y equal to 0.) Parameterization The [...]The post Fermat curve first appeared on John D. Cook.

The Dixon elliptic functions sm and cm are in some ways analogous to sine and cosine. However, whereas sine and cosine satisfy the Dixon functions satisfy The exponent 3 foreshadows the fact that these functions have a sort of three-fold symmetry. In particular, the function sm maps an equilateral triangle in the complex plane to [...]The post Conformal map between disk and equilateral triangle first appeared on John D. Cook.

As a student, I often made the mistake of thinking that if I knew a more powerful theorem, I didn't need to learn a less powerful theorem. The reason this is a mistake is that the more powerful theorem may be better by one obvious criterion but not be better by other less-obvious criteria. The [...]The post Integrals involving secants and tangents first appeared on John D. Cook.

Public key cryptography uses two keys: a private key and a public key. The nature of these keys depends on the encryption scheme, such as whether one is using RSA, ECC, or some other method, but you can think of a key as a long number. A key may be a short list of numbers, [...]The post What is the point of a public key fingerprint? first appeared on John D. Cook.

The diff utility compares files by lines, which is often what you'd like it to do. But sometimes you'd like more granularity. For example, supposed we want to compare two versions of Psalm 23. Here are the first three verses in the King James version: The Lord is my shepherd; I shall not want. He [...]The post Fine-grained file differences first appeared on John D. Cook.

I stumbled on the book Ed Mastery by Michael W. Lucas and couldn't tell immediately whether it was serious. In a sort of technical version of Poe's law, Lucas lays on the technical machismo pretty thick, but not thicker than some people do unironically. Bravado Here's a paragraph from early in the book. Many younger [...]The post The ed line editor: bravado, utility, and history first appeared on John D. Cook.

A few days ago I wrote about sufficient conditions for f(g(x)) to bound g(f(x)). This evening I stumbled on an analogous theorem. For real numbers and , cos( sin(x)) > sin( cos(x)) for all real x provided ^2 + ^2 < (/2)^2. Source: American Mathematical Monthly. February 2009. Solution to problem 11309, page 184. [...]The post sin(cos(x)) versus cos(sin(x)) first appeared on John D. Cook.

There is a conformal map between any two simply connected open proper subsets of the complex plane. This means, for example, there is a one-to-one analytic map from the interior of a square onto the interior of a a circle. Or from the interior of a triangle onto the interior of a pentagon. Or from [...]The post Rectangles to Rectangles first appeared on John D. Cook.

GnuPG ASCII armor is a way to encode binary data as text and decode the text back into binary. It could be used with any binary data, but most often it is used with cryptographic data: public keys, encrypted messages, etc. Secure communication over an insecure channel When people ask whether some medium supports encryption," [...]The post ASCII armor: send encrypted data in plain text first appeared on John D. Cook.

Perhaps you've heard that you should not reuse passwords but don't understand why. After all, you have a really good password, one that nobody would ever guess, so why not use it everywhere? Your password is not as good as you think First of all, people who think they have a really good password are [...]The post Why not reuse passwords? first appeared on John D. Cook.

Something that seems like an isolated trick may turn out to be much more important. This is the case with a change of variables discovered by Karl Weierstrass. Every calculus student learns a handful of standard techniques: u-substitutions, partial fractions, integration by parts, and trig substitutions. Then there is one more technique that is like [...]The post The world's sneakiest substitution first appeared on John D. Cook.

I stumbled upon a theorem today that I feel like I've needed in the past, though I can't remember any particular applications. I'm writing it up here as a note to my future self should the need reappear. The theorem gives sufficient conditions to conclude f(g(x)) g(f(x)) and uses this to prove, for example, [...]The post f(g(x)) versus g(f(x)) first appeared on John D. Cook.

Mathematica has data on stars and constellations. Here is Mathematica code to create a list of constellations, sorted by the declination (essentially latitude on the celestial sphere) of the brightest star in the constellation. constellations = EntityList["Constellation"] sorted = SortBy[constellations, -#["BrightStars"][[1]]["Declination"] &] We can print the name of each constellation with Map[#["Name"] &, sorted] This [...]The post Constellations in Mathematica first appeared on John D. Cook.

A blog carnival is a round up of recent blog posts. The Carnival of Mathematics is a long-running carnival of blog posts on mathematical topics. This is the 222nd edition of the carnival. Facts about 222 By longstanding tradition, the nth Carnival of Mathematics must begin with trivia about the number n, and so here [...]The post 222nd Carnival of Mathematics first appeared on John D. Cook.

Suppose you have an nth degree polynomial with complex coefficients p(z) = anzn + an-1zn-1 + ... + a0 and you want to find some circle that is guaranteed to contain all the zeros of p. Cauchy found such a circle in 1829. The zeros of p lie inside the circle |z| r where [...]The post Bounding complex roots by a positive root first appeared on John D. Cook.

I was reading a theorem giving conditions for a divergent series to have a convergent subseries and had a sort of flashback. I studied nonlinear PDEs in grad school, which amounted to applied functional analysis. We were constantly proving or using theorems about sequences having convergent subsequences, often subsequences that converged in a very weak [...]The post Convergent subsequence first appeared on John D. Cook.

Motivation Memorizing the periodic table has some practical value, especially if you're a chemist, but in any case it's an interesting exercise, easier to do than it may sound. And it's a case study for how you might memorize other things of more practical value to you personally. Major system pegs The Major system is [...]The post How to memorize the periodic table first appeared on John D. Cook.

The numbers in today's date-11, 28, and 23-make up the sides of a triangle. This doesn't always happen; the two smaller numbers have to add up to more than the larger number. We'll look at triangles with sides 11, 23, and 28 in the plane, on a sphere, and on a hypersphere. Most of the [...]The post Solving a triangle the size of Argentina first appeared on John D. Cook.

If you knew that you wanted to learn 10 spoken languages, it would probably be helpful to take a course in linguistics first. Or maybe to have a linguistics course after learning your first or second language. And if the languages are related, it would help to know something about the linguistics of that group [...]The post Unix linguistics first appeared on John D. Cook.

Richard Hamming [1] gives this nice example of an integral with a mild singularity: The integrand approaches - as x approaches 0 and yet the integral is finite. If we try into numerically evaluate this integral, we will either get inaccurate results or we will have to go to a lot of work. This post [...]The post Numerical integral with a singularity first appeared on John D. Cook.

When you stretch a coiled spring, the radius decreases slightly, so slightly that you can't see the difference unless you stretch the spring so much that you damage it. The math is essentially the same as in the previous post about wrapping Christmas lights around a tree trunk. If you have a coiled spring of [...]The post Radius of a stretched spring first appeared on John D. Cook.

Suppose you want to wrap Christmas lights around a tree trunk that we can approximate by a cylinder of radius r. You want to wrap lights around the tree in a helix, going up a distance h every time you go around the tree once. What length of lights do you need to make n [...]The post Wrapping Christmas lights around a tree trunk first appeared on John D. Cook.

In 2018, three researchers from the US Census Bureau published a paper entitled Understanding Database Reconstruction Attacks on Public Data." [1] The article showed that private data on many individuals could be reverse engineered from public data. As I wrote about a few days ago, census blocks are at the bottom of the US Census [...]The post Database reconstruction attacks first appeared on John D. Cook.

This post is a sort of footnote to the previous post, Estimating the number of groups of a given order. The following is taken from an answer to a question on Stack Exchange. In general there is no formulaf(n) for the number of groups of order up to isomorphism. However, if n is squarefree (no [...]The post Number of groups of squarefree order first appeared on John D. Cook.

John Conway et al [1] give the name gnu(n) to the number of groups of order n, where gnu" stands for group number. This function has been studied since the 19th century, but I don't know whether there has ever been a standard notation for it. Mathematica calls it FiniteGroupCount. It's also the first sequence [...]The post Estimating number of groups of a given order first appeared on John D. Cook.

The term nonlinear pendulum" is analogous to a retronym, a new name for an old thing to distinguish it from a new variation. For example, once upon a time a guitar was just a guitar. Now such a guitar is called an acoustic guitar to distinguish it from an electric guitar. Similarly, analog signal processing [...]The post Period of a nonlinear pendulum first appeared on John D. Cook.

A Kepler triangle is a right triangle whose sides are in geometric progression. That is, if the sides have length a < b < c, then b/a = c/b = k. All Kepler triangles are similar because the proportionality constant k can only take on one value. To see this, we first pick our units [...]The post Kepler triangle first appeared on John D. Cook.

Terence Tao has been experimenting with formal theorem proving using Lean and writing about his experience. Here's something Tao said on Mathstodon that I thought was interesting. It is remarkable how much decoupling" is achieved by the Lean+Blueprint combo. Contributors can work locally on proving a lemma, without necessarily fully understanding the global proof structure. [...]The post Decoupling formal theorem proving effort first appeared on John D. Cook.

Given a set of dots and dashes, how many ways can they be partitioned into a set of Morse code letters? There is at least one way, since you could take each dot to be an E and each dash to be a T. If you have a sequence ofn dots and dashes, there no [...]The post Partitioning dots and dashes first appeared on John D. Cook.

Let D be the open unit disk in the complex plane. The Schwarz lemma says that if f is an analytic function from D to D with f(0) = 0, then for allz in D. The lemma also says more, but this post will focus on just this portion of the theorem. The Schwarz-Pick theorem [...]The post Schwarz lemma, Schwarz-Pick theorem, and Poincare metric first appeared on John D. Cook.

A couple days ago Michael Nielsen posted an image of a one-page paper that gives an algorithm for generating factored random numbers, uniformly distributed from 1 to some designated N. The algorithm does not generate random numbers then factor them. It's more efficient than that, generating the factorization along with the final result. It does [...]The post Factored random numbers first appeared on John D. Cook.

The previous post discussed EXIF data embedded in a digital photo. DICOM files are analogous medical images. You can think of a DICOM image as a JPEG with medical metadata. Strictly speaking a DICOM file is a sort of database, and one of the fields in the database contains the pixels. The pixels are [...]The post DICOM image data first appeared on John D. Cook.

Is it possible to identify the people in the photo above? Maybe. Digital images potentially contain a large amount of metadata that could reveal the photographer's identify and location. There may also be a surprising number of clues in the photo itself. EXIF metadata The standard format for image metadata is EXIF, Exchangeable Image File [...]The post Personal information in digital photos first appeared on John D. Cook.

What can someone learn about you from your phone number? The answer depends on what other information someone has. Identifiers always depend on context. To a naked man in a tree [1] the phone number doesn't carry any information. But to someone with a list of names and phone numbers, some sort of reverse phone [...]The post What can you learn from a phone number? first appeared on John D. Cook.

Students seeing differential equations for the first time expect every equation to have a nice closed-form solution, because up to that point in their education nearly every problem they've seen has been contrived to have a nice closed-form solution. Once you resign yourself to the fact that a differential equation will rarely have a closed [...]The post Rational solution to Korteweg-De Vries equation first appeared on John D. Cook.

This summer I wrote about Ruzsa distance and Ruzsa entropy. That earlier post would make a good warmup for reading Terence Tao's latest post On a conjecture of Martin.The post Ruzsa distance and Ruzsa entropy warmup first appeared on John D. Cook.

The latest episode of Darknet Diaries interviews someone using the pseudonym Default. He says in the interview that he had nearly a thousand Bitcoins (about $36 M) in a wallet stored on an external hard drive that was seized by federal agents when they raided his home. Default went to prison for five years for [...]The post How to memorize a Bitcoin address first appeared on John D. Cook.

Some kinds US Census geographic areas nest into a tidy hierarchy, but others do not. Here's a brief overview of both. Hierarchical entities The orderly hierarchy is nation region division state county census tract block group census block. All cleanly nested. There are four regions: West, Midwest, Northeast, and South. Each region splits into two [...]The post US Census area hierarchy first appeared on John D. Cook.

I noticed the other day that an app on my phone assumed that a long number was a USPS tracking number. I wondered how it decided that and did a little research. I assumed there was some structure to the number, at least a check sum if not more than that. This turned out to [...]The post USPS tracking numbers first appeared on John D. Cook.

Differential privacy can be rigid and overly conservative in practice, and so finding ways to relax pure differential privacy while retaining its benefits is an active area of research. Two approaches to doing this are concentrated differential privacy [1] and Renyi differential privacy [3]. Concentrated differential privacy was used in reporting results from the 2020 [...]The post Zero-Concentrated Differential Privacy first appeared on John D. Cook.

Let's work our way up to differentially private stochastic gradient descent (DP-SGD) a little at a time. We'll first look at gradient descent, then stochastic gradient descent, then finally differentially private stochastic gradient descent. Gradient descent We'll start with gradient descent. Suppose you have a function of several variables f(x) where x is a vector. [...]The post Differentially private stochastic gradient descent first appeared on John D. Cook.