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