# Category: Number theory

## 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 […]

## 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 […]

## 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 […]

## Testing for primes less than a quintillion

The most common way to test whether a large number is prime is the Miller-Rabin test. If the test says a number is composite, it’s definitely composite. Otherwise the number is very likely, but not certain, to be prime. A pseudoprime is a composite number that slips past the Miller-Rabin test. (Actually, a strong pseudoprime. […]

## Regression, modular arithmetic, and PQC

Linear regression Suppose you have a linear regression with a couple predictors and no intercept term: β1×1 + β2×2 = y + ε where the x‘s are inputs, the β are fixed but unknown, y is the output, and ε is random error. Given n observations (x1, x2, y + ε), linear regression estimates the parameters β1 […]

## Naming elliptic curves for cryptography

There are an infinite number of elliptic curves, but a small number that are used in cryptography, and these special curves have names. Apparently there are no hard and fast rules for how the names are chosen, but there are patterns. The named elliptic curves are over a prime field, i.e. a finite field with […]

## Sum-product theorem for finite fields

A week ago I wrote about using some Python code to play with the sum-product theorem of Erdős and Szemerédi and its conjectured refinement. This morning I learned that the Erdős-Szemerédi theorem has been extended to finite fields. David Johnston left a comment saying that he and his colleagues used this extension to finite fields as […]

## Computing Legendre and Jacobi symbols

In a earlier post I introduce the Legendre symbol where a is a positive integer and p is prime. It is defined to be 0 if a is a multiple of p, 1 if a has a square root mod p, and -1 otherwise. The Jacobi symbol is a generalization of the Legendre symbol and uses the same notation. It […]

## Exploring the sum-product conjecture

Quanta Magazine posted an article yesterday about the sum-product problem of Paul Erdős and Endre Szemerédi. This problem starts with a finite set of real numbers A then considers the size of the sets A+A and A*A. That is, if we add every element of A to every other element of A, how many distinct sums are there? If we […]

## Big O tilde notation

There’s a variation on Landau’s big-O notation [1] that’s starting to become more common, one that puts a tilde on top of the O. At first it looks like a typo, a stray diacritic mark. What does that mean? In short, That is, big O tilde notation ignores logarithmic factors. For example, the FFT algorithm computes […]

## How fast can you multiply really big numbers?

How long does it take to multiply very large integers? Using the algorithm you learned in elementary school, it takes O(n²) operations to multiply two n digit numbers. But for large enough numbers it pays to carry out multiplication very differently, using FFTs. If you’re multiplying integers with tens of thousands of decimal digits, the […]

## Goldbach’s conjecture, Lagrange’s theorem, and 2019

The previous post showed how to find all groups whose order is a product of two primes using 2019 as an example. Here are a couple more observations along the same line, illustrating the Odd Goldbach Conjecture and Lagrange’s four square theorem with 2019. Odd Goldbach Conjecture Goldbach’s Conjecture says that every even number greater […]

## Check sums and error detection

The previous post looked at Crockford’s base 32 encoding, a minor variation on the way math conventionally represents base 32 numbers, with concessions for human use. By not using the letter O, for example, it avoids confusion with the digit 0. Crockford recommends the following check sum procedure, a simple error detection code: The check […]

## Base 32 and base 64 encoding

Math has a conventional way to represent numbers in bases larger than 10, and software development has a couple variations on this theme that are only incidentally mathematical. Math convention By convention, math books typically represent numbers in bases larger than 10 by using letters as new digit symbols following 9. For example, base 16 […]

## New prime record: 51st Mersenne prime discovered

A new prime record was announced yesterday. The largest known prime is now Written in hexadecimal the newly discovered prime is For decades the largest known prime has been a Mersenne prime because there’s an efficient test for checking whether a Mersenne number is prime. I explain the test here. There are now 51 known […]

## RSA with one shared prime

The RSA encryption setup begins by finding two large prime numbers. These numbers are kept secret, but their product is made public. We discuss below just how difficult it is to recover two large primes from knowing their product. Suppose two people share one prime. That is, one person chooses primes p and q and the other chooses p […]

## RSA with Pseudoprimes

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 […]

## RSA encryption exponents are mostly all the same

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 […]

## Mersenne prime trend

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 51 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 […]