Category Archives: number-theory

The Discrete Log, Part 2: Shanks' Algorithm

In a group $G$, the discrete logarithm problem is to solve for $x$ in the equation $g^x =h$ where $g,h\in G$. In Part 1, we saw that solving the discrete log problem for finite fields would imply that we could solve the Diffie-Hellman problem and crack the ElGamal encryption scheme. Obviously, the main question at […]

The Discrete Logarithm, Part 1

Given a group $G$, and an element $g\in G$ (the "base"), the discrete logarithm $\log_g(h)$ of an $h\in G$ is an element $x\in G$ such that $g^x = h$ if it exists. Its name "discrete logarithm" essentially means that we are only allowed to use integer powers in the group, rather than extending the definition […]

A partition identity

There is a cool way to express 1 as a sum of unit fractions using partitions of a fixed positive integer. What do we mean by partition? If $n$ is such an integer then a partition is just a sum $e_1d_1 + \cdots + e_kd_k = n$ where $d_i$ are positive integers. For example, 7 […]

Some graphs about primes

Lately I've been thinking about primes, and I've plotted a few graphs to illustrate some beautiful ideas involving primes. Even though you might not always associate with primes, they are always haunting quietly in the background. Abundance of primes in an arithmetic progression Let's start out with the oddest prime of all: 2. Get it? […]

Booker's Extension of the Selberg Class

Briefly, the Selberg class is a set of functions $F:\C\to\C$ such that $f(s)$ can be written as a Dirichlet series for $\Re(s) > 1$ and that satisfies a form of analytic continuation, a functional equation, a Ramanujan hypothesis bound on coefficients of the Dirichlet series, and an Euler product formula. Andrew Booker in [1] has […]