Here’s kind of an unusual question: What is the density of integers that have an even number of prime factors with an exponent greater than 1? To define the density, you take the proportion up to an integer N then take the limit as N goes to infinity. It’s not obvious that the limit should […]

# Category: Math

## Trott’s constant

Trott’s constant is the unique number whose digits equal its continued fraction coefficients.

See OEIS sequence A039662.

More continued fraction posts

Best rational approximations to π

Continued fraction cryptography

Normal hazard continued fra…

## Using one RNG to sample another

Suppose you have two pseudorandom bit generators. They’re both fast, but not suitable for cryptographic use. How might you combine them into one generator that is suitable for cryptography? Coppersmith et al [1] had a simple but effective approach which they call the shrinking generator. The idea is to use one bit stream to sample […]

## Rock, paper, scissors, algebra

Aatish Bhatia posted something interesting on Twitter: if you define multiplication on Rock, Paper, Scissors to be the winner of a match, the result is commutative but not associative. Here’s a neat thing about the algebra of Rock, Paper, Scissors. If you define ‘multiplication’ as the game’s winner, then it’s commutative, i.e. P x R […]

## Sums of volumes of spheres

I ran across a video this afternoon that explains that the sum of volumes of all even-dimensional unit spheres equals eπ. Why is that? Define vol(n) to be the volume of the unit sphere in dimension n. Then and so the sum of the volumes of all even dimensional spheres is But what if you […]

## The AES S-box

The AES (Advanced Encryption Standard) algorithm takes in blocks of 128 or more bits [1] and applies a sequence of substitutions and permutations. The substitutions employ an “S-box”, named the Rijndael S-box after its designer, an invertible nonlinear transformation that works on 8 bits at a time. There are 256 = 16 × 16 possible […]

## Between now and quantum

The National Security Agency has stated clearly that they believe this is the time to start moving to quantum-resistant encryption. Even the most optimistic enthusiasts for quantum computing believe that practical quantum computers are years away, but so is the standardization of post-quantum encryption methods. The NSA has also made some suggestions for what to […]

## Strong primes

There are a couple different definitions of a strong prime. In number theory, a strong prime is one that is closer to the next prime than to the previous prime. For example, 11 is a strong prime because it is closer to 13 than to 7. In cryptography, a strong primes are roughly speaking primes […]

## Comparing Truncation to Differential Privacy

Traditional methods of data de-identification obscure data values. For example, you might truncate a date to just the year. Differential privacy obscures query values by injecting enough noise to keep from revealing information on an individual. Let’s compare two approaches for de-identifying a person’s age: truncation and differential privacy. Truncation First consider truncating birth date […]

## Golden ratio primes

The golden ratio is the larger root of the equation φ² – φ – 1 = 0. By analogy, golden ratio primes are prime numbers of the form p = φ² – φ – 1 where φ is an integer. When φ is a large power of 2, these prime numbers are useful in cryptography […]

## Goldilocks and the three multiplications

Mike Hamburg designed an elliptic curve he calls Ed448-Goldilocks. The prefix Ed refers to the fact that it’s an Edwards curve. The number 448 refers to the fact that the curve is over a prime field where the prime p has size 448 bits. But why Goldilocks? Golden primes and Goldilocks The prime in this […]

## Tricks for arithmetic modulo NIST primes

The US National Institute of Standards and Technology (NIST) originally recommended 15 elliptic curves for use in elliptic curve cryptography [1]. Ten of these are over a field of size 2n. The other five are over prime fields. The sizes of these fields are known as the NIST primes. The NIST curves over prime fields […]

## Elliptic curve P-384

The various elliptic curves used in ellitpic curve cryptography (ECC) have different properties, and we’ve looked at several of them before. For example, Curve25519 is implemented very efficiently, and the parameters were transparently chosen. Curve1174 is interesting because it’s an Edwards curve and has a special addition formula. This post looks at curve P-384. What’s […]

## Bessel function crossings

The previous looked at the angles that graphs make when they cross. For example, sin(x) and cos(x) always cross with the same angle. The same holds for sin(kx) and cos(kx) since the k simply rescales the x-axis. The post ended with wondering about functions analogous to sine and cosine, such as Bessel functions. This post […]

## Orthogonal graphs

Colin Wright posted a tweet yesterday that said that the plots of cosine and tangent are orthogonal. Here’s a plot so you can see for yourself. Jim Simons replied with a proof so short it fits in a tweet: The product of the derivatives is -sin(x)sec²(x) = -tan(x)/cos(x), which is -1 if cos(x)=tan(x). This made […]

## Area and volume of Menger sponge

The Menger sponge is the fractal you get by starting with a cube, dividing each face into a 3 by 3 grid (like a Rubik’s cube) and removing the middle square of each face and everything behind it. That’s M1, the Menger sponge at the 1st stage of its construction. The next stage repeats this […]

## A misunderstanding of complexity

Iterating simple rules can lead to complex behavior. Many examples of this are photogenic, and so they’re good for popular articles. It’s fun to look at fractals and such. I’ve written several articles like that here, such as the post that included the image below. But there’s something in popular articles on complexity that bothers […]

## Improving on the sieve of Eratosthenes

Ancient algorithm Eratosthenes had a good idea for finding all primes less than an upper bound N over 22 centuries ago. Make a list of the numbers 2 to N. Circle 2, then scratch out all the larger multiples of 2 up to N. Then move on to 3. Circle it, and scratch out all […]

## How category theory is applied

Instead of asking whether an area of mathematics can be applied, it’s more useful to as how it can be applied. Differential equations are directly and commonly applied. Ask yourself what laws govern the motion of some system, write down these laws as differential equations, then solve them. Statistical models are similarly direct: propose a […]

## Quantum leaps

A literal quantum leap is a discrete change, typically extremely small [1]. A metaphorical quantum leap is a sudden, large change. I can’t think of a good metaphor for a small but discrete change. I was reaching for such a metaphor recently and my first thought was “quantum leap,” though that would imply something much […]