Category Archives: number-theory

The Lucas primality test

We've been talking about the Miller-Rabin randomized primality test, which is one of the easiest to implement and most effective tests that, given a number, will either prove it to be composite or state that it is most likely prime. As good as it is for practical applications, the Miller-Rabin test leaves something to be […]

Effectiveness of the Miller-Rabin primality test

Last time, I explained the Miller-Rabin probabilistic primality test. Let's recall it: Theorem. Let $p$ be an odd prime and write $p-1 = 2^kq$ where $q$ is an odd number. If $a$ is relatively prime to $p$ then at least one of the following statements is true: $a^q\equiv 1\pmod{p}$, or One of $a^q,a^{2q},a^{4q},\dots,a^{2^{k-1}q}$ is congruent […]

Miller-Rabin Primality Test

Fermat's little theorem states that for a prime number $p$, any $a\in \Z/p^\times$ satisfies $a^{p-1} = 1$. If $p$ is not prime, this may not necessarily be true. For example: $$2^{402} = 376 \in \Z/403^\times.$$ Therefore, we can conclude that 403 is not a prime number. In fact, $403 = 13\cdot 31$ Fermat's little theorem […]

Symmetric+RSA vs. RSA and Davida's Attack

Alice wants her friends to send her stuff only she can read. RSA public-key encryption allows her to do that: she chooses huge primes $p$ and $q$ and releases $N = pq$ along with an encryption exponent $e$ such that ${\rm gcd}(e,(p-1)(q-1)) = 1$. If Bob wants to send Alice a message $m$, he sends […]

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

On normal numbers and e

A real number is simply normal in base $b$ if the frequency of each base $b$ digit in the first $n$ digits tends to a limit as $n$ goes to infinity, and each of these limits is the same. In other words, a real number is simply normal in base $b$ if each digit appears […]

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

Carmichael numbers

Since the days of antiquity, we've always been looking for ways to determine whether a natural number is prime. Trial division up to the square root of a number quickly becomes tedious, thought it is worth noting that even on my fairly old laptop a slightly optimised trial-division algorithm will list all the primes under […]