Number theory

Number theory is the study of integers and the relations between them. Carl Friedrich Gauss (1777 − 1855) allegedly said that mathematics is the queen of the sciences and that number theory is the queen of mathematics. What he meant by this is that mathematics, unlike the empirical sciences, studies regularities which are independent from the universe that we live in. Not having to deal with the messiness of the real world makes mathematics the purest of all sciences. Similarly, he must have considered number theory to be the most elegant and the purest branch of mathematics, given its beauty and that it was studied for centuries for its own sake. Or as Leonard Eugene Dickson (1874 − 1954) put it: “Thank God that number theory is unsullied by any application”. This changed with the advent of modern cryptography and coding theory in the second half of the 20th century. Unlike the mathematicians who discovered most of what I cover in this article, we’re studying number theory only for its applications in these two fields, which will be the topics of the next two articles.

The goal of this article is to understand how we can construct linear one-way functions using finite groups which have a certain property. There are two families of finite groups which are widely used in modern cryptography: multiplicative groups and elliptic curves. The former are based on modular arithmetic, the latter on finite fields. Prime numbers play a crucial role in both. We’ll study these topics in a somewhat peculiar order and also visit additive groups and commutative rings on our journey:

Since it’s easy to get lost in theorems and proofs, I start this article with introducing and motivating the concept of linear one-way functions so that we never lose sight of our goal. Afterwards, I cover finite groups in the abstract in order to establish the terminology that we will use for the rest of the article. Establishing such a mental framework first also helps us to process our observations later on. Additionally, proving properties in the abstract saves us a lot of work when looking at multiple examples. If you read about these topics for the first time, feel free to jump ahead and play with concrete examples before understanding the theory behind them. If you really want to grasp the math behind modern cryptography, you likely have to read this article more than once anyway. The reason for covering modular arithmetic and multiplicative groups before prime numbers is to get as far as possible before the math gets more challenging and to understand why prime numbers are so special. After learning about elliptic curves, I cover the best known algorithms for breaking our linear one-way functions in a bonus chapter, before concluding the article with formal proofs of basic group properties as an appendix.

There exist already plenty of textbooks and blog posts on number theory (see below for some recommendations), so I wasn’t sure whether it’s worth adding my own. Since future articles will require a thorough understanding of number theory and my ambition is to explain things from first principles, I proceeded anyway. Looking at the result, here’s what sets this article apart:

• Focus: Number theory is a big field with many advanced concepts. This article focuses on the aspects which are relevant for modern cryptography and coding theory. As you’ll see, almost all theorems mentioned in this article are being used later on.
• Notation: As we’ll see, two notations are used in group theory, and I haven’t found any other source which consistently provides both. Not having to translate between the two yourself reduces your cognitive load.
• Intuition: I went to great lengths to complement formal proofs with more intuitive explanations. While formal rigor is important, nothing beats an intuitive understanding of a theorem or an algorithm.
• Completeness: Apart from the chapter on elliptic curves, I took no shortcuts when explaining why things are the way they are. Therefore, this article contains the complete proofs of almost all covered theorems, including Carmichael’s totient function, the Monier-Rabin bound, square roots modulo composite numbers, and the expected running time of Pollard’s rho algorithm, which I haven’t found online outside of PDFs. While you might not be interested in such advanced proofs for now, this article is designed to serve as a work of reference for your whole journey into modern cryptography.
• Interactivity: Depending on how you count them, this article contains up to 40 interactive tools, which I also published on a separate page. Many tools, such as the repetition tables, visualize important group properties. Many other tools show how important algorithms work, such as the extended Euclidean algorithm, the Miller-Rabin primality test, and the Tonelli-Shanks algorithm. I also implemented the main algorithms to solve the discrete-logarithm problem, such as Pollard’s rho algorithm, the Pohlig-Hellman algorithm, and the index-calculus algorithm. Besides being fun to play with, these tools allow you to check your own hypotheses, which makes mathematics an empirical science after all. 🙂

It should be no surprise that an article about math contains a lot of math. If you’re afraid of math, then see this article as a free exposure-therapy session. On a more serious note: Number theory is quite different from the math you endured during high school. Number theory is mostly about understanding why some properties follow from others. You won’t have to calculate anything yourself; this is what computers are for. At times, the notation can seem daunting, but this is actually a problem of language and communication, not math. The situation isn’t made easier by the fact that different notations are used to talk about the same things. While I tried to keep everything as unconfusing as possible, this is an aspect that I couldn’t change.

There is a big difference between understanding how something works and understanding why something works. In mathematics, answers to why questions are called proofs. Proofs explain why a statement is true by showing how the statement can be deduced from already proven statements (called theorems) and statements which are simply assumed to be true (called axioms). If you want to understand only how modern cryptography works, you can skip this whole article and read just the next one. If you want to understand also why modern cryptography works, there is no way around proofs, even if you find them overly formal and tedious. But of course, you can always ignore answers to questions you would not have asked.

The two most important sources when writing this article were A Computational Introduction to Number Theory and Algebra by Victor Shoup and the Handbook of Applied Cryptography by Alfred Menezes, Paul van Oorschot, and Scott Vanstone (1947 − 2014). Consult the former for mathematical proofs and the latter for algorithmic aspects. Other useful sources are wikis for proofs, such as ProofWiki and Groupprops, and question-and-answer websites, such as Stack Exchange and Quora.

As we saw in a previous article, cryptographic hash functions work on inputs of arbitrary size and have to fulfill additional requirements, namely second-preimage resistance and collision resistance. We don’t care about these properties here because we will limit our linear one-way functions to a finite set of inputs and construct them in such a way that unequal inputs are mapped to unequal outputs. Depending on whether you limit the set of inputs or not, second preimages either don’t exist or are trivial to find. On the other hand, cryptographic hash functions are typically not linear (as long as we ignore provably secure hash functions, which are of limited practical use).

Computational complexity theory classifies problems according to how many steps are needed to solve them. Determining the precise number of steps required to solve an instance of a problem is of little interest, though. What computer scientists care about is how the required effort depends on the size of the input: If you double the input, does the number of steps that it takes to find a solution grow polynomially, such as quadrupling, or exponentially? Problems whose computational complexity grows exponentially with the input size become intractable if you make the input large enough. One-way functions can exist only if there are problems which cannot be solved in polynomial time, but solutions to which can be verified in polynomial time. It is widely believed that such problems exist, but we still lack a proof for this. This conjecture, which is known as P ≠ NP, is the most important open question in computer science. Examples of problems for which no polynomial-time algorithms are known but whose solution can be verified in polynomial time are integer factorization and the discrete-logarithm problem (DLP).

Algebra is the study of how to manipulate equations with symbols, and abstract algebra is the study of algebraic structures, which consist of a set and certain operations on the elements of the set. The goal of abstract algebra is to understand the properties of such structures at the highest level of abstraction so that these properties are applicable to any structure which satisfies the same requirements. Each algebraic structure has its own set of requirements, which are called axioms. Axioms are the premises from which conclusions are derived. The next chapter is about finite groups, but we’ll encounter other algebraic structures later on, namely commutative rings and finite fields.

The hours of an analog clock form a finite group. Its set consists of the elements 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12. In order to make things easier mathematically, we relabel 12 as 0. The operation is addition, where we wrap around to 0 after reaching 11:

As we’ll discuss later, the wrapping around corresponds to the modulo operation. Clearly, this group is closed: No matter how much time passes, the hour hand never leaves the clock. Associativity is given by the linearity of time and addition: Waiting for B hours and then for C hours is the same as waiting for B + C hours. 0 is the identity element: A + 0 = 0 + A = A. And finally, every element has an inverse: the number of hours you have to wait until it’s noon or midnight again. For example, 2 + 10 = 0.

In the case of an analog clock, we wrap around to \(0\) when reaching \(12\). I write \(A =_{12} B\) to denote that \(A = B\) up to a multiple of \(12\). Repeating the element \(5\), we have \(2 \cdot 5 =_{12} 5 + 5 =_{12} 10\), followed by \(3 \cdot 5 =_{12} 5 + 5 + 5 =_{12} 10 + 5 =_{12} 3\), and so on:

Using the above definitions, we have that \(0 \cdot 5 =_{12} 0\) and \((-n)5 =_{12} n(-5)\), where \(-5 =_{12} 7\) because \(5 + 7 =_{12} 0\). Therefore:

The above recursive algorithm can easily be turned into a non-recursive algorithm:

This function returns the correct result because \(B \cdot A^n\) (respectively \(B + nA\)) equals the desired result before and after every loop iteration and we repeat the loop until \(n = 0\). Unlike the variant on Wikipedia, the above algorithm wastes one group operation in the last iteration when \(n = 1\). On the other hand, we don’t have to handle the case where \(n = 0\) separately. Since computers represent numbers in binary, you can check whether \(n\) is odd with a bitwise and (typically written as n & 1 === 1) and divide \(n\) by \(2\) without having to subtract the least-significant bit first by shifting the bits one to the right (typically written as n >> 1). Since I haven’t yet introduced any groups of interest, I will provide an interactive tool for fast repetitions later on.

A set is a collection of distinct elements. When a variable is used to denote a set, it is often written in blackboard bold, such as \(\mathbb{Z}\) for the set of integers, \(\mathbb{R}\) for the set of real numbers, and \(\mathbb{C}\) for the set of complex numbers. The symbol \(\in\) is used to denote that \(A\) “is” an element of the set \(\mathbb{G}\), written as \(A \in \mathbb{G}\). I put “is” in quotation marks because the same notation is used when \(A\) is not an element of the set but rather a variable which represents an element of the set. Sets are usually defined by enumerating all its elements within curly brackets, such as \(\{1, 2, 3\}\), or by specifying a criteria for its elements after a vertical bar, such as \(\{x \in \mathbb{Z} \mid x > 2\}\) for the set of integers greater than two.

As we saw earlier, the hours of an analog clock form a finite group under addition. Using the above notations, we write the group as \(\mathbb{G} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\) and its order as \(|\mathbb{G}| = 12\).

We can determine the order of every element in the group which corresponds to an analog clock by repeating each element:

Since you get the inverse of any element \(A\) in any finite group simply by repeating \(A\), you may wonder why we require each element to have an inverse in the group as one of our axioms. The reason for this is that without invertibility, \(X \circ A = B\) can have several solutions, which means that you can get stuck in a loop which doesn’t involve the identity element. (To see this happening, set the modulus to a composite number in the repetition table of multiplicative groups below.) Instead of requiring that each element has an inverse, we can require that \(X \circ A = B\) and \(A \circ Y = B\) have a unique solution for any elements \(A\) and \(B\) of the group. This is an alternative definition of a group and makes even the identity axiom redundant, as we’ll see later.

As shown in a previous box, the elements \(1\), \(5\), \(7\), and \(11\) generate the additive group modulo 12: \(\mathbb{G} = ⟨1⟩ = ⟨5⟩ = ⟨7⟩ = ⟨11⟩\).

Repeating the inverse of \(G\) generates the group in the opposite direction because the inverse undoes one repetition at a time:

As a consequence, every cyclic group with more than two elements has an even number of generators because the inverse of every generator is also a generator. (Since each inverse is unique and the inverse of each inverse is the original element again, two different generators cannot have the same inverse — and a generator can equal its inverse only for groups of order 2.)

The group defined by an analog clock is cyclic and has an even number of generators, namely \(1\), \(5\), \(7 =_{12} -5\), and \(11 =_{12} -1\).

The group defined by an analog clock, which consists of the elements \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\), has the following subgroups: \(\{0\}\), \(\{0, 6\}\), \(\{0, 4, 8\}\), \(\{0, 3, 6, 9\}\), \(\{0, 2, 4, 6, 8, 10\}\), and \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\). Any other subset of \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\), such as \(\{0, 1, 2, 3\}\), is not closed. (As we’ll see later, all subgroups of cyclic groups are cyclic.)

As you may have noticed, I began to denote a group by its set in this section. The subgroup relation is usually written as \(\mathbb{H} ≤ \mathbb{G}\) (or as \(\mathbb{H} < \mathbb{G}\) if \(\mathbb{H} ≠ \mathbb{G}\)) instead of \(\mathbb{H} \subseteq \mathbb{G}\) because not every subset of elements forms a subgroup.

Given two subgroups \(\mathbb{H_1}\) and \(\mathbb{H_2}\) of a group \(\mathbb{G}\), their intersection \(\mathbb{H} = \mathbb{H_1} \cap \mathbb{H_2}\) is also a subgroup of \(\mathbb{G}\) because:

• \(\mathbb{H}\) is not empty because the identity element \(E\) of \(\mathbb{G}\) is included in both \(\mathbb{H_1}\) and \(\mathbb{H_2}\). Therefore, \(E \in \mathbb{H}\).
• \(\mathbb{H}\) is closed because for any elements \(A\) and \(B\) in \(\mathbb{H}\), \(A\) and \(B\) belong to both \(\mathbb{H_1}\) and \(\mathbb{H_2}\).
  Since \(\mathbb{H_1}\) and \(\mathbb{H_2}\) are closed, \(A \circ B \in \mathbb{H_1}\) and \(A \circ B \in \mathbb{H_2}\). Therefore, \(A \circ B \in \mathbb{H}\).

On the other hand, the union of two subgroups is generally not a subgroup.

Given the group \(\mathbb{G} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}\) with addition modulo 12, which corresponds to an analog clock, the subgroup \(\mathbb{H} = \{0, 3, 6, 9\}\) has the following cosets: \(\mathbb{H} + 0 = \{0, 3, 6, 9\}\), \(\mathbb{H} + 1 = \{1, 4, 7, 10\}\), \(\mathbb{H} + 2 = \{2, 5, 8, 11\}\), \(\mathbb{H} + 3 = \{3, 6, 9, 0\}\), and so on. (You can generate all cosets of a cyclic subgroup below.) It’s easy to verify that these subgroup cosets are either equal or disjoint as proven above. For example, \(\mathbb{H} + 0 = \mathbb{H} + 3\), whereas \(\mathbb{H} + 1 \cap \mathbb{H} + 2 = \varnothing\).

We determined the order of every element in the group which corresponds to an analog clock earlier. It’s easy to verify that the order of each element divides the group’s order. Since these generated subgroups are the only possible subgroups as explained later on, the order of every subgroup divides the group’s order. And since \(12A\) is a multiple of \(12\) for any element \(A\), we have that \(12A =_{12} 0\) for all elements of the group as implied by the second consequence of Lagrange’s theorem.

Given a group \(\mathbb{G}\) and a subgroup \(\mathbb{H}\), the ratio \(\frac{|\mathbb{G}|}{|\mathbb{H}|}\) is called the index of the subgroup or the cofactor in the case of elliptic curves.

If we restrict our attention to commutative groups, there’s a much simpler proof for why you get the identity element when you repeat an element of such a group as many times as there are elements in the group. (I found this proof on page 34 of Victor Shoup’s book.) Since you get different results when you combine an element \(A\) with two different elements \(B_1\) and \(B_2\), \(f(X) = A \circ X\) is an invertible function. This means that \(f(X)\) is a permutation, and thus \(f(\mathbb{G}) = \{f(B) \mid B \in \mathbb{G}\} = \mathbb{G}\). Using Greek letters to iterate over all the elements of a commutative group, we can observe the following:

You can replace \(B\) with \(f(B)\) and aggregate all \(A\) outside the loop only if the operation of the group is commutative. The order of every element has to divide the order of the group because it cannot be larger and you wouldn’t get the identity element if \(|\mathbb{G}|\) was not a multiple of \(|A|\). To make similar statements about non-commutative groups and non-cyclic subgroups, you still need Lagrange’s theorem with its cosets. This is probably why this proof is not more popular; but it is enough for our purposes.

An integer \(d\) which divides another integer \(n\) without a remainder is a co-called divisor of \(n\). This is usually written as \(d \mid n\), which means that there is an integer \(c\) so that \(c \cdot d = n\). In this context, the term “divisor” is used differently than in the Euclidean division above.

In many programming languages, including C, C++, Go, Java, and JavaScript, the % operator does not compute the remainder as presented here. Instead, these languages round the quotient towards zero and allow the remainder to be negative, which is listed as truncated division on Wikipedia. For example, -7 % 2 == -1, which means that you cannot test whether a potentially negative integer is odd by using n % 2 == 1. For the quotient, this behavior is probably desirable, which is why signed division is implemented like this in the IDIV instruction of the x86 instruction set. The situation becomes even more complicated if you allow the divisor/modulus to be negative.

For additive groups modulo some number, even the fact that a group is partitioned by subgroup cosets is somewhat intuitive:

Admittedly, this is the simplest possible case. What happens if you don’t hit \(0\) in the first pass and have to do more loops? If you repeat an element from the left side of the circle, then you just reach the elements in the opposite order (e.g. \((6 + 6)\ \%\ 9 = 3\) and \((3 + 6)\ \%\ 9 = 0\)). For a more sophisticated example, let’s look at the additive group modulo 14 with the element 6:

As you can see in the above graphic, the distance between adjacent elements of the subgroup is always the same. This has to be the case because repeating an element generates a cyclic subgroup, which is closed. As a consequence, the difference between the two closest elements is itself an element. (If we denote the closest elements as \(A\) and \(B\), then \(B + (-A)\) is also an element of the subgroup due to closure.) This difference can then be added and subtracted from all other elements. If this leads to an even smaller gap, you repeat this procedure until the subgroup is closed. If the original element does not generate the whole group, you get a disjoint coset when you rotate the generated subgroup by one. As we’ll see later, the difference between adjacent elements of the generated subgroup equals the greatest common divisor of the generating element and the modulus, and the first time you hit zero again corresponds to the least common multiple of these two numbers.

Given two statements \(P\) and \(Q\), “\(P\) if and only if \(Q\)” means that either both statements are true or neither of them is. In other words, \(P\) is necessary and sufficient for \(Q\) (and the other way around), which means that each statement implies the other. In formulas, this so-called material equivalence is usually written as \(\iff\), which is a binary truth function with the following truth table (using \(\top\) for true and \(\bot\) for false):

Being a Latin square is not a sufficient condition to form a group, which can be demonstrated with the following example:

This table lacks an identity row and column, but more importantly, the operation is not associative. For example, \((A \circ B) \circ C = A \circ C = C\), whereas \(A \circ (B \circ C) = A \circ B = B\). Since associativity makes a statement about three elements and not just two, it is difficult to spot whether an operation is associative based on its table. If an operation defined by a Latin square is associative, it does form a group, though. In order to understand why this is the case, we need to understand why an associative operation with unique solutions implies that the identity element is the same for all elements.

Since every column of the operation table is a permutation of the group’s elements, every element has to appear in its own column. This means that for every element \(D\), there exists an element \(E\) so that \(E \circ D = D\). By applying this element on both sides from the left, we get \(E \circ (E \circ D) = E \circ D\). Due to associativity, \((E \circ E) \circ D = E \circ D\). Since \(X \circ D = D\) has a unique solution, \(E \circ E = E\). In other words, every identity for a single element is idempotent. What remains to be seen is that an idempotent element is an identity for all elements.

For any element \(F\), \(E \circ X = F\) has a unique solution. Since \(E \circ E = E\), \((E \circ E) \circ X = F\) and thus \(E \circ (E \circ X) = F\). Using the fact that \(E \circ X = F\), it follows that \(F\) is the unique solution for \(E \circ X = F\). This is why an identity for one element is an identity for all elements. The identity element is unique because \(X \circ F = F\) would have two solutions otherwise. The same argument can be used to show that the right identity is also unique. The left identity \(E_L\) and the right identity \(E_R\) are the same because they are identities for each other: \(E_L = E_L \circ E_R = E_R\). Since you can get from any element to any other element in a Latin square, you can get to the unique identity from any element, which means that each element has an inverse.

We have shown that any associative operation which generates a Latin square forms a group. I cover an alternative proof for these alternative group axioms in the last chapter.

Before we continue, let’s fix the above operation table by starting with the necessary identity row and column:

We may try to complete the operation table by setting \(B \circ B\) to \(A\), but this would lead to a conflict in the third row and column:

Given that \(C\) has to occur in the middle row and column and cannot occur a second time in the last row and column, it has to be that \(B \circ B = C\). Another reason for this is that \(B \circ B = A\) makes the order of \(B\) 2 since \(A\) is the identity element; but this violates Lagrange’s theorem, which implies that the order of any element divides the order of the group. Therefore:

Since there was no other way to complete the operation table, this is the only group of order 3. In fact, all groups of prime order are unique up to a relabeling of the elements because as we saw earlier, groups of prime order are cyclic, and as we will see later, all cyclic groups of the same order behave identically. This particular group corresponds to the additive group modulo 3.

If you enjoy solving Sudokus, you might also enjoy solving the operation table for groups of higher order. For example, there are two solutions for groups of order 4. Can you find them? And can you prove that these are the only two groups of order 4? 🤓

Given a generator \(G\) which generates the cyclic group \(\mathbb{G} = \href{#group-generators}{⟨G⟩}\) of order \(n = \lvert \mathbb{G} \rvert = \lvert G \rvert\), there exists a single subgroup of order \(d\) for every divisor \(d\) of \(n\). We prove this statement by showing that such a subgroup exists and that it is unique:

For example, \(2\) generates the multiplicative group modulo \(13\) of order \(12\). A subgroup of order \(6\) is generated by \(2^{12/6} =_{13} 4\). Another subgroup of order \(6\) may contain \(9 =_{13} 2^8\). In this case, \(b = \frac{a \cdot d}{n} = \frac{8 \cdot 6}{12} = 4\). It follows that \(4^4 =_{13} 9\), which is true.

To get a better feeling for where an element with a certain order may or may not appear, you can enable the “Order” option.

Subgroups don’t have to be generated by a single element. For example, \(\{1, 4, 11, 14\}\) form a multiplicative group modulo \(15\):

Since each element is its own inverse, none of the elements generates the whole subgroup. Its cosets still partition the non-cyclic multiplicative group of coprime elements modulo 15:

The above tool just doesn’t support this case because we’re usually interested only in repetitions of a single element.

Quantum computers perform calculations using the physical properties of quantum mechanics, such as superposition. The discrete-logarithm problem can be solved efficiently on a sufficiently powerful quantum computer with Shor’s algorithm, named after Peter Shor (born in 1959). The quantum computers which have been built until now are by far not powerful enough to break modern cryptography, but since this might change in the future, cryptography which cannot be broken by quantum computers – so-called post-quantum cryptography – is an active area of research with increasing interest.

All tools in this chapter can handle arbitrarily large integers, which are easier to read when their digits are grouped with a delimiter. I prefer the apostrophe as a thousand separator, but other people have different preferences. From time to time, you may also want to copy numbers or expressions to other calculators or to source code, in which case it is best if the number or expression isn’t formatted at all. (Many programming languages actually allow underscores in integer literals.) For these reasons, I decided to make the outputs of my tools fully configurable, including the signs of various operations:

By convention, 1 is not included in the set of prime numbers in order to make statements involving prime numbers simpler.

Euclid’s theorem states that there are infinitely many prime numbers. It is named after Euclid, who proved it around 300 BCE. If there were only a finite number of primes, then the product of all primes plus 1 cannot be divided without remainder by any of the prime numbers. The new number is therefore either prime or has prime factors which were not accounted for. Since this is a contradiction, there has to be an infinite number of primes.

An integer is called \(n\)-smooth if none of its prime factors are greater than \(n\). As you can see when playing with the above tool, factoring large numbers is easy if most of their factors are sufficiently small. Since this is often undesirable in cryptographic applications, you have to choose the delicate parameters carefully.

The unique factorization theorem, which is also known as the fundamental theorem of arithmetic, states that every integer greater than 1 can be written uniquely – up to the order of the factors – as a product of prime numbers. It makes two claims:

• Existence: All integers greater than 1 can be factorized into primes because each of them is either composite or prime.
• Uniqueness: Suppose that there are integers greater than 1 which have distinct prime factorizations. Let \(n\) be the smallest such integer so that \(n = p_1 \cdot p_2 \cdot … \cdot p_k = q_1 \cdot q_2 \cdot … \cdot q_l\), where each \(p_i\) and each \(q_j\) is prime. Since \(p_1\) divides \(n = q_1 \cdot q_2 \cdot … \cdot q_l\), it has to divide one of the \(q_j\)s according to (a recursive application of) Euclid’s lemma. Since we don’t care about the order of the \(q_j\)s, let’s assume that \(p_1\) divides \(q_1\). Since both \(p_1\) and \(q_1\) are prime and greater than 1, it follows that \(p_1 = q_1\). When we cancel these factors on both sides of the equation, we get \(m = p_2 \cdot … \cdot p_k = q_2 \cdot … \cdot q_l\). Given that the two factorizations of \(n\) were distinct, these two factorizations of \(m\) have to be distinct as well. Since \(m < n\), \(n\) cannot be the smallest integer with distinct prime factorizations, which is a contradiction. Thus, each positive integer can be represented by a unique multiset of prime factors.

There is another way to see why elements which share a prime factor with the modulus are undesirable. If the integer \(a\) is not coprime with the modulus \(m\), then \(\operatorname{gcd}(a, m) > 1\) and \(\operatorname{lcm}(a, m) < a \cdot m\). This means that there is some integer \(b < m\) for which \(b \cdot a = \operatorname{lcm}(a, m)\). Since \(\operatorname{lcm}(a, m)\) is also a multiple of \(m\), \(b \cdot a =_m 0\). As I explained when I introduced multiplicative groups, \(0\) has to be excluded from the set of elements. Since a group has to be closed, we have to exclude \(a\) or \(b\). This problem can be observed in the operation table of multiplicative groups. If we set the modulus to 12, for example, we see that all the elements which are not coprime with the modulus (the tool marks them with a blue background) reach \(0\) at some point. After that, the elements repeat because \((b + 1) \cdot a =_m b \cdot a + 1 \cdot a =_m 0 + a =_m a\). The first factor for which we reach \(0\) is \(b = \frac{\operatorname{lcm}(a, m)}{a} = \frac{m}{\operatorname{gcd}(a, m)}\). This means that there are \(\operatorname{gcd}(a, m)\) repetitions in the rows and columns of non-coprime elements. It also implies that the equation \(a \cdot x =_m c\) has \(d = \operatorname{gcd}(a, m)\) solutions in \(\mathbb{Z}_m\) if \(c\) is a multiple of \(d\) and no solution otherwise.

As required by the group axioms, the multiplicative inverse of a coprime element is unique. Suppose that the coprime element \(a\) has two multiplicative inverses: \(b_1 \cdot a =_m 1\) and \(b_2 \cdot a =_m 1\). It follows that \(b_1 \cdot a =_m b_2 \cdot a\) and hence that \(b_1 \cdot a - b_2 \cdot a =_m 0\). This means that \(b_1 \cdot a - b_2 \cdot a = (b_1 - b_2) \cdot a\) is a multiple of \(m\). Since \(\operatorname{\href{#greatest-common-divisor}{gcd}}(a, m) = 1\), \(m\) has to divide \(b_1 - b_2\) according to a generalized version of Euclid’s lemma. (Its proof required only that \(p\) and \(a\) are coprime, which means that \(p\) has to be only relatively prime to one of the factors, not “absolutely” prime.) Therefore, \(b_1\) has to equal \(b_2\) up to a multiple of \(m\).

I used the following two shortcuts in the description of the Chinese remainder theorem, which you might not be familiar with:

• Capital-sigma notation: \(\sum_{i=1}^{l} r_i \cdot N_i \cdot M_i = r_1 \cdot N_1 \cdot M_1 + … + r_l \cdot N_l \cdot M_l\), and
• Capital-pi notation: \(\prod_{i=1}^l m_i = m_1 \cdot … \cdot m_l\), where \(i\) is the index which is incremented.

The Chinese remainder theorem is more intuitive than it may seem. Given two pulses with coprime repetition frequencies, it’s clear that the phase of one pulse shifts relative to the phase of the other pulse until they re-align at the least common multiple:

The offset between the two pulses has to be different throughout this cycle. If the same offset occurred twice, the difference between the two occurrences would be a multiple of both frequencies smaller than the least common multiple, which is a contradiction. (This argument is similar to the one we used to establish that you reach the identity element before any of the group’s elements can appear again when repeating an element.) This is also why all (and only) the coprime elements generate the additive group. In the above example, there are 5 offsets to cover and 5 green ticks before the cycle repeats. Since no two offsets may be the same, all 5 offsets are covered due to the pigeonhole principle. (On the other side of the number line, there are 7 offsets to cover with 7 blue ticks.) The difference between the two remainders in the tool above determines into which repetition the solution falls. For example, if the first remainder is one smaller than the second remainder, the solution is 15 + r₁.

All cyclic groups of the same order are isomorphic. As we saw earlier, additive groups are always cyclic. This means that all cyclic groups of order \(m\) are isomorphic to \(\mathbb{Z}_m^+\) and thus commutative. Given a generator \(G\), \(\href{#group-generators}{⟨G⟩} \cong \mathbb{Z}_m^+\) if and only if \(\lvert G \rvert = m\).

In some groups, the inverse isomorphism is difficult to compute, giving us the linear one-way functions we were looking for.

Given two subgroups \(\mathbb{H_1}\) and \(\mathbb{H_2}\) of a commutative group \(\mathbb{G}\) which have no element in common other than the identity element \(E\) (i.e. \(\mathbb{H_1} \cap \mathbb{H_2} = \{E\}\)), the so-called internal direct product \(\mathbb{H_1} \circ \mathbb{H_2} = \{A_1 \circ A_2 \mid A_1 \in \mathbb{H_1}, A_2 \in \mathbb{H_2}\}\) is isomorphic to the direct product \(\mathbb{H_1} \times \mathbb{H_2}\) (i.e. \(\mathbb{H_1} \times \mathbb{H_2} \cong \mathbb{H_1} \circ \mathbb{H_2}\)). The isomorphism is given by the function \(f\big((A_1, A_2)\big) = A_1 \circ A_2\), which maps elements of \(\mathbb{H_1} \times \mathbb{H_2}\) to elements of \(\mathbb{H_1} \circ \mathbb{H_2}\). In order to show that this is indeed an isomorphism, we need to show that \(f\) is compatible with the group operations (i.e. \(f(A \circ_1 B) = f(A) \circ_2 f(B)\)) and invertible:

• Compatibility: \(f\big((A_1, A_2) \circ (B_1, B_2)\big) = f\big((A_1 \circ B_1, A_2 \circ B_2)\big) = (A_1 \circ B_1) \circ (A_2 \circ B_2) = (A_1 \circ A_2) \circ (B_1 \circ B_2) = f\big((A_1, A_2)\big) \circ f\big((B_1, B_2)\big)\) due to associativity and commutativity.
• Invertibility (a so-called bijection): The function \(f\) is invertible if the following two criteria are fulfilled:
  • Distinct elements are mapped to distinct elements (injectivity): This is the case if we obtain equal outputs only for equal inputs. In other words, we need to show that \(f\big((A_1, A_2)\big) = f\big((B_1, B_2)\big)\) implies \((A_1, A_2) = (B_1, B_2)\). As \(A_1 \circ A_2 = B_1 \circ B_2\), we have that \(\overline{B_1} \circ A_1 = B_2 \circ \overline{A_2}\). Clearly, \(\overline{B_1} \circ A_1 \in \mathbb{H_1}\) and \(B_2 \circ \overline{A_2} \in \mathbb{H_2}\) due to closure. Since the identity element is the only element which is in both \(\mathbb{H_1}\) and \(\mathbb{H_2}\), \(\overline{B_1} \circ A_1 = E\) and \(B_2 \circ \overline{A_2} = E\). Thus, \(A_1 = B_1\) and \(A_2 = B_2\).
  • Every element of the target group is reached (surjectivity): Since every element in \(\mathbb{H_1} \circ \mathbb{H_2}\) is of the form \(A_1 \circ A_2\) by definition, there’s an input for every element in \(\mathbb{H_1} \circ \mathbb{H_2}\), namely \((A_1, A_2)\) because \(f\big((A_1, A_2)\big) = A_1 \circ A_2\).

Given a finite commutative group \(\mathbb{G}\) with two elements \(A_1\) and \(A_2\) so that \(\operatorname{\href{#greatest-common-divisor}{gcd}}(|A_1|, |A_2|) = 1\), the order of \(A_1 \circ A_2\) is \(|A_1| \cdot |A_2|\). Since \(A_1\) generates the subgroup \(\href{#group-generators}{⟨A_1⟩}\) and \(A_2\) generates the subgroup \(⟨A_2⟩\), their intersection is a subgroup of both \(⟨A_1⟩\) and \(⟨A_2⟩\). By Lagrange’s theorem, \(|⟨A_1⟩ \cap ⟨A_2⟩|\) divides both \(|⟨A_1⟩|\) and \(|⟨A_2⟩|\). Since \(\operatorname{gcd}(|⟨A_1⟩|, |⟨A_2⟩|) = 1\), \(|⟨A_1⟩ \cap ⟨A_2⟩|\) has to equal \(1\). Since the identity element \(E\) is part of every subgroup, \(⟨A_1⟩ \cap ⟨A_2⟩ = \{E\}\). According to the previous box, \(⟨A_1⟩ \circ ⟨A_2⟩\) is thus isomorphic to \(⟨A_1⟩ \times ⟨A_2⟩\). Therefore, \(|A_1 \circ A_2| = |(A_1, A_2)| = \operatorname{\href{#least-common-multiple}{lcm}}(|A_1|, |A_2|) = |A_1| \cdot |A_2|\).

Euler’s theorem is a generalization of Fermat’s little theorem: For any coprime integers \(a\) and \(m\), we have that \(a^{\varphi(m)} =_m 1\).

We saw that all cyclic groups are isomorphic to the additive group of the same order. Any element \(A\) that is coprime with the modulus \(m\) generates the additive group because \(mA\) is the first time you get a multiple of \(m\). (If there was a smaller number \(n\) such that \(nA =_m 0\), then the least common multiple of \(A\) and \(m\) would be smaller than \(mA\), which means that their greatest common divisor would be larger than \(1\).) As a consequence, the number of generators of any cyclic group \(\mathbb{G}\) is given by \(\varphi(|\mathbb{G}|)\).

As shown earlier, all subgroups of cyclic groups are cyclic, and a unique subgroup exists for every divisor \(d\) of the group’s order \(n\). Since subgroups are groups, the cyclic subgroup of order \(d\) has \(\varphi(d)\) generators. This means that in a cyclic group of order \(n\), there are exactly \(\varphi(d)\) elements of order \(d\) for every divisor \(d\) of \(n\). According to Lagrange’s theorem, each of the \(n\) elements has an order which divides \(n\). This implies that the sum of the Euler’s totient function of every divisor \(d\) of \(n\) equals \(n\):

If you enable the “Totient” option in the repetition tables above, you see the output of the Euler’s totient function for every divisor of the group’s order in a separate row. The sum of all the values in this row plus \(1\) for the identity element, whose count is covered by the label \(\varphi(i)\), equals the number of elements in the group. Please note that the value in the totient row matches the number of elements with the given order only if the group is cyclic.

The so-called exponent of the multiplicative group \(\mathbb{Z}_m^\times\) is the smallest positive integer \(n\) so that \(A^n =_m 1\) for all elements \(A\) of the group. Clearly, \(n\) divides the order of the group and is a multiple of the order of each element, including the largest one. In this box, we show that an element of order \(n\) exists, which implies that \(\lambda(m) = n\) and \(A^{\lambda(m)} =_m 1\) for any number \(A\) which is coprime with the modulus \(m\). This is in fact how Carmichael’s totient function is usually defined. Since \(\lambda(m) ≤ \varphi(m)\) for any positive integer \(m\), Carmichael’s totient function gives a tighter exponent than Euler’s totient function in Euler’s theorem.

Let \(\prod_{i=1}^l p_i^{e_i}\) be the prime factorization of the exponent \(n\). For each \(i\) between (and including) \(1\) and \(l\), there exists an element \(A_i \in \mathbb{Z}_m^\times\) so that \(A_i^{n/p_i} ≠_m 1\). If no such \(A_i\) could be found for some \(i\), \(n/p_i\) would be an exponent smaller than \(n\) which results in \(1\) for all elements of the group, which would contradict the minimality of \(n\). Given such an element \(A_i\) for each \(i\), the element \(A_i^{n/p_i^{e_i}}\) has order \(p_i^{e_i}\) because \((A_i^{n/p_i^{e_i}})^{p_i^{e_i}} =_m A_i^n =_m 1\) and \((A_i^{n/p_i^{e_i}})^{p_i^{e_i - 1}} =_m A_i^{n/p_i} ≠_m 1\) (see the previous box). As all the prime powers of a prime factorization are coprime with one another, the order of \(\prod_{i=1}^l A_i^{n/p_i^{e_i}}\) is \(n\) according to an earlier theorem.

Let’s start with the simplest case: \(\mathbb{Z}_p^\times\) is cyclic if \(p\) is prime. In order to prove this, we need math which we haven’t covered yet:

1. \(\href{#integers-modulo-m}{\mathbb{Z}_p} = \{0, …, p - 1\}\) is a finite field over which polynomials can be defined. We’ll discuss finite fields later in this article.
2. A non-constant single-variable polynomial of degree \(d\) over any field evaluates to \(0\) for at most \(d\) distinct inputs. In other words, \(f(x) = \sum_{i=0}^d c_i x^i\) with some coefficients \(c_0,\allowbreak …,\allowbreak c_d \in \mathbb{Z}_p\) where \(d > 0\) and at least \(c_d ≠ 0\) has at most \(d\) roots. Confusingly enough, this statement is also known as Lagrange’s theorem. When formulated over the field of complex numbers, it is also known as the fundamental theorem of algebra. We’ll prove it in the article about coding theory.

We learned in the previous box that \(A^{\lambda(p)} =_p 1\) for all elements \(A\) of \(\mathbb{Z}_p^\times\). This means that the polynomial \(f(X) =_p X^{\lambda(p)} - 1\) evaluates to \(0\) for all \(\varphi(p) = p - 1\) elements of \(\mathbb{Z}_p^\times\). Since a polynomial of degree \(\lambda(p)\) over a field can have at most \(\lambda(p)\) roots, \(\lambda(p)\) cannot be smaller than \(\varphi(p)\). Therefore, \(\lambda(p) = \varphi(p)\), which implies that \(\mathbb{Z}_p^\times\) is cyclic. Please note that this argument works only for fields (i.e. if the modulus is prime). In \(\mathbb{Z}_{24}\), for example, \(X^2 - 1 =_{24} 0\) has 8 solutions.

Even though we know that \(\mathbb{Z}_p^\times\) is cyclic for any prime \(p\) and that it has \(\varphi(p - 1)\) generators, no formula is known for finding a generator without searching. We’ll discuss how to find a generator for a multiplicative group in the last section of this chapter.

Since \(\mathbb{Z}_{p^e}\) is not a field for any integer \(e > 1\), we need four additional facts to prove that \(\mathbb{Z}_{p^e}^\times\) is cyclic for any odd prime \(p\).

Since multiplication distributes over addition, we have that \((a + b)(c + d) = a(c + d) + b(c + d) = ac + ad + bc + bd\). More generally, when evaluating the product of two sums, you add up all possible products of a term from the first sum and a term from the second sum. If the two sums are the same, you get some products several times: \((a + b)^2 = (a + b)(a + b) = aa + ab + ba + bb = a^2 + 2ab + b^2\). The same is true for powers greater than \(2\). In the case of \((a + b)^n\), each product consists of \(n\) instead of \(2\) terms. How many times do we obtain the product \(a^ib^{n-i}\) for some integer \(i\) between \(0\) and \(n\) when we expand \((a + b)^n\)? The first \(a\) can be chosen from any of the \(n\) sums, the second \(a\) from any of the remaining \(n - 1\) sums, and so on until you have \(n - i + 1\) options left for the \(i\)^th \(a\). Since we don’t care about the order in which we picked the \(a\)s in a specific product of \(a\)s and \(b\)s, we have to divide the integer that we obtained so far by the number of ways in which \(i\) \(a\)s can be ordered. The first \(a\) can be any of the \(i\) \(a\)s, the second \(a\) any of the remaining \(i - 1\) \(a\)s, and so on. \(i \cdot (i - 1) \cdot … \cdot 2 \cdot 1\) is the so-called factorial of \(i\), which is usually written with an exclamation mark as \(i!\). The number of ways in which you can pick \(i\) \(a\)s out of \(n\) sums is:

This is known as the binomial coefficient, which is often written as the two numbers above each other in parentheses. Since no choice is left for the \(n - i\) \(b\)s, we don’t need to account for them. Instead of choosing the \(i\) \(a\)s, we could choose the \(n - i\) \(b\)s, though, which would give us the same result as \(\binom{n}{i} = \binom{n}{n - i}\). Putting everything together, we get the binomial theorem:

\(\binom{p}{i} =_p 0\) for any prime \(p\) and any integer \(i\) strictly between \(0\) and \(p\) (i.e. \(0 < i < p\)). Proof: Since \(\binom{p}{i} = \frac{p (p-1) (p-2) … (p-i+1)}{i!}\) must be an integer given what it counts, \(i!\) divides \(p (p-1) (p-2) … (p-i+1)\). Since \(p\) is prime and all factors in \(i!\) are smaller than \(p\), \(\operatorname{\href{#greatest-common-divisor}{gcd}}(p, i!) = 1\). By Euclid’s lemma, \(i!\) then has to divide \((p-1) (p-2) … (p-i+1)\). Therefore, \(\binom{p}{i}\) is a multiple of \(p\).

Given a prime \(p\) and a positive integer \(e\), \(a =_{p^e} b\) implies \(a^p =_{p^{e+1}} b^p\) for any integers \(a\) and \(b\).

Proof: \(a =_{p^e} b\) means that \(a = b + cp^e\) for some integer \(c\). Thus, \(a^p = (b + cp^e)^p = b^p + pb^{p-1}cp^e + dp^{2e}\) for some integer \(d\). (See the binomial theorem if you struggle with this expansion.) As a consequence, \(a^p\) equals \(b^p\) up to some multiple of \(p^{e+1}\).

Given a prime \(p\) and a positive integer \(e\) with \(p^e > 2\), \(a =_{p^{e+1}} 1 + p^e\) implies \(a^p =_{p^{e+2}} 1 + p^{e+1}\) for any integers \(a\) and \(b\).

Proof: According to the previous box, \(a =_{p^{e+1}} 1 + p^e\) implies \(a^p =_{p^{e+2}} (1 + p^e)^p\). Using the binomial theorem, we get:

Since \(\binom{p}{i}\) is divisible by \(p\) for \(0 < i < p\), we conclude that \(\binom{p}{i} p^{ei}\) is divisible by \(p^{1+2e}\) for \(2 ≤ i < p\). Since \(1 + 2e ≥ e + 2\) for all \(e ≥ 1\), we can ignore the terms of the second sum when computing modulo \(p^{e+2}\). By the requirement that \(p^e > 2\), either \(p ≥ 3\) or \(e ≥ 2\). In both cases, \(ep ≥ e + 2\). Therefore, we can ignore \(p^{ep}\) as well, which leaves us with \((1 + p^e)^p =_{p^{e+2}} 1 + p^{e+1}\).

In this box, we want to show that \(\mathbb{Z}_{p^e}^\times\) is cyclic for any odd prime \(p\) and any integer \(e > 1\). We learned earlier that \(\mathbb{Z}_p^\times\) is cyclic. Let \(G\) be a generator of \(\mathbb{Z}_p^\times\) and \(n\) be the order of \(G\) in \(\mathbb{Z}_{p^e}^\times\). Since \(G^n =_{p^e} 1\), \(G^n =_p 1\). (If \(G^n - 1\) is a multiple of \(p^e\), it is also a multiple of \(p\) because \(p^e\) is a multiple of \(p\).) Therefore, \(n\) has to be a multiple of \(p - 1\), which is the order of \(\mathbb{Z}_p^\times\). Since \(n\) is the smallest positive integer so that \(G^n =_{p^e} 1\), \(G^{n/(p-1)}\) has an order of \(p - 1\) in \(\mathbb{Z}_{p^e}^\times\). If we find an element \(H\) with an order of \(p^{e-1}\) in \(\mathbb{Z}_{p^e}^\times\), then \(H \cdot G^{n/(p-1)}\) has an order of \(p^{e-1} (p - 1) = \varphi(p^e)\) according to an earlier theorem.

We now show that \(H = 1 + p\) has an order of \(p^{e-1}\) in \(\mathbb{Z}_{p^e}^\times\). According to the previous box, \(H =_{p^2} 1 + p\) implies \(H^p =_{p^3} 1 + p^2\). If \(e > 2\), \(p^e\) is a multiple of \(p^3\), and thus \(H^p ≠_{p^e} 1\). When we raise \(H^p\) to the power of \(p\) again, we get \(H^{p^2} =_{p^4} 1 + p^3\). This continues until \(H^{p^{e-1}} =_{p^{e+1}} 1 + p^e =_{p^e} 1\). Since this is the first time that we reach the identity element, the order of \(H\) is \(p^{e-1}\).

You can use the repetition table to verify that \(\mathbb{Z}_2^\times\) and \(\mathbb{Z}_4^\times\) are cyclic and that \(\mathbb{Z}_8^\times\) has no generator. In this box, we first show that every element in \(\mathbb{Z}_{2^e}^\times\) for an integer \(e > 2\) has an order of at most \(2^{e - 2}\). This is an upper bound for \(\lambda(2^e)\). By showing that the element \(5\) has this order, we establish the same value as a lower bound, which implies that \(\lambda(2^e) = 2^{e - 2}\) for \(e > 2\).

We first observe that all even integers have the factor \(2\) in common with powers of \(2\) and that all odd integers are coprime with powers of \(2\). Therefore, any element \(A \in \mathbb{Z}_{2^e}^\times\) can be written as \(A = 1 + 2b\) for some integer \(b\). Using our algebraic skills, \(A^2 = (1 + 2b)^2 = 1 + 4b + 4b^2 = 1 + 4b(1 + b)\). Since either \(b\) or \(1 + b\) is even, \(c = \frac{b(1 + b)}{2}\) is an integer. Therefore, \(A^2 = 1 + 8c\). For \(e = 3\), we have seen that \(A^{2^{e-2}} = 1 + 2^ec\), which means that \(A^{2^{e-2}} =_{2^e} 1\). By induction, we show that this is also true for any \(e > 3\): \((A^{2^{e-2}})^2 = A^{2^{e-1}} = (1 + 2^ec)^2 = 1 + 2 \cdot 2^ec + 2^{2e}c^2 = 1 + 2^{e+1}(c + 2^{e-1}c^2)\), which means that \(A^{2^{e-1}} =_{2^{e+1}} 1\).

With the same argument as in the previous box, we prove that the element \(5\) has an order of \(2^{e - 2}\) in \(\mathbb{Z}_{2^e}^\times\). This time, though, we start with \(5 =_{2^3} 1 + 2^2\), which means that we have \(H =_{p^3} 1 + p^2\) for \(p = 2\) before raising \(H\) to the power of \(p\) for the first time. As a consequence, we lag one exponentiation behind when compared to the previous box, which is why the order of \(5\) is \(2^{e-2}\) instead of \(2^{e-1}\). Ignoring this and working it out again, we get \(5^{2^i} =_{2^{3+i}} 1 + 2^{2+i}\) when squaring \(5\) \(i\) times according to this box. When \(i = e - 2\), we have \(5^{2^{e-2}} =_{2^{e+1}} 1 + 2^e =_{2^e} 1\). When \(i = e - 3\), \(5^{2^{e-3}} =_{2^e} 1 + 2^{e-1} ≠_{2^e} 1\). Therefore, \(|5| = 2^{e-2}\).

• Input n: The input \(n\) has to be odd because the inputs are shared with the Miller-Rabin primality test, which cannot handle even inputs. (For even inputs, the candidate 2 is always a witness as we’ll see in the next box.)
• Seed: As many candidates as indicated by the “Rounds” slider are generated pseudo-randomly from the given seed. This allows you to revisit earlier candidates and share interesting outputs with others. Another benefit is that you get a new set of candidates simply by changing the seed, such as by clicking on the “Increment” button. If you implement a probabilistic primality test yourself, there’s no reason to use a pseudo-random number generator (PRNG) like I did. In particular, using a known seed is dangerous in an adversarial setting. (The design choice of generating candidates deterministically also made it easy to use the same candidates in the tool of the Miller-Rabin primality test below.)
• Abort: If you want to find liars for a particular input, you don’t want the tool to stop after encountering a witness. This is why the tool allows you to disable the “Abort”, which you wouldn’t do if you care only about whether the input is probably prime.

A composite integer \(n\) is a Carmichael number if and only if Carmichael’s totient function \(\lambda(n)\) divides \(n - 1\). If this is the case, then \(A^{n-1} =_n A^{\lambda(n) \cdot c} =_n 1^c =_n 1\) for all \(A\) which are coprime with \(n\) and some integer \(c\). These numbers are also named after Robert Daniel Carmichael (1879 − 1967). The Fermat primality test fails to detect Carmichael numbers as composite only if all the chosen candidates are coprime with the number which is being tested. If a candidate \(A\) is not coprime with the integer \(n\), \(A\) has no multiplicative inverse, and the closest you can get to a multiple of \(n\) is \(\operatorname{\href{#greatest-common-divisor}{gcd}}(A, n)\). In other words, if \(\operatorname{gcd}(A, n) > 1\), then \(A^{n-1} ≠_n 1\). Thus, \(\mathbb{L}_n^F = \mathbb{Z}_n^\times\). If you use the first dozen prime numbers as candidates, which the tool above does by default, the Fermat primality test fails for only 2 out of the first 33 Carmichael numbers as given by this list from the On-Line Encyclopedia of Integer Sequences (OEIS): 252’601 = 41 · 61 · 101 and 410’041 = 41 · 73 · 137. All the other numbers on the list have a factor smaller than 41. As we will see in the next box, there’s a formula to obtain Carmichael numbers which don’t have a small factor.

If you find an integer \(k\) so that \(6k + 1\), \(12k + 1\), and \(18k + 1\) are prime, then \(n = (6k + 1)(12k + 1)(18k + 1)\) is a Carmichael number since \(\href{#carmichaels-totient-function}{\lambda}(n) = \operatorname{\href{#least-common-multiple}{lcm}}(6k, 12k, 18k) = 36k\) divides \(n - 1 = 1296k^3 + 396k^2 + 36k\). (\(1296 / 36 = 36\) and \(396 / 36 = 11\).) The small subset of Carmichael numbers which are of this form are called Chernick’s Carmichael numbers, named after Jack Chernick (1911 − 1971), who lacks an entry on Wikipedia. As we learned in the previous box, the Fermat primality test detects the compositeness of a Carmichael number only if one of the tested candidates is a multiple of one of its prime factors. The probability that a random candidate is a liar, and we thus fail to detect the compositeness of the Carmichael number \(n\) in any particular round, is \(\frac{|\mathbb{L}_n^F|}{|\mathbb{Z}_n^{\cancel{0}}|} = \frac{\href{#eulers-totient-function}{\varphi}(n)}{n-1}\). Since each round is independent from the others, the failure rate after 100 rounds is \(\big(\frac{\varphi(n)}{n-1}\big)^{100}\).

It is no coincidence that Chernick’s formula for Carmichael numbers is a product of three prime numbers. In this box we’ll show that every Carmichael number is a product of at least three distinct primes. Let \(n = p_1^{e_1} \cdot … \cdot p_l^{e_l}\) be the prime factorization of an arbitrary Carmichael number. This factorization has the following four properties (see page 308 in Victor Shoup’s book):

1. \(n\) is odd, i.e. \(p_i ≠ 2\) for all \(i \in \{1, …, l\}\): If \(n\) was even, \(n - 1\) would be odd and the coprime element \(-1 =_n n - 1\) would be a witness because \(-1^d =_n -1 ≠_n 1\) for any odd integer \(d\). Since \(n\) is a Carmichael number, this cannot be the case.
2. \(e_i = 1\) for every \(i \in \{1, …, l\}\): The composite group \(\mathbb{Z}_n^\times\) is isomorphic to the direct product of \(\mathbb{Z}_{p_1^{e_1}}^\times, …, \mathbb{Z}_{p_l^{e_l}}^\times\). Since \(n\) is a Carmichael number, \(A^{n-1} =_n 1\) for every \(A \in \mathbb{Z}_n^\times\). Since the isomorphism maps \(1 \in \mathbb{Z}_n^\times\) to \((1, …, 1) \in \mathbb{Z}_{p_1^{e_1}}^\times \times … \times \mathbb{Z}_{p_l^{e_l}}^\times\), it has to be the case that \(A^{n-1} =_{p_i^{e_i}} 1\) for every \(A \in \mathbb{Z}_{p_i^{e_i}}^\times\). Since \(p_i\) is odd according to the previous point, \(\mathbb{Z}_{p_i^{e_i}}^\times\) is cyclic, and thus \(n - 1\) has to be a multiple of \(|\mathbb{Z}_{p_i^{e_i}}^\times| = \href{#eulers-totient-function}{\varphi}(p_i^{e_i}) = p_i^{e_i-1} (p_i - 1)\). With \(e_i > 1\), \(p_i^{e_i-1} (p_i - 1)\) would be a multiple of \(p_i\) and thus \(n - 1\) would also be a multiple of \(p_i\). However, given that \(p_i\) is a factor of \(n\), \(e_i\) has to be \(1\) because \(n\) and \(n - 1\) cannot both be multiples of \(p_i\).
3. \(p_i - 1\) divides \(n - 1\) for all \(i \in \{1, …, l\}\): I explained in the previous point why \(n - 1\) has to be a multiple of \(p_i^{e_i-1} (p_i - 1)\). Now that we know that \(e_i = 1\), it follows that \(n - 1\) is a multiple of \(p_i - 1\).
4. \(l ≥ 3\): By definition, \(n\) has to be composite and thus \(l > 1\). Suppose \(l = 2\), which means that \(n\) is the product of two primes. According to the previous point, \(p_1 - 1\) divides \(n - 1\). Given that \(n - 1 = p_1 p_2 - 1 = (p_1 - 1) p_2 + (p_2 - 1)\), \(p_1 - 1\) has to divide \(p_2 - 1\). (\(a \cdot b + c\) can be a multiple of \(a\) only if \(c\) is a multiple of \(a\).) By a symmetric argument, \(p_2 - 1\) has to divide \(p_1 - 1\). However, two integers can be multiples of each other only if they are the same. Since our notation for the prime factorization requires the factors to be distinct, \(p_1\) cannot equal \(p_2\). Hence, \(n\) is the product of at least three distinct primes.

The second and the third point are sufficient for \(n\) to be a Carmichael number because they ensure that \(\href{#carmichaels-totient-function}{\lambda}(n)\) divides \(n - 1\) as required by our definition. This is known as Korselt’s criterion, named after Alwin Reinhold Korselt (1864 − 1947).

For a sufficiently large integer \(x\), there are at least \(x^{1/3}\) Carmichael numbers smaller than \(x\). On the other hand, the number of primes smaller than \(x\) is approximately \(\frac{x}{\log_\mathrm{e}(x)}\), where \(\log_\mathrm{e}(x)\) is the natural logarithm of \(x\). To give you an idea for how much rarer Carmichael numbers are than prime numbers: There are 2’220’819’602’560’918’840 ≈ 2 · 10¹⁸ prime numbers and only 8’220’777 ≈ 8 · 10⁶ Carmichael numbers below 100’000’000’000’000’000’000 = 10²⁰.

As we saw above, the Fermat liars \(\mathbb{L}_n^F\) form a subgroup of the coprime elements \(\mathbb{Z}_n^\times\) for all integers \(n\) greater than \(1\). Due to Lagrange’s theorem, \(|\mathbb{Z}_n^\times| / |\mathbb{L}_n^F|\) is an integer. This ratio is known as the index of the subgroup. If the index of \(\mathbb{L}_n^F\) is \(1\) and \(n\) is composite, \(n\) is a Carmichael number. If a composite \(n\) is not a Carmichael number, the index of \(\mathbb{L}_n^F\) has to be at least \(2\). There are integers for which half of all coprime elements are liars in the Fermat primality test:

If we want the ratio of Fermat liars to all candidates (i.e. \(|\mathbb{L}_n^F| / |\mathbb{Z}_n^{\cancel{0}}|\)) to be as close to 0.5 as possible, we’re interested in those integers which are the product of just two primes. Such integers are known as semiprimes. (The more primes there are in the prime factorization of \(n\), the smaller \(\frac{\href{#eulers-totient-function}{\varphi}(n)/2}{n-1}\) becomes.) It turns out that the semiprimes in the above list are of the form \(n = p \cdot q \textsf{,}\) where \(p\) and \(q\) are prime and \(q = 2p - 1\). The beginning of the list is the same, and we approach 0.5 for larger values of \(n\):

Therefore, 0.5 is indeed the best bound for the ratio of Fermat liars to all candidates of composite non-Carmichael numbers.

It turns out that the first \(l\) prime numbers form excellent candidates for the Miller-Rabin primality test:

The function \(f_y(X) =_n X^y\) computes the \(y\)^th power of any element \(X\) of the multiplicative group \(\mathbb{Z}_n^\times\). For any subset \(\mathbb{S} \subseteq \mathbb{Z}_n^\times\), we denote the so-called preimage of \(\mathbb{S}\) under \(f_y\) as \(f_y^{-1}(\mathbb{S}) = \{X \in \mathbb{Z}_n^\times \mid f_y(X) \in \mathbb{S}\}\). (As we will revisit later, \(f_y^{-1}(\{1\})\) is the so-called kernel of \(f_y\).) We need the following property in order to prove the Monier-Rabin bound on the number of liars: If \(\mathbb{Z}_n^\times\) is cyclic, \(|f_y^{-1}(\{1\})| = \operatorname{\href{#greatest-common-divisor}{gcd}}(y, \href{#eulers-totient-function}{\varphi}(n))\). Proof: Let \(G\) be a generator of the cyclic group, then for any \(X \in \mathbb{Z}_n^\times\), there’s an integer \(x\) so that \(X =_n G^x\). We want to determine the number of \(X \in \mathbb{Z}_n^\times\) for which \(X^y =_n (G^x)^y =_n 1\). Now \(G^z\) can equal \(1\) only if \(z\) is a multiple of \(\lvert G \rvert = \varphi(n)\). How many \(x \in \mathbb{Z}_{\varphi(n)}\) are there so that \(x \cdot y =_{\varphi(n)} 0\)? As we saw earlier, the answer is \(\operatorname{gcd}(y, \varphi(n))\).

Louis Monier (born in 1956) and Michael Oser Rabin (born in 1931) proved independently in 1980 that \(|\mathbb{L}_n^{MR}| / |\mathbb{Z}_n^{\cancel{0}}| ≤ \frac{1}{4}\) for any odd composite integer \(n\). As a consequence, the probability that an odd composite integer \(n\) is mislabeled as a probable prime after \(t\) rounds of the Miller-Rabin primality test with random candidates is at most \((\frac{1}{4})^t\). I adapted the following proof from page 309 of Victor Shoup’s book. You find similar approaches here and here in case you cannot follow my explanations.

After checking that \(n\) is odd and aborting the Miller-Rabin primality test otherwise, there are two cases to consider:

1. \(n = p^e\) for some odd prime \(p\) and an integer \(e > 1\): Since every Miller-Rabin liar is also a Fermat liar (i.e. \(\mathbb{L}_n^{MR} \subseteq \mathbb{L}_n^{F}\)), any upper bound on the latter also applies to the former (i.e. if \(|\mathbb{L}_n^{F}| ≤ \frac{n-1}{4}\), then \(|\mathbb{L}_n^{MR}| ≤ \frac{n-1}{4}\)). An element \(L \in \mathbb{Z}_n^\times\) is a Fermat liar if and only if \(L^{n-1} =_n 1\). Since multiplicative groups modulo a power of an odd prime are cyclic, there are \(|f_{n-1}^{-1}(\{1\})| \allowbreak = \operatorname{\href{#greatest-common-divisor}{gcd}}(n - 1, \href{#eulers-totient-function}{\varphi}(n))\) Fermat liars in \(\mathbb{Z}_n^\times\) according to the previous box. Using the definitions of Euler’s totient function \(\varphi\) and \(n\), we get \(\operatorname{gcd}(p^e - 1, p^{e-1}(p - 1))\). Clearly, \(p - 1\) divides \(p^{e-1}(p - 1)\). Since \((p - 1) \sum_{i=0}^{e-1} p^i \allowbreak = \big(\sum_{i=1}^e p^i\big) - \big(\sum_{i=0}^{e-1} p^i\big) \allowbreak = p^e - 1\), \(p - 1\) divides also \(p^e - 1\). (It’s obvious when putting it as \((m+1)^e =_m 1\) for \(m = p - 1\).) Since \(\sum_{i=0}^{e-1} p^i\) is not a multiple of \(p\) (as it is one more than a multiple of \(p\)), \(p - 1\) is the greatest common divisor of \(p^e - 1\) and \(p^{e-1}(p - 1)\). Finally, \(p - 1 = (p^e - 1) / \big(\sum_{i=0}^{e-1} p^i\big) = \frac{n - 1}{p^{e-1} + … + 1} ≤ \frac{n-1}{4}\) because \(p^{e-1} + 1 ≥ 4\) for any \(p ≥ 3\) and \(e ≥ 2\). Thus, \(|\mathbb{L}_n^{F}| ≤ |\mathbb{Z}_n^{\cancel{0}}| / 4\). This bound is reached for \(n = 9\) (i.e. \(p = 3\) and \(e = 2\)), where two out of eight elements (namely \(1\) and \(8\)) are Miller-Rabin liars. This is the reason why I write \(|\mathbb{L}_n^{MR}| / |\mathbb{Z}_n^{\cancel{0}}| ≤ \frac{1}{4}\) instead of \(|\mathbb{L}_n^{MR}| / |\mathbb{Z}_n^\times| ≤ \frac{1}{4}\) as \(\varphi(9) = 6\) and \(|\mathbb{L}_9^{MR}| / |\mathbb{Z}_9^\times| = \frac{2}{6} > \frac{1}{4}\).
2. \(n = p_1^{e_1} \cdot … \cdot p_l^{e_l}\) for \(l > 1\) distinct odd primes \(p_i\) and positive integers \(e_i\): This case is more complicated because \(\mathbb{L}_n^{MR}\) is generally not closed under multiplication. (For example, \(8\) and \(18\) are liars for \(n = 65\), but \(8 \cdot 18 =_{65} 14\) is a witness for the compositeness of \(n\).) The composite group \(\mathbb{Z}_n^\times\) is isomorphic to the direct product of \(\mathbb{Z}_{p_1^{e_1}}^\times, …, \mathbb{Z}_{p_l^{e_l}}^\times\). Let \(n - 1 = 2^cd\) for an integer \(c ≥ 1\) and an odd integer \(d\). Similarly, \(\varphi(p_i^{e_i}) = 2^{c_i}d_i\), where \(1 ≤ i ≤ l\) and \(d_i\) is odd. We define \(a\) as the smallest integer in the set \(\{c, c_1, …, c_l\}\). Since \(\varphi(p_i^{e_i})\) is even for any odd prime \(p_i\), \(a ≥ 1\). Next, we’ll prove a series of statements:
   • \(L^{2^ad} =_n 1\) for all \(L \in \mathbb{L}_n^{MR}\). If \(a = c\), this is the case because every Miller-Rabin liar is also a Fermat liar (i.e. \(L^{n-1} =_n 1\)). If \(a < c\), \(a = c_j\) for some index \(j\). If \(L^{2^bd} ≠_n 1\) for some \(L \in \mathbb{L}_n^{MR}\), we must have \(L^{2^bd} =_n -1\) for some \(b\) greater than or equal to \(a\) and smaller than \(c\) because \(L\) wouldn’t be a Miller-Rabin liar otherwise. If \(L^{2^bd} + 1\) is a multiple of \(n\), it is also a multiple of \(p_j^{e_j}\). Therefore, \(L^{2^bd} =_n -1\) implies that \(L^{2^bd} =_{p_j^{e_j}} -1\). Since \((L^d)^{2^b} =_{p_j^{e_j}} -1\) and \((L^d)^{2^{b+1}} =_{p_j^{e_j}} 1\), the order of \(L^d\) is \(2^{b+1}\) in \(\mathbb{Z}_{p_j^{e_j}}^\times\) according to an earlier theorem. However, the order of \(\mathbb{Z}_{p_j^{e_j}}^\times\) is \(2^{c_j}d_j\), which means that \(|L^d|\) does not divide \(|\mathbb{Z}_{p_j^{e_j}}^\times|\) because \(b + 1 > c_j\). Since this is a contradiction, there is no liar \(L \in \mathbb{L}_n^{MR}\) for which \(L^{2^ad} ≠_n 1\).
   • \(|\mathbb{L}_n^{MR}| ≤ 2 \cdot |f_{2^{a-1}d}^{-1}(\{1\})|\). It follows from the previous point and the definition of a Millar-Rabin liar that \(L^{2^{a-1}d} =_n ±1\) for all \(L \in \mathbb{L}_n^{MR}\). Therefore, \(\mathbb{L}_n^{MR} \subseteq f_{2^{a-1}d}^{-1}(\{1\}) \cup f_{2^{a-1}d}^{-1}(\{-1\})\). Let \(\{U_1, U_2, U_3, …, U_v\}\) denote all the elements of \(f_{2^{a-1}d}^{-1}(\{-1\})\). Then \(f_{2^{a-1}d}^{-1}(\{1\})\) cannot be smaller than \(f_{2^{a-1}d}^{-1}(\{-1\})\) because it contains at least the \(v\) elements \(\{U_1 \cdot U_1, U_1 \cdot U_2, U_1 \cdot U_3, …, U_1 \cdot U_v\}\). These elements are distinct because all preimages from \(U_1\) to \(U_v\) belong to \(\mathbb{Z}_n^\times\) and you get different results when you combine the same element with different elements in a group.
   • \(|f_y^{-1}(\{1\})| = \prod_{i=1}^{l} \operatorname{gcd}(y, 2^{c_i}d_i)\) for any positive integer \(y\). Since \(\mathbb{Z}_n^\times \cong \mathbb{Z}_{p_1^{e_1}}^\times \times … \times \mathbb{Z}_{p_l^{e_l}}^\times\), the number of elements in \(\mathbb{Z}_n^\times\) which map to \(1\) when being raised to the \(y\)^th power is given by the product of the number of elements which do the same in each of the groups \(\mathbb{Z}_{p_1^{e_1}}^\times\) to \(\mathbb{Z}_{p_l^{e_l}}^\times\). Since each \(\mathbb{Z}_{p_i^{e_i}}^\times\) is a cyclic group, the formula from the previous box can be used.

   • \(|f_{2^ad}^{-1}(\{1\})| = 2^l \cdot |f_{2^{a-1}d}^{-1}(\{1\})|\). According to the previous point, \(|f_{2^ad}^{-1}(\{1\})| = \prod_{i=1}^{l} \operatorname{gcd}(2^ad, 2^{c_i}d_i)\). Since \(a ≥ 1\) and \(c_i ≥ a\) for \(i = 1, …, l\), we have that \(|f_{2^ad}^{-1}(\{1\})| = 2^l \cdot \prod_{i=1}^{l} \operatorname{gcd}(2^{a-1}d, 2^{c_i}d_i) = 2^l \cdot |f_{2^{a-1}d}^{-1}(\{1\})|\). (This is why \(a\) has to be smaller than or equal to each \(c_i\); you wouldn’t be able to extract the factor \(2\) in each of the groups otherwise.)

   • \(|f_{2^ad}^{-1}(\{1\})| ≤ |f_{2^cd}^{-1}(\{1\})|\) because for any \(X \in \mathbb{Z}_n^\times\) for which \(X^{2^ad} =_n 1\), \(X^{2^cd} =_n 1\) since \(c ≥ a\).

   If follows from these statements that \(|\mathbb{L}_n^{MR}| ≤ 2^{-l+1} \cdot |f_{n-1}^{-1}(\{1\})|\) since \(|\mathbb{L}_n^{MR}| ≤ 2 \cdot |f_{2^{a-1}d}^{-1}(\{1\})| = 2 \cdot 2^{-l} \cdot |f_{2^ad}^{-1}(\{1\})| ≤ 2^{-l+1} \cdot |f_{2^cd}^{-1}(\{1\})| = 2^{-l+1} \cdot |f_{n-1}^{-1}(\{1\})|\) given that \(2^cd = n - 1\). There are two cases to consider:

   • \(l ≥ 3\): This implies that \(|\mathbb{L}_n^{MR}| ≤ |f_{n-1}^{-1}(\{1\})| / 4\). Since \(|f_{n-1}^{-1}(\{1\})| ≤ |\mathbb{Z}_n^\times|\) and \(|\mathbb{Z}_n^\times| < |\mathbb{Z}_n^{\cancel{0}}|\), we have \(|\mathbb{L}_n^{MR}| < |\mathbb{Z}_n^{\cancel{0}}| / 4\).

   • \(l = 2\): According to an earlier theorem, \(n\) cannot be a Carmichael number. Since in this case at most half of all coprime elements can be Fermat liars, we have that \(|f_{n-1}^{-1}(\{1\})| = |\mathbb{L}_n^{F}| ≤ |\mathbb{Z}_n^\times| / 2\). Thus, \(|\mathbb{L}_n^{MR}| ≤ 2^{-1} \cdot |f_{n-1}^{-1}(\{1\})| < |\mathbb{Z}_n^{\cancel{0}}| / 4\).

Since this algorithm tests many integers for their primality, the performance of the prime number generation is determined by the performance of the employed primality test. Here are some ways to reject composite inputs as quickly as possible:

• Trial division by small primes: Since every second number is a multiple of 2, every third number number is a multiple of 3, and so on, you can rule out a substantial fraction of inputs using trial division by small prime numbers. (To check that an input is odd, you have to verify only that the least-significant bit is 1.)
• Coprimality with product of small primes: You can check that an input is not a multiple of many small primes “at once” by checking that the input is coprime with their product using the Euclidean algorithm. The product of the first \(l\) prime numbers is known as the primorial number \(p_l\# = \prod_{i=1}^{l} p_i\), where \(p_i\) is the \(i\)^th prime number. For example, the product of the first 40 prime numbers is (see the last row of this table).
• Incremental instead of random search: Instead of choosing the next input randomly, you can increment the previous input by a known value. This has the advantage that you no longer need to perform the trial divisions if you store the remainders from the previous attempt. See the note 4.51 in the Handbook of Applied Cryptography for a more detailed discussion of this approach. (The tool above increments even inputs by 1 to make them odd before performing any primality checks.)

As I mentioned earlier, there are approximately \(\frac{x}{\log_\mathrm{e}(x)}\) prime numbers smaller than \(x\). Since half of all the integers are odd, the probability that a random odd integer smaller than \(x\) is prime is around \(\frac{x}{\log_\mathrm{e}(x)} / \frac{x}{2} = \frac{2}{\log_\mathrm{e}(x)}\). Denoting the number of bits we are interested in as \(l\), we get \(\frac{2}{\log_\mathrm{e}(2^l)}\). Since \(s = \log_\mathrm{e}(2^l)\) means that \(e^s = 2^l\), we can raise both sides by \(1 / l\) to get \(e^{s/l} = 2\). Thus, \(\log_\mathrm{e}(2) = s / l\) and \(s = l \cdot \log_\mathrm{e}(2) = \log_\mathrm{e}(2^l)\), which is one of the logarithmic identities. The number of independent trials needed to get a success is given by the geometric distribution. If the probability of success in each attempt is \(P\), it takes on average \(\frac{1}{P}\) attempts. As a consequence, the expected number of attempts needed to find a prime number with \(l\) bits is \(l \cdot \frac{\log_\mathrm{e}(2)}{2} = 0.34657 \cdot l ≈ \frac{1}{3} l\). The probability of finding a safe prime is \(P^2\), which means that it takes \((l \cdot \frac{\log_\mathrm{e}(2)}{2})^2 = 0.12 \cdot l^2\) attempts on average. The following table lists the expected number of attempts for lengths in the range of the tool above.

While I implemented some of the optimizations mentioned in the previous box, the tool is not fast enough to find a safe prime with 2’048 bits in a reasonable amount of time. I still wanted to support this length so that you get a sense for how large the prime number has to be in order to get a reasonable amount of security. (Finding a normal prime of this length is no problem.)

Since the Miller-Rabin primality test is a probabilistic primality test, what is the probability that the random search for a prime number returns a composite number? How many rounds do we have to perform in the Miller-Rabin primality test to push this probability below a certain value, such as \((\frac{1}{2})^{80}\)? You may think that this error probability is given by the Monier-Rabin bound on the number of liars, namely \((\frac{1}{4})^t\), where \(t\) denotes the number of rounds. However, this bound limits the probability that the Miller-Rabin primality test declares an input to be prime given that the input is composite. Using mathematical notation, this is \(P(D_t \mid C) ≤ (\frac{1}{4})^t\), where \(D_t\) denotes the event that the input is declared prime after \(t\) rounds of the Miller-Rabin primality test and \(C\) represents the event that the input is composite. (\(P(D_t \mid C)\) is a conditional probability, which is defined as \(P(D_t \mid C) = \frac{P(D_t\ \cap\ C)}{P(C)}\).) What we are interested in here, though, is the probability that an input is composite given that the Miller-Rabin primality test declared it to be prime after \(t\) rounds: \(P(C \mid D_t)\). Using Bayes’ theorem, we have

where \(r\) is the ratio of the inputs which are prime. Since the Miller-Rabin primality test declares all inputs which are prime to be prime, \(P(D_t) ≥ r\). If \(r\) is small, the probability \(P(C \mid D_t)\) can be considerably larger than \((\frac{1}{4})^t\). (For example, the probability of error is \(1\) if the set of candidates contains only composite numbers.) However, the fraction of Miller-Rabin liars is far smaller than \(\frac{1}{4}\) for most numbers. According to the note 4.49 in the Handbook of Applied Cryptography, it has been shown that just 6 rounds of the Miller-Rabin primality test are needed to push the probability that the random search for a 512-bit prime returns a composite number below \((\frac{1}{2})^{80}\). For 1’024 bits, 3 rounds are enough, and for 2’048 bits, it suffices to perform 2 rounds. Since you perform on average only a bit more than one round of the Miller-Rabin primality test for unsuccessful candidates even in the worst case, choosing a bigger \(t\) won’t affect the performance of the random search by much. The situation is different when searching for safe primes, but a better optimization is to increase your confidence that both \(p\) and \(q = 2p + 1\) are prime in parallel instead of gaining high certainty that \(p\) is prime before even considering \(q\). (I didn’t implement this optimization in the above tool because it wouldn’t match the visualization, including the counter of how many times \(p\) was prime.)

Please note that this discussion applies only to the case where the candidates are sampled randomly. If you test an input which is provided by an untrusted party, you can rely only on the worst-case error bound of \((\frac{1}{4})^t\). Not considering the adversarial setting has been an issue in many cryptography libraries. If you verify that an integer provided by someone else is prime, you should use 64 rounds to push the risk of being exploited below \(2^{-128}\). Alternatively, you can use the Baillie-PSW primality test, which is named after Robert Baillie, Carl Bernard Pomerance (born in 1944), John Lewis Selfridge (1927 − 2010), and Samuel Standfield Wagstaff Jr. (born in 1945). This primality test consists of a single round of the Miller-Rabin primality test with the candidate 2 followed by the Lucas probable prime test, which is named after François Édouard Anatole Lucas (1842 − 1891).

Since at most \(\frac{1}{4}\) of all candidates of a composite number are liars, the probability that you have to perform a second round of the Miller-Rabin primality test after performing a first round with a random candidate is at most \(\frac{1}{4}\) for any composite number. The probability that you need a third round is at most \(\frac{1}{16}\), and so on. In the worst case (the fraction of liars is usually much smaller than \(\frac{1}{4}\)), the expected number of rounds needed to detect that a composite number is composite is \(1 + \frac{1}{4} + \frac{1}{16} + … = \frac{4}{3}\). (\(s = \sum_{i=0}^{\infin} r^i = 1 + r + r^2 + …\) is a geometric series, which converges to \(\frac{1}{1-r}\) if \(|r| < 1\) because \(s - rs = s(1 - r) = 1\) as all but the first term cancel out.) We get the same result when we interpret this as the geometric distribution, whose expected value is \(\frac{1}{P}\), with a success probability of \(P = \frac{3}{4}\). Ignoring the optimizations mentioned above, we have to multiply the expected number of attempts to find a probable prime by \(\frac{4}{3}\) to get an estimate for the total number of Miller-Rabin primality test rounds before the last attempt, which returns the probable prime after an additional \(t\) rounds. This estimate is not really affected by the parameter \(t\). For example, when we search for a 2’048-bit prime, we expect to perform in the order of \(710 \cdot \frac{4}{3} = 947\) rounds of the Miller-Rabin primality test before the last attempt. Whether you perform an additional 2 or 64 rounds for the last attempt is only a matter of a few percentages. The above optimizations make the impact of the last attempt on the overall performance significantly bigger, but we’re still talking about percentages and not multiples when we change the parameter \(t\).

Given a generator \(G\) of a group \(\mathbb{G}\) of order \(n\), the element \(H = G^\frac{n}{d}\) generates the unique subgroup \(\mathbb{H}\) of order \(d\), where \(d\) is a divisor of \(n\). (The order of \(H\) has to be \(d\) because the order of \(G\) wouldn’t be \(n\) otherwise.) If the order of the desired subgroup \(\mathbb{H}\) is prime, you don’t need to find a generator of the supergroup \(\mathbb{G}\) first. To find a generator of the subgroup with the prime order \(p\), you can repeatedly choose a random element \(R \in \mathbb{G}\) until \(R^\frac{n}{p} ≠ I\). Once you have found an element \(R\) for which this is the case, the element \(R^\frac{n}{p}\) generates the subgroup of order \(p\). Proof: Clearly, \((R^\frac{n}{p})^p = I\) because \(A^n = I\) for all \(A \in \mathbb{G}\) due to Lagrange’s theorem. Since \((R^\frac{n}{p})^p = I\) and \((R^\frac{n}{p})^1 ≠ I\), it follows from an earlier theorem with \(e = 1\) that the order of \(R^\frac{n}{p}\) is \(p\).

Given a finite group \(\mathbb{G}\) and the prime factorization of its order \(n = p_1^{e_1}p_2^{e_2} … p_l^{e_l}\), we want to determine the order \(d\) of an element \(A\). Due to Lagrange’s theorem, \(d\) divides \(n\). Therefore, the multiset of the prime factors of \(n\) includes the multiset of the prime factors of \(d\), which means that \(d = p_1^{s_1}p_2^{s_2} … p_l^{s_l}\), where \(s_i ≤ e_i\) for \(i\) from \(1\) to \(l\). Since \(d\) is the order of \(A\), \(A^d = I\) and \(A^{c \cdot d} = (A^d)^c = I^c = I\) for any integer \(c\). This allows us to determine \(d\) by lowering each of the \(e_i\) to the lowest value \(s_i'\) for which \(A\) repeated \(d' = \prod_{i=1}^l p_i^{s_i'}\) times still equals the identity element. The important insight is that we can tweak each of the exponents independently from the others. As long as \(s_i' ≥ s_i\) for each of the exponents, \(d'\) is still a multiple of \(d\). As soon as one \(s_i' < s_i\), \(d'\) is no longer a multiple of \(d\), and thus \(A^{d'} ≠ I\). This gives us the following algorithm for determining the order of \(A\):

The algorithm does not require the group to be cyclic, but it requires that the prime factorization of the group’s order is known. The following tool implements the above algorithm for arbitrarily large numbers as long as it can determine and then factorize the order of the group with Pollard’s rho factorization algorithm. You can ignore the tab titled elliptic curve for now.

Given a cyclic, commutative group \(\mathbb{G}\) and the prime factorization of its order \(n = p_1^{e_1}p_2^{e_2} … p_l^{e_l}\), we get a generator \(G\) by doing

Before we can understand why this algorithm works, we must note that the above construction implies that

It follows from an earlier theorem that the order of \(G_i\) is \(p_i^{e_i}\). According to another theorem, the order of \(G\) is \(n\) because \(\operatorname{\href{#greatest-common-divisor}{gcd}}(|G_i|, |G_j|) = 1\) for all \(i ≠ j\). This means that if the algorithm terminates, \(G\) is indeed a generator of the group \(\mathbb{G}\).

This algorithm is quite fast because we need on average at most two attempts to find a suitable \(A\) for each \(p_i\). This is because:

1. The image \(\mathbb{H} = f_{n/p_i}(\mathbb{G})\) of the power function \(f_{n/p_i}\) is a subgroup of \(\mathbb{G}\): Since every element in \(\mathbb{H}\) is of the form \(A^{n/p_i}\) for some \(A \in \mathbb{G}\) and the group operation is commutative, \(A_1^{n/p_i} \cdot A_2^{n/p_i} = (A_1 \cdot A_2)^{n/p_i} \in \mathbb{H}\) because \(A_1 \cdot A_2 \in \mathbb{G}\). Thus, \(\mathbb{H}\) is closed. Since every element in \(\mathbb{G}\) is mapped to some element in \(\mathbb{H}\), \(\mathbb{H}\) is not empty. Therefore, \(\mathbb{H}\) is indeed a subgroup of \(\mathbb{G}\).
2. The order of \(\mathbb{H}\) is \(p_i\): Given a generator \(G\) of the group \(\mathbb{G}\), \(G^{n/p_i} \in \mathbb{H}\) has order \(p_i\) because \((G^{n/p_i})^{p_i} = G^n = I\). Since the group generated by \(G^{n/p_i}\) is included in \(\mathbb{H}\) due to closure, \(\mathbb{H}\) contains at least \(p_i\) elements. Since \(\mathbb{G}\) is cyclic, the subgroup \(\mathbb{H}\) is cyclic as well. So let \(H\) be a generator of \(\mathbb{H}\) and \(J \in f_{n/p_i}^{-1}(\{H\})\) be any of its preimages. Since the order of \(J\) can be at most \(n\) due to Lagrange’s theorem, the order of \(H = J^{n/p_i}\) can be at most \(p_i\). Therefore, \(\mathbb{H}\) contains exactly \(p_i\) elements.
3. The preimage \(\mathbb{K} = f_{n/p_i}^{-1}(\{I\})\) of the identity element \(I\) is a subgroup of \(\mathbb{G}\): \(I \in \mathbb{K}\) because \(I^{n/p_i} = I\). For any \(A_1, A_2 \in \mathbb{K}\) (i.e. \(A_1^{n/p_i} = I\) and \(A_2^{n/p_i} = I\)), \(A_1 \cdot A_2 \in \mathbb{K}\) because \((A_1 \cdot A_2)^{n/p_i} = A_1^{n/p_i} \cdot A_2^{n/p_i} = I\) due to commutativity. Since \(\mathbb{K}\) is non-empty and closed, \(\mathbb{K}\) is a subgroup of \(\mathbb{G}\). (As we will revisit later, \(\mathbb{K}\) is the so-called kernel of \(f_{n/p_i}\).)

4. \(f_{n/p_i}\) maps two inputs \(A\) and \(B\) to the same output if and only if they belong to the same coset of \(\mathbb{K}\):
   \(A^{n/p_i} = B^{n/p_i} \iff A^{n/p_i} / B^{n/p_i} = I \iff (A / B)^{n/p_i} = I \iff A / B \in \mathbb{K} \iff A \in \mathbb{K} \cdot B\).

5. \(A^{n/p_i}\) is distributed uniformly over \(\mathbb{H}\) as \(A\) is chosen at random from \(\mathbb{G}\) and all cosets contain the same number of elements.

6. \(P(A^{n/p_i} = I) = \frac{1}{p_i} ≤ \frac{1}{2}\) because of the previous point and \(|\mathbb{H}| = p_i\). Therefore, the probability of success when choosing \(A\) is \(P(A^{n/p_i} ≠ I) = 1 - \frac{1}{p_i} ≥ \frac{1}{2}\). Since the number of attempts needed to find a suitable \(A\) for each \(p_i\) follows the geometric distribution, the expected number of attempts is \(\frac{1}{1 - 1 / p_i} ≤ 2\).

You find a more elaborate analysis of the running time of this algorithm on page 328 of Victor Shoup’s book. The following tool implements the above algorithm for cyclic groups. As we saw earlier, a multiplicative group is cyclic if and only if \(\href{#carmichaels-totient-function}{\lambda}(m) = \href{#eulers-totient-function}{\varphi}(m)\), which is the case if and only if the modulus \(m = 2\), \(4\), \(p^e\), or \(2p^e\) for an odd prime \(p\) and a positive integer \(e\). In the case of elliptic curves, the situation is more complicated, and the tool simply aborts after 128 failed attempts to find a suitable \(A\).

• Lowercase: I use lowercase letters to denote the elements of a ring instead of uppercase letters as I did in the case of groups. This makes it easier to tell groups and rings apart: As we will see in a moment, the inputs of our linear one-way functions form a ring, whereas the outputs belong to a group. The inputs of the linear one-way functions scale the outputs, and it’s common to write coefficients in lowercase.
• Identities: Since the only rings we are interested in for now consist of integers, it’s convenient to use the integers 0 and 1 to denote the additive and the multiplicative identity.
• Precedence: By convention, multiplication and division are evaluated before addition and subtraction, i.e. \(a \cdot b + a \cdot c\) is to be interpreted as \((a \cdot b) + (a \cdot c)\). (Exponentiation and root extraction have an even higher precedence.)

• \(\mathbb{R}\): This symbol is usually used to denote the set of real numbers. Since we talk only about integers throughout this article, I decided to use this symbol despite this conflict in meaning.

When making a statement about the elements of a set, it is important to indicate whether the statment is true for all elements of the set or just for some elements of the set. In predicate logic, one uses the universal quantifier \(\forall\) (“for all”) for the former and the existential quantifier \(\exists\) (“it exists”) for the latter. The most important rule of inference is universal instantiation: If a statement is true for all elements of a set, it is true for any particular element of the set. The order of quantifiers matters: The identity axiom says that there is at least one element which is an identity for all elements of the set, whereas the invertibility axiom says that for all elements of the set at least one element exists which is an inverse for that particular element.

I stated the group axioms for addition in the ring axioms above in a reduced form. Ignoring for now that the definition of invertibility is ambiguous, it still follows from these reduced group axioms that the right identity is unique and that the right identity is also a left identity (see the last chapter). As far as I can tell, we have to require that the right identity is also a left identity in the case of a monoid in order to ensure that the identity of the monoid is unique. (If there were two distinct identities \(E_1\) and \(E_2\), then \(E_1 = E_1 \circ E_2 = E_2\), which is a contradiction.) Alternatively, we could require that both a left identity and a right identity exist in a monoid. (If there were two distinct left identities \(E_1\) and \(E_2\) and a right identity \(E\), then \(E_1 = E_1 \circ E = E\) and \(E_2 = E_2 \circ E = E\), which contradicts that \(E_1 ≠ E_2\).)

A ring \(\mathbb{S}\) is a subring of another ring \(\mathbb{R}\) if \(\mathbb{S}\) is a subset of \(\mathbb{R}\) and the ring axioms hold for addition and multiplication restricted to \(\mathbb{S}\). Since the modulus \(m\) is part of these operations (it defines what it means to be equivalent), the integers modulo \(m\) have no subrings other than the whole ring because the multiplicative identity \(1\) generates the whole additive group.

The above axioms don’t require that \(0 ≠ 1\). If the additive identity equals the multiplicative identity, all elements in the ring are equal to these identities:

A ring which contains only a single element is a so-called zero ring. Since all zero rings are isomorphic to one another, we speak of the zero ring, denoted as \(\{0\}\). The zero ring is not a subring of any non-zero ring because the additive identity is different from the multiplicative identity in non-zero rings, and a subring must have the same identities as its superring in order to satisfy the axioms for the same operations. We’re not interested in such technicalities, and we will exclude the case where \(0 = 1\) explicitly when defining fields, as it is commonly done.

The statement that each element is either a unit or a zero divisor doesn’t hold for rings with an infinite number of elements. For example, the integers \(\mathbb{Z}\) form a ring under ordinary addition and multiplication. The only elements which have a multiplicative inverse in \(\mathbb{Z}\) are \(+1\) and \(-1\), yet no integer other than \(0\) divides \(0\). A non-zero commutative ring where the product of any two non-zero elements is non-zero (i.e. \(0\) is the only zero divisor), is called an integral domain. Since every element of a finite ring is either a unit or a zero divisor, every finite integral domain is a field. Since we’re interested only in finite algebraic structures, we don’t care about integral domains. I still want to note that the cancellation property holds also for infinite rings: If \(a\) is not a zero divisor, then \(a \cdot b = a \cdot c\) implies that \(b = c\) because \(a \cdot b = a \cdot c\) implies that \(a \cdot b - a \cdot c = a \cdot (b - c) = 0\) and \(b - c\) has to equal \(0\) given that \(a\) is not a zero divisor, which is the case only if \(b = c\).

If an element of a ring has a multiplicative inverse, the multiplicative inverse is unique. For finite rings, this fact follows directly from the argument above. (If \(a\) is a unit, \(f_a\) is a permutation, and thus there is only a single element for which \(f_a(x) = 1\).) It’s not difficult to show that this fact holds for infinite rings as well: After proving that a right inverse is also a left inverse (or simply requiring that the ring is commutative), any two inverses \(a_1^{-1}\) and \(a_2^{-1}\) of \(a\) are the same because \(a_1^{-1} = a_1^{-1} \cdot 1 = a_1^{-1} \cdot (a \cdot a_2^{-1}) = (a_1^{-1} \cdot a) \cdot a_2^{-1} = 1 \cdot a_2^{-1} = a_2^{-1}\).

Given a ring \(\mathbb{R}\), the set of all units in \(\mathbb{R}\) is usually denoted as \(\mathbb{R}^\times\) (or as \(\mathbb{R}^*\)). \(\mathbb{R}^\times\) forms a group under the ring’s multiplication:

• Identity: The multiplicative identity \(1\) is a unit and thus included in \(\mathbb{R}^\times\) because it has a multiplicative inverse, namely itself.
• Invertibility: By definition, every unit has a multiplicative inverse. Since a right inverse is also a left inverse and vice versa, every inverse is itself invertible (i.e. if \(b\) is the inverse of \(a\), then \(a\) is the inverse of \(b\)).
• Closure: The product of two units is another unit because for any \(a, b \in \mathbb{R}^\times\), \((a \cdot b)^{-1} = b^{-1} \cdot a^{-1}\) as \((a \cdot b) \cdot (b^{-1} \cdot a^{-1}) = (a \cdot (b \cdot b^{-1})) \cdot a^{-1} = a \cdot a^{-1} = 1\). (\(a^{-1}\) and \(b^{-1}\) exist because \(a\) and \(b\) are units.)
• Associativity: Since multiplication is the same operation as in the ring, it is still associative.

The notation for the group of units shouldn’t surprise you. I’ve been using it since I introduced multiplicative groups: \(\mathbb{Z}_m\) \(\to\) \(\mathbb{Z}_m^\times\).

A homomorphism is a function which maps the elements of one algebraic structure to the elements of a similar algebraic structure while preserving the relations between the elements in each structure under the operations of the corresponding structure. Unlike an isomorphism, which has to be invertible (see the group isomorphisms above), a homomorphism can map several elements of its domain to a single element of its codomain and doesn’t have to reach all the elements of its codomain. In other words, a homomorphism has to be neither injective) nor surjective, while an isomorphism has to be both in order to be bijective. (Every isomorphism is a homomorphism, but a homomorphism is an isomorphism if and only if it is bijective.)

Given two rings \(\mathbb{R}_1\) and \(\mathbb{R}_2\), a ring homomorphism is a function \(f{:}\ \mathbb{R}_1 \to \mathbb{R}_2\) which satisfies the following properties:

1. Preservation of addition: For all \(a, b \in \mathbb{R}_1\), \(f(a +_1 b) = f(a) +_2 f(b)\).
2. Preservation of multiplication: For all \(a, b \in \mathbb{R}_1\), \(f(a \cdot_1 b) = f(a) \cdot_2 f(b)\).
3. Preservation of the multiplicative identity: \(f(1_1) = 1_2\).

The index indicates to which ring an operation or an identity element belongs. The third property prevents that all elements are mapped to \(0_2\). It follows from these properties that the additive identity and additive and multiplicative inverses are preserved.

The kernel of a homomorphism \(f{:}\ \mathbb{R}_1 \to \mathbb{R}_2\) is the preimage of the additive identity element (or just the identity element in the case of groups): \(\mathbb{K}_f = \{x \in \mathbb{R}_1 \mid f(x) = 0_2 \} = f^{-1}(\{ 0_2 \})\) (see these boxes if you don’t understand these notations). (The kernel is usually written as \(\ker(f)\) or \(\ker f\) instead of \(\mathbb{K}_f\), but I decided to make use of my artistic license again.)

The kernel \(\mathbb{K}_f\) of a homomorphism \(f{:}\ \mathbb{R}_1 \to \mathbb{R}_2\) has some interesting properties:

1. The kernel is a group under addition:
   • Closure: For all \(a, b \in \mathbb{K}_f\), \(a +_1 b \in \mathbb{K}_f\) because \(f(a +_1 b) = f(a) +_2 f(b) = 0_2 +_2 0_2 = 0_2\).
   • Associativity: Inherited from the associativity of addition in \(\mathbb{R}_1\).
   • Identity: \(0_1 \in \mathbb{K}_f \iff f(0_1) = 0_2\) because you can cancel \(f(0_1)\) from \(f(0_1) = f(0_1 +_1 0_1) = f(0_1) +_2 f(0_1)\).
   • Invertibility: For all \(a \in \mathbb{K}_f\), \(-a \in \mathbb{K}_f\) because \(0_2 = f(0_1) = f(a +_1 (-a)) = f(a) +_2 f(-a) = f(-a)\).
2. A homomorphism maps two inputs \(a\) and \(b\) to the same output if and only if they belong to the same coset of its kernel: \(f(a) = f(b) \iff f(a) -_2 f(b) = 0_2 \iff f(a -_1 b) = 0_2 \iff a -_1 b \in \mathbb{K}_f \iff a \in \mathbb{K}_f +_1 b\). Obviously, \(b \in \mathbb{K}_f +_1 b\) because \(0_1 \in \mathbb{K}_f\). (You may have noticed that we’ve already used this fact earlier.)
3. \(f\) is injective if and only if \(\mathbb{K}_f = \{0_1\}\). One direction of this equivalence is trivial to prove: If \(f\) is injective, no two inputs are mapped to the same output, including \(0_2\). If \(f\) is not injective, there are at least two distinct elements \(a, b \in \mathbb{R}_1\) so that \(f(a) = f(b)\). Therefore, \(a -_1 b \in \mathbb{K}_f\) as shown in the previous point. Since \(a ≠ b\), \(a -_1 b ≠ 0_1\), which proves the contraposition of the other direction.

An ideal \(\mathbb{I}\) is a subset of the elements of a ring \(\mathbb{R}\) so that they form a group under addition and that they absorb all the elements of \(\mathbb{R}\) under multiplication, which means that for every \(r \in \mathbb{R}\) and every \(i \in \mathbb{I}\), \(r \cdot i \in \mathbb{I}\). (If the ring is not commutative, one has to distinguish between left ideals and right ideals, whose intersection consists of the two-sided ideals.) Ideals are usually not subrings, as they typically lack the multiplicative identity. For example, given the ring of integers \(\mathbb{Z}\), the set of all the multiples of an integer \(n\), which is commonly written as \(n \mathbb{Z} = \{n \cdot z \mid z \in \mathbb{Z}\}\), is an ideal. This set is closed under addition (the sum of two multiples of \(n\) is another multiple of \(n\)), addition remains associative (the order in which you add multiples of \(n\) doesn’t matter), it has an identity element (\(0\) is a multiple of \(n\) because \(n \cdot 0 = 0\)), and every element has an additive inverse (\((n \cdot z) + (n \cdot (-z)) = n \cdot (z - z) = 0\)). Additionally, if you multiply any multiple of \(n\) by any integer, you get another multiple of \(n\).

The kernel \(\mathbb{K}_f\) of a homomorphism \(f\) is an ideal because the kernel forms a group under addition (see the first property in the previous box) and the kernel absorbs all the elements under multiplication since for all \(r \in \mathbb{R}_1\) and all \(k \in \mathbb{K}_f\), \(r \cdot_1 k \in \mathbb{K}_f\) as \(f(r \cdot_1 k) = f(r) \cdot_2 f(k) = f(r) \cdot_2 0_2 = 0_2\).

A principal ideal is an ideal in a ring \(\mathbb{R}\) which is generated by multiplying a single element \(a\) of \(\mathbb{R}\) by every element of \(\mathbb{R}\). Such a principal ideal is often written as \(a \mathbb{R} = \{a \cdot r \mid r \in \mathbb{R}\}\). If the ring is not commutative, \(a \mathbb{R}\) can be different from \(\mathbb{R} a\). If they are the same, the ideal generated by \(a\) is also written as \(⟨a⟩\) or simply as \((a)\). As we saw earlier when we discussed Bézout’s identity, every linear combination of any two integers \(a\) and \(b\) is a multiple of \(\operatorname{\href{#greatest-common-divisor}{gcd}}(a, b)\). This means that any ideal in the ring of integers \(\mathbb{Z}\) can be generated by a single element, which makes \(\mathbb{Z}\) a so-called principal ideal domain.

Given a ring \(\mathbb{R}\) and a (two-sided) ideal \(\mathbb{I}\) in \(\mathbb{R}\), we can define an equivalence relation \(=_{\mathbb{I}}\) so that for any \(a, b \in \mathbb{R}\), \(a =_{\mathbb{I}} b\) if and only if \(a - b \in \mathbb{I}\). For \(=_{\mathbb{I}}\) to be an equivalence relation, it must satisfy the following properties for any elements \(a\), \(b\), and \(c \in \mathbb{R}\):

• Reflexivity: \(a =_{\mathbb{I}} a\). Since every ideal includes \(0\), \(a - a = 0 \in \mathbb{I}\).
• Symmetry: If \(a =_{\mathbb{I}} b\), then \(b =_{\mathbb{I}} a\). Since the elements of an ideal form an additive group, an ideal contains the additive inverse of each of its elements. Therefore, if \(a - b \in \mathbb{I}\), then \(b - a \href{#inversion-of-combination}{=} -(a - b) \in \mathbb{I}\).
• Transitivity: If \(a =_{\mathbb{I}} b\) and \(b =_{\mathbb{I}} c\), then \(a =_{\mathbb{I}} c\). Since \(a - b \in \mathbb{I}\) and \(b - c \in \mathbb{I}\), \((a - b) + (b - c) = a - c \in \mathbb{I}\) because every ideal is closed under addition (i.e. if \(i \in \mathbb{I}\) and \(j \in \mathbb{I}\), then \(i + j \in \mathbb{I}\), which also means that \(i =_{\mathbb{I}} j\)).

A set of equivalent elements is called an equivalence class. Transitivity implies that any two equivalence classes overlap each other completely or not at all but not partially. Since the elements of both the ring and the ideal form a group under addition, the ideal is an additive subgroup of the ring. Since \(a - b \in \mathbb{I} \iff a \in \mathbb{I} + b\) and \(b \in \mathbb{I} + b\) because \(0 \in \mathbb{I}\), two elements are identical if and only if they belong to the same additive cosets of the ideal. As shown earlier, cosets are either equal or disjoint.

Interestingly, \(=_{\mathbb{I}}\) is also a congruence relation, which means that equivalent inputs result in equivalent outputs under addition and multiplication: Given \(a_1, a_2, b_1, b_2 \in \mathbb{R}\) where \(a_1 =_{\mathbb{I}} a_2\) and \(b_1 =_{\mathbb{I}} b_2\), then

• \(a_1 + b_1 =_{\mathbb{I}} a_2 + b_2\) because \(a_1 - a_2 =_{\mathbb{I}} b_2 - b_1\) as we required that \(a_1 - a_2 \in \mathbb{I}\) and \(b_2 - b_1 \in \mathbb{I}\), and
• \(a_1 \cdot b_1 =_{\mathbb{I}} a_2 \cdot b_2\) because \(a_1 = a_2 + i_a\) for some \(i_a \in \mathbb{I}\) and \(b_1 = b_2 + i_b\) for some \(i_b \in \mathbb{I}\), and thus \(a_1 \cdot b_1 = (a_2 + i_a) \cdot (b_2 + i_b) = a_2 \cdot b_2 + a_2 \cdot i_b + i_a \cdot b_2 + i_a \cdot i_b\). Now \(a_2 \cdot b_2 + a_2 \cdot i_b + i_a \cdot b_2 + i_a \cdot i_b =_{\mathbb{I}} a_2 \cdot b_2\) because \(a_2 \cdot b_2 + a_2 \cdot i_b + i_a \cdot b_2 + i_a \cdot i_b - a_2 \cdot b_2 = a_2 \cdot i_b + i_a \cdot b_2 + i_a \cdot i_b \in \mathbb{I}\) since \(\mathbb{I}\) absorbs multiplication and is closed under addition.

Therefore, addition and multiplication are well-defined for the cosets of \(\mathbb{I}\): No matter which elements from two cosets you add or multiply, all results belong to the same coset. As a consequence, the function \(f(x) = \mathbb{I} + x = \{i + x \mid i \in \mathbb{I}\}\) is a ring homomorphism, where \(\mathbb{I}\) is the additive identity because \(\mathbb{I} + \mathbb{I} = \mathbb{I}\) (closure under addition) and \(a \cdot \mathbb{I} = \mathbb{I}\) for any \(a \in \mathbb{R}\) (absorption of multiplication), and \(\mathbb{I}\) is also the kernel of \(f\) because for all \(i \in \mathbb{I}\) and only those \(i\)s, \(f(i) = \mathbb{I} + i = \mathbb{I}\):

1. Preservation of addition: For all \(a, b \in \mathbb{R}\), \(f(a + b) = \mathbb{I} + (a + b) = \mathbb{I} + \mathbb{I} + (a + b) = (\mathbb{I} + a) + (\mathbb{I} + b) = f(a) + f(b)\).
2. Preservation of multiplication: For all \(a, b \in \mathbb{R}\), \(f(a \cdot b) = \mathbb{I} + (a \cdot b) = \mathbb{I} \cdot \mathbb{I} + \mathbb{I} \cdot b + a \cdot \mathbb{I} + a \cdot b = (\mathbb{I} + a) \cdot (\mathbb{I} + b) = f(a) \cdot f(b)\), where \(\mathbb{A} \cdot \mathbb{B} = \{a \cdot b \mid a \in \mathbb{A}, b \in \mathbb{B} \}\) instead of the Cartesian product of sets.
3. Preservation of the multiplicative identity: \(f(1) = \mathbb{I} + 1\), which is the multiplicative identity because \((\mathbb{I} + a) \cdot (\mathbb{I} + 1) = \mathbb{I} \cdot \mathbb{I} + \mathbb{I} \cdot 1 + a \cdot \mathbb{I} + a \cdot 1 = \mathbb{I} + a\) for any \(a \in \mathbb{R}\).

Since the ideal \(\mathbb{I}\) “divides” (partitions) the ring \(\mathbb{R}\), the ring of cosets is called the quotient ring of \(\mathbb{R}\) modulo \(\mathbb{I}\), written as \(\mathbb{R} / \mathbb{I}\). So not only does a ring homomorphism define a kernel, which is an ideal, an ideal also defines a homomorphism, whose kernel is the ideal itself. A ring homomorphism \(f\) maps all the elements of a coset of \(\mathbb{K}_f\) to a single element because for all \(a \in \mathbb{K}_f + b\), \(f(a) = f(k_a + b) = f(k_a) + f(b) = 0 + f(b) = f(b)\) for some \(k_a \in \mathbb{K}_f\). We thus have an invertible mapping between the cosets of \(\mathbb{K}_f\) and the image of \(f\), which means that the quotient ring of \(\mathbb{R}\) modulo \(\mathbb{K}_f\) is isomorphic to the image \(f(\mathbb{R})\) of \(f\):

This theorem has some interesting edge cases. If the ideal (and thus the kernel) is the ring itself, all elements are mapped to zero, and the quotient ring is isomorphic to the zero ring: \(\mathbb{R} / \mathbb{R} \cong \{0\}\). (This is the case if the multiplicative identity belongs to the ideal.) On the other hand, if the ideal contains only zero, the quotient ring is isomorphic to the ring itself: \(\mathbb{R} / \{0\} \cong \mathbb{R}\).

In the scope of this article, we’re interested only in integers modulo an integer \(m\), where we have \(\mathbb{Z} / m \mathbb{Z} \cong \mathbb{Z}_m\). As noted above, \(m \mathbb{Z}\) is the ideal which consists of all multiples of \(m\). We can visualize what we learned in this box as follows for \(m = 3\):

The ring-related concepts from the previous boxes have group-related equivalents:

Just like an additive subgroup of a ring has to satisfy an additional requirement to be an ideal, a subgroup \(\mathbb{H}\) of a group \(\mathbb{G}\) is a normal subgroup if and only if the left coset \(G \circ \mathbb{H}\) equals the right coset \(\mathbb{H} \circ G\) for all \(G \in \mathbb{G}\). In commutative groups, every subgroup is normal. There’s a great explanation on why we need this condition for non-commutative groups on Stack Exchange. See also this answer on Quora, which introduces conjugacy classes. Both answers use the symmetric group \(\mathrm{S}_3\) as an example.

Examples for infinite fields are the rational numbers \(\mathbb{Q}\), the real numbers \(\mathbb{R}\), and the complex numbers \(\mathbb{C}\).

Given that I quantified the various multiplication axioms over different sets, it’s admittedly not obvious why the non-zero elements of a field form a group under multiplication. Clearly, if associativity, identity, and commutativity hold for all the elements of a field, then they also hold for a subset of them. Since every field is a ring, multiplication by \(0\) always results in \(0\). Therefore, the inverse of a non-zero element is another non-zero element because you wouldn’t get \(1\) otherwise. As we saw above and will prove again below, invertibility implies that there are no non-trivial zero divisors. Consequently, the product of two non-zero elements is another non-zero element, which means that the non-zero elements are closed under multiplication.

Strictly speaking, commutativity of addition is not required as an axiom because it follows from the other axioms.

In the case of integers modulo a prime number \(p\), the additive group is cyclic because the multiplicative identity \(1\) generates the whole group. In the article about coding theory, we will extend these so-called prime fields and see that the additive group of a proper extension field is not cyclic.

The multiplicative group of any field is cyclic: As mentioned but not yet proven earlier, a polynomial of degree \(d > 0\) over any field evaluates to \(0\) for at most \(d\) distinct inputs. If we label the multiplicative group of a field \(\mathbb{F}\) as \(\mathbb{F}^\times\), where \(\mathbb{F}^\times = \href{https://en.wikipedia.org/wiki/Complement_(set_theory)}{\mathbb{F} \setminus \{0\}}\), we have that \(X^{|\mathbb{F}^\times|} = 1\) for all \(X \in \mathbb{F}^\times\) due to Lagrange’s theorem. The exponent of \(\mathbb{F}^\times\) is the smallest positive integer \(n\) so that \(X^n = 1\) for all \(X \in \mathbb{F}^\times\). Since the polynomial \(X^n - 1\) can evaluate to \(0\) for at most \(n\) elements but \(X^n - 1 = 0\) for all \(X \in \mathbb{F}^\times\), \(n\) cannot be smaller than \(|\mathbb{F}^\times|\). As proven earlier, an element of order \(n = |\mathbb{F}^\times|\) exists. Therefore, \(\mathbb{F}^\times\) is cyclic.

The implication operator \(\implies\) is a binary truth function with the following truth table (using \(\top\) for true and \(\bot\) for false):

The technical term for this operation is material implication in order to distinguish it from how we use the term “implication” in everyday language. In logic, implication does not require causation. For example, \(7 \text{ is odd} \implies 3 \text{ is prime}\) is a true statement.

The logical disjunction \(\lor\) (“or”) is true if and only if one of the operands are true (\(\htmlClass{color-green}{\top}\)) instead of false (\(\htmlClass{color-red}{\bot}\)):

In the field of integers modulo a prime \(p\), the only square roots of \(1\) are \(1\) and \(-1\) due to Euclid’s lemma as we saw earlier. Thus:

It would make much more sense to use the term “non-quadratic residue” instead of “quadratic non-residue” for the integers which are not a residue of a square number. Gauss is to blame for this. He’s the one who introduced the terms “quadratic residue” and “quadratic non-residue” (respectively their Latin sources “residua quadratica” and “non-residua quadratica”) in his book Disquisitiones Arithmeticae in 1801. These terms have been used since then, often even without “quadratic” if it’s clear from the context what “residue” and “non-residue” refer to. Furthermore, “nonresidue” is frequently written without a hyphen.

Given the field \(\mathbb{Z}_p\) of integers modulo an odd prime \(p\), we denote its multiplicative group, which consists of all its elements except \(0\), as \(\mathbb{Z}_p^\times\). The squaring function \(f(x) =_p x^2\) is a group homomorphism because \(f(a \cdot b) =_p (a \cdot b)^2 =_p a^2 \cdot b^2 =_p f(a) \cdot f(b)\). As a consequence, the image of this function – the set of quadratic residues — is a subgroup of \(\mathbb{Z}_p^\times\). The kernel \(\mathbb{K}_f\) of this homomorphism is \(\{1, -1\}\). \(f\) maps two inputs \(a\) and \(b\) to the same output if and only if they belong to the same coset \(\mathbb{K}_f\): \(a^2 =_p b^2 \iff a^2 / b^2 =_p 1 \iff (a / b)^2 =_p 1 \iff a / b \in \mathbb{K}_f \iff a \in \mathbb{K}_f \cdot b\). Since \(|\mathbb{K}_f| = 2\) and all cosets are of the same size, always two elements are mapped to the same output, which means that half of all elements are quadratic residues. This is no surprise since we already proved earlier that every element of the function’s image has exactly two preimages.

The following table summarizes what you get when you multiply quadratic residues and non-residues modulo an odd prime \(p\):

Given that multiplication of integers is commutative, there are three cases to analyze:

1. Residue · residue: The set of quadratic residues is closed under multiplication because for any residues \(a^2\) and \(b^2\), their product \(a^2 \cdot b^2 =_p (a \cdot b)^2\) is another quadratic residue. (We already saw in the previous box that the quadratic residues form a subgroup of \(\mathbb{Z}_p^\times\). Since \(1^2 =_p 1\), \(1\) is a residue. And the inverse of a residue is another residue: \((a^2)^{-1} =_p (a^{-1})^2\).)
2. Residue · non-residue: Since \(\mathbb{Z}_p^\times\) is a multiplicative group, the function \(f(x) =_p a \cdot x\) is a permutation for any \(a \in \mathbb{Z}_p^\times\) (i.e. distinct inputs are mapped to distinct outputs). Since we know that exactly half of all elements in \(\mathbb{Z}_p^\times\) are residues and that the product of two residues is another residue, the function \(f(x) =_p b \cdot x\) has to map all non-residues to non-residues for any residue \(b\). If just a single non-residue was mapped to a residue, more than half of all outputs would be residues.
3. Non-residue · non-residue: Since the product of a residue and a non-residue is a non-residue, the function \(f(x) =_p c \cdot x\) has to map all non-residues to residues for any non-residue \(c\). If just a single non-residue was mapped to a non-residue, more than half of all outputs would be non-residues.

The second point can also be proven as follows: Let \(b\) be a residue and \(c\) be a non-residue. If \(b \cdot c\) was a residue, \(b^{-1} \cdot b \cdot c =_p c\) would be a residue according to the first point, which is a contradiction. Therefore, \(b \cdot c\) has to be a non-residue.

The second and the third case can also be derived using our advanced group concepts: Let \(\mathbb{S}_p\) denote the subgroup of quadratic residues modulo the odd prime \(p\), then the quadratic non-residues are a coset of \(\mathbb{S}_p\). Let’s call this coset of non-residues \(\mathbb{T}_p\), then \(\mathbb{S}_p \cdot s = \mathbb{S}_p\) for any \(s \in \mathbb{S}_p\), and \(\mathbb{S}_p \cdot t = \mathbb{T}_p\) for any \(t \in \mathbb{T}_p\). Now \(\mathbb{S}_p\) can also be interpreted as a kernel, where the resulting quotient group \(\mathbb{Z}_p^\times / \mathbb{S}_p\) consists of the elements \(\mathbb{S}_p\) and \(\mathbb{T}_p\), where \(\mathbb{S}_p\) is the identity element and the order of the group is \(2\). Since the order of \(\mathbb{T}_p\) cannot be greater than \(2\), we have \(\mathbb{T}_p \cdot \mathbb{T}_p = \mathbb{S}_p\). This means that \(\mathbb{Z}_p^\times / \mathbb{S}_p \href{#group-isomorphisms}{\cong} \href{#additive-group-notations}{\mathbb{Z}_2^+}\) as groups of prime order are cyclic and cyclic groups are isomorphic to the additive group of the same order.

For the above table to be correct, \(0\) has to be excluded from the set of quadratic residues. Otherwise, a residue times a non-residue can result in a residue because \(0\) times any number is \(0\). |residues| = |non-residues| wouldn’t hold either otherwise.

Since \(p\) is an odd prime, \(\mathbb{Z}_p^\times\) is cyclic and its order is even. In a cyclic group of even order, an element \(A = G^a\) is a quadratic residue if and only if the exponent \(a\) is even, where \(G\) is a generator of the group. The reason for this is that a quadratic residue is of the form \(A = X^2 = (G^x)^2 = G^{2 \cdot x}\). Since the modulus \(p - 1\) of the repetition ring is even, wrapping around cannot make an even exponent odd, i.e. \(2 \cdot x \text{ \href{#modulo-operation}{mod} } p - 1\) is still even. This can be visualized as follows:

If you repeat any element \(p - 1\) times, you get the \(1\). For the elements of the form \(A = X^2\), this is the case already after \(\frac{p - 1}{2}\) repetitions. All other elements need to be squared one more time to get there (i.e. to have an exponent which is a multiple of \(p - 1\)). As explained earlier, the element midway through the cycle is \(-1\).

Adrien-Marie Legendre (1752 − 1833) introduced the following notation for Euler’s criterion, called the Legendre symbol:

Given two integers \(a\) and \(b\), Euler’s criterion of their product equals the product of their Euler’s criteria: \((a \cdot b)^\frac{p - 1}{2} =_p a^\frac{p - 1}{2} \cdot b^\frac{p - 1}{2}\). This makes it much easier to analyze whether the products of residues and non-residues are residues or non-residues.

The Tonelli-Shanks algorithm, named after Alberto Tonelli (1849 − 1920) and Daniel Shanks (1917 − 1996), finds a square root \(x\) of a quadratic residue \(a\) modulo any odd prime \(p\) by repeatedly adjusting an initial guess with the help of any quadratic non-residue \(b\). The best known algorithm for finding a quadratic non-residue is to compute Euler’s criterion for random elements of the field \(\mathbb{Z}_p\) until you find a non-residue. Since half of all elements are non-residues, it takes on average just two attempts to find a non-residue (because this is a geometric distribution with a success probability of \(\frac{1}{2}\)). Since \(p\) is odd, \(p - 1\) is even and can be written as \(2^c \cdot d\), where \(c > 0\) and \(d\) is odd. Given that \(a\) is a quadratic residue and \(b\) is a quadratic non-residue, we have:

We set \(x =_p a^\frac{d + 1}{2}\) initially. At the core of the algorithm is the expression \((x^2 \cdot a^{-1})^{(2^e)}\) with an exponent \(e\). When \(e = c - 1\), the expression evaluates to \((x^2 \cdot a^{-1})^{(2^{c - 1})} =_p ((a^\frac{d + 1}{2})^2 \cdot a^{-1})^{(2^{c - 1})} =_p (a^{d + 1} \cdot a^{-1})^{(2^{c - 1})} =_p (a^d)^{(2^{c - 1})} =_p 1\). Next, we want to decrement \(e\) while making sure that the expression keeps evaluating to \(1\). If we can get \(e\) to \(0\) so that \((x^2 \cdot a^{-1})^{(2^e)} =_p x^2 \cdot a^{-1} =_p 1\), then \(x\) is a square root of \(a\). As explained when we discussed the Miller-Rabin primality test, \(1\) and \(-1\) are the only possible square roots of \(1\) modulo a prime number. If the expression still evaluates to \(1\) for an \(e\) decremented by \(1\), we can keep decrementing \(e\) if \(e\) is still greater than \(0\) without doing anything. If, on the other hand, the expression evaluates to \(-1\) for some \(e < c - 1\), we have to adjust the value of \(x\) to keep the expression at \(1\). You get from \(-1\) to \(1\) with a factor of \(-1\). Since \(x\) is raised to the \(2^{e + 1}\)-th power, we look for a value \(y\) such that \(y^{(2^{e + 1})} =_p -1\). As it turns out, \(y = (b^d)^{(2^{c - e - 2})}\) does the trick (\(c - e - 2 ≥ 0\) because \(e ≤ c - 2\) at this point): \(((b^d)^{(2^{c - e - 2})})^{(2^{e + 1})} =_p (b^d)^{(2^{c - 1})} =_p -1\). Therefore, multiplying \(x\) by \((b^d)^{(2^{c - e - 2})}\) brings the expression back to \(1\), thereby maintaining our loop invariant. If we haven’t reached \(e = 0\), we decrement \(e\) again.

The following tool implements the Tonelli-Shanks algorithm for arbitrarily large numbers. To make the output deterministic, it searches for a quadratic non-residue in the natural order of the field’s elements. In an adversarial context, this can affect the performance of the algorithm negatively. If \(c = 1\), \(e = c - 1 = 0\) immediately, which means that the initial \(x\) is the final \(x\), and thus the search for a quadratic non-residue can be skipped. The tool displays the adjusted \(x\) only in the next row. If the value in the third column is \(1\) (in green), the same \(x\) is used in the next row and the value in the last column is ignored (in gray). I included the ignored values in the last column anyway so that you can see that the last column does not depend on the input \(a\) and that it’s easier to observe that each value in the last column is the square of the value above it. When you step through the quadratic residues of the field with the buttons next to the input \(a\), you’ll see that \(x\) sometimes has to be adjusted in every step and other times not at all. The algorithm presented here can be optimized in several ways. For example, computing the multiplicative inverse of \(a\) can be avoided (see Wikipedia), but I think my version of the algorithm is the easiest one to understand.

Given an integer \(a\) and a composite modulus \(m\), how can we compute an \(x\) so that \(x^2 =_m a\)? If we know the prime factorization \(\prod_{i=1}^l p_i^{e_i}\) of \(m\), we can determine a square root modulo each of the factors since \(\mathbb{Z}_m \cong \mathbb{Z}_{p_1^{e_1}} \times … \times \mathbb{Z}_{p_l^{e_l}}\), and then use the Chinese remainder theorem to revert the isomorphism. If we don’t know the prime factorization of \(m\), determining whether \(a\) is a quadratic residue modulo \(m\) and computing square roots modulo \(m\) is generally (but not always) as difficult as factorizing \(m\). This fact is used in some cryptosystems. So far, we have discussed only how to compute a square modulo an odd prime \(p\). Modulo a prime power \(p^e\) for some integer \(e ≥ 1\), there are several cases to consider, which I derived mostly myself:

• \(a =_{p^e} 0\): \(x =_{p^e} cp^d\), where \(d = \lceil \frac{e}{2} \rceil\) and \(c \in \{0, 1, …, p^{e - d} - 1\}\).
• \(a =_{p^e} p^b\) for some integer \(b ≥ 1\): If \(b\) is even, \(x =_{p^e} ±(p^{b / 2} + cp^d)\), where \(d = \operatorname{max}(\lceil \frac{e}{2} \rceil, e - \frac{b}{2} - (1 - p\ \href{#modulo-operation}{\%}\ 2))\) and \(c \in \{0, 1, …, p^{e - d} - 1\}\), because \(x^2 =_{p^e} (p^{b / 2} + cp^d)^2 =_{p^e} p^b + 2 c p^{b/2 + d} + c^2 p^{2d} =_{p^e} a\) due to the previous choice of \(d\). Otherwise, there are no square roots because \(p^b =_{p^e} x^2 \iff p^b + tp^e = p^b(1 + tp^{e-b}) = x^2\) for some integer \(t\). As the prime factorization of an integer is unique, an integer has an integer square root if and only if every exponent of its prime factorization is even. Since \(1 + tp^{e-b}\) is not a multiple of \(p\) (it is one off from a multiple of \(p\)), its prime factors don’t include \(p\), which leaves us with the odd exponent \(b\) for the prime factor \(p\). Thus, \(p^b(1 + tp^{e-b})\) has no square roots among the integers.
• \(\operatorname{\href{#greatest-common-divisor}{gcd}}(a, p^e) = 0\):
  • \(p\) is odd: As we saw earlier, the multiplicative group modulo a power of an odd prime is cyclic, and Euler’s criterion can be generalized to any cyclic multiplicative group by replacing \(p - 1\) with \(\href{#eulers-totient-function}{\varphi}(p^e)\) in this box. With the same replacement, you can also generalize the Tonelli-Shanks algorithm to any cyclic multiplicative group. Alternatively, you can “lift” a solution modulo \(p^{e-1}\) to modulo \(p^e\) (recursively starting from \(p^1\)) as explained in section 12.5.2 of Victor Shoup’s book.
  • \(p\) is even (i.e. \(p = 2\)): This case is almost always ignored, and the only algorithm I’ve found had no explanation. Fortunately, we can derive an algorithm for powers of 2 with the following observations:
    1. If \(x^2 =_{p^e} a\) (i.e. \(x^2 - a\) is a multiple of \(p^e\)), then \(x^2 =_{p^d} a\) for some positive integer \(d ≤ e\) because any multiple of \(p^e\) is also a multiple of \(p^d\).
    2. Whenever \(x^2 =_{p^e} a\), \(-x\) is also a solution because \((-x)^2 \href{#multiplication-by-minus-one}{=} ((-1)x)^2 = (-1)^2x^2 \href{#multiplication-by-minus-one}{=} (-(-1))x^2 \href{#double-inverse-theorem}{=} x^2\).
    3. Whenever \(x^2 =_{2^e} a\), \(x + 2^{e-1}\) is also a solution because \((x + 2^{e-1})^2 =_{2^e} x^2 + 2x2^{e-1} + 2^{2(e-1)} =_{2^e} x^2\).
    4. If \(e ≥ 3\), \(x^2 =_{2^e} 1\) has exactly four solutions, namely \(1\), \(1 + 2^{e-1}\), \(-1\), and \(-(1 + 2^{e-1}) =_{2^e} -1 + 2^{e-1}\), as \(-2^{e-1} =_{2^e} 2^{e-1}\). Since \(x^2 - 1 = (x + 1)(x - 1)\) is a multiple of \(2^e\) and \((x + 1) - (x - 1) = 2\), both \(x + 1\) and \(x - 1\) are even (if they both were odd, their product couldn’t be a multiple of \(2^e\)), and one of them is not a multiple of \(4\). Consequently, the other one has to be a multiple of \(2^{e-1}\) for their product to be a multiple of \(2^e\). Since the only multiples of \(2^{e-1}\) modulo \(2^e\) are \(0\) and \(2^{e-1}\), \(x\) has to be next to them, which gives us the four aforementioned solutions.
    5. In the case of \(e = 3\), the solutions of \(x^2 =_8 1\) are \(1\), \(3\), \(5\), and \(7\) according to the previous point, which you can verify with the repetition table of multiplicative groups. As you can also see, \(3\), \(5\), and \(7\) have no square roots modulo \(8\).
    6. Combined with the first observation, \(x^2 =_{2^e} a\) for some \(e ≥ 3\) has no solutions if \(a\) is odd and \(a\ \%\ 8 ≠ 1\).
    7. The integers which are coprime with the modulus (i.e. all odd integers in the case of \(m = 2^e\)) form a multiplicative group. As we saw earlier, the power function (squaring in this case) is a homomorphism. As explained in the fourth observation, the size of its kernel is \(4\). Since a homomorphism maps two inputs to the same output if and only if they belong to the same coset of its kernel, an odd \(a\) has either four square roots or none modulo \(2^e\) for some \(e ≥ 3\) since all cosets contain the same number of elements as the kernel. Given a solution \(x\), you obtain the other solutions by multiplying \(x\) with each element of the kernel. Since the odd integer \(x\) can be written as \(1 + b \cdot 2\) for some integer \(b\), \(x(1 + 2^{e-1}) =_{2^e} x + (1 + b \cdot 2)2^{e-1} =_{2^e} x + 2^{e-1} + b \cdot 2^e =_{2^e} x + 2^{e-1}\), which matches our third observation.
    8. The four solutions \(x\), \(x + 2^e\), \(-x\), and \(-x + 2^e\) to \(x^2 =_{2^{e+1}} a\) for an odd \(a\) and some \(e ≥ 3\) are also solutions to \(x^2 =_{2^e} a\) according to the first observation. In this case, however, \(x + 2^e =_{2^e} x\) and \(-x + 2^e =_{2^e} -x\), which means that the four solutions modulo \(2^{e+1}\) map to two of the four solutions modulo \(2^e\). Moreover, either \(x\) or \(x + 2^e\) modulo \(2^{e+1}\) is already between \(0\) and \(2^e\), which means that one element stays the same when the two halves are mapped to one half by computing modulo \(2^e\). The same is true for \(-x\) and \(-x + 2^e\) as well, which we can depict as follows:
    9. Given a solution \(x\) to \(x^2 =_{2^e} a\), either \(x\) or \(x + 2^{e-1}\) is also a solution to \(x^2 =_{2^{e+1}} a\) because the two solutions which \(x^2 =_{2^e} a\) and \(x^2 =_{2^{e+1}} a\) have in common differ in their sign and not by \(2^{e-1}\) according to the previous point.

       	$$±2^{e-1}$$
       $$\cdot (-1)$$	$$x$$	$$x + 2^{e-1}$$
       	$$-x$$	$$-x + 2^{e-1}$$

    These observations result in the following algorithm: Since \(\operatorname{gcd}(a, 2^e) = 0\) in this branch, \(a\) and any solution \(x\) are odd. If \(e = 1\), return \(\{1\}\). If \(e = 2\), return \(\{1, 3\}\) if \(a =_4 1\) and \(\{\}\) otherwise. (There are only two solutions in this case because \(x + 2 =_4 -x\) for \(x \in \{1, 3\}\).) If \(a\ \%\ 8 ≠ 1\), return \(\{\}\). Set \(x := 1\). For \(i\) from \(3\) to \(e - 1\), add \(2^{i-1}\) to \(x\) if \(x^2 ≠_{2^{i+1}} a\). Return \(\{x, 2^{e-1} - x, 2^{e-1} + x, 2^e - x\}\).

• \(\operatorname{gcd}(a, p^e) = p^b\) for some integer \(b ≥ 1\): This means that \(a =_{p^e} p^bc\) for some integer \(c\), where \(\operatorname{gcd}(c, p^e) = 0\). You get the solutions by multiplying each solution \(x_1\) to \(x^2 =_{p^e} p^b\) with each solution \(x_2\) to \(x^2 =_{p^e} c\). You find the solutions to these subproblems according to the previous two cases. Please note that these products are not all different from one another. Clearly, all these products are solutions to \(x^2 =_{p^e} a\) because \((x_1x_2)^2 =_{p^e} x_1^2x_2^2 =_{p^e} p^bc =_{p^e} a\). It’s less obvious why these are the only solutions. Since \(p^bc =_{p^e} x^2 \iff p^bc + tp^e = p^b(c + tp^{e-b}) = x^2\) for some integer \(t\) and \(c + tp^{e-b}\) is not a multiple of \(p\) because \(c\) isn’t a multiple of \(p\), the prime factorization of \(x\) has to include \(p\) with an exponent of \(\frac{b}{2}\). But as noted in the second case, solutions to \(x^2 =_{p^e} p^b\) can be shifted by multiples of \(p^d\). The other prime factors are determined by \(c + tp^{e-b} = x^2 \iff c =_{p^{e-b}} x^2\), which means that you can use the solutions to \(x^2 =_{p^{e-b}} c\) instead of the solutions to \(x^2 =_{p^e} c\).

The following tool computes the square roots of the given input modulo the specified composite integer as described above:

In the previous box, we saw how the square roots modulo a composite number can be computed efficiently if the prime factorization of the modulus is known. This means that an efficient algorithm for factorizing integers would lead to an efficient algorithm for computing the square roots modulo a composite number. In this box, we show that the opposite is also true: An efficient algorithm for computing the square roots modulo a composite number would lead to an efficient algorithm for factorizing integers. Being able to reduce each of these two problems to the other one efficiently (i.e. in polynomial time) implies that these two problems are of similar computational complexity. Since no efficient algorithm is known for either of these two problems, both problems are believed to be difficult to solve for large inputs.

For the sake of simplicity, we assume that the number \(n\), which we want to factorize, is the product of two odd primes \(p\) and \(q\) (i.e. \(n = p \cdot q\)). Since there are two solutions to \(x^2 =_p a\) and two solutions to \(x^2 =_q a\) as proven earlier, there are four solutions to \(x^2 =_n a\) because \(\mathbb{Z}_n \cong \mathbb{Z}_p \times \mathbb{Z}_q\). (Two of the solutions are the additive inverses of the other two.) Since we haven’t specified whether the algorithm has to find one square root of the given input \(a\) or all of them, there are two possibilities to consider:

• The efficient algorithm for computing square roots modulo a composite number returns all four solutions: Compute the four square roots of an arbitrary quadratic residue \(a\), such as \(1\). Choose distinct \(x\) and \(y\) from the four square roots so that \(x ≠_n -y\). Since \(x^2 =_n y^2 =_n a\), \(x^2 - y^2 = (x + y)(x - y)\) is a multiple of \(n\). However, \(n\) divides neither \(x + y\) (as \(x ≠_n -y\)) nor \(x - y\) (as \(x ≠_n y\)), which means that \(p\) has to divide one of the factors and \(q\) the other. (If the prime factorization of one of these factors contained both \(p\) and \(q\), \(n\) would divide this factor.) Therefore, \(\operatorname{gcd}(x ± y, n)\), which can be computed efficiently with the Euclidean algorithm, equals either \(p\) or \(q\), which means that we have successfully factorized \(n\).
• The efficient algorithm for computing square roots modulo a composite number returns just one pair of solutions: Choose a random \(x\) between \(0\) and \(n\), and compute \(a =_n x^2\). By feeding this value \(a\) into the square-root-finding algorithm, you get a value \(y\) so that \(y^2 =_n a\). Since the value \(x\) has been chosen randomly, the chance that \(y =_n ±x\) is exactly 50%. If \(y =_n ±x\), you repeat the process for another randomly chosen \(x\) until \(x ≠_n ±y\). Now again, \(\operatorname{gcd}(x ± y, n)\) equals either \(p\) or \(q\).

For the group operation to be well defined (see the next section), the curve has to be smooth, which means every point on the curve has a unique tangent. An elliptic curve is smooth (non-singular) if it has no cusps and does not intersect itself. This is the case if and only if the polynomial on the right-hand side of the equation has no repeated roots, which is the case if and only if its discriminant \(-4a^3 - 27b^2\) is not zero. Let’s look at two examples, where this is not the case:

You may have noticed that the above equation defining elliptic curves misses the \(x^2\) term. The reason for this is that a cubic polynomial of the form \(c(z) = sz^3 + tz^2 + uz + v\) can be turned into a so-called depressed cubic of the form \(d(x) = x^3 + ax + b\) by replacing \(z\) with \(x - \frac{t}{3s}\), thereby shifting the input, which means \(c(x - \frac{t}{3s}) = d(x) \iff c(z) = d(z + \frac{t}{3s})\):

In order to get the promised form, we need to divide the polynomial by \(s\), thereby scaling the output. Therefore, we have:

This change of variable doesn’t work if the polynomial is defined over a finite field whose so-called characteristic is \(3\) because in this case, \(3s = 0\), and we cannot divide by \(0\). In the case of elliptic curves, there are even more terms to consider, such as \(xy\), which you cannot get rid of if the characteristic of the underlying field is \(2\). As you can see, things become complicated quickly.

In order to form a group, point addition has to be associative, i.e. for any points \(A\), \(B\), and \(C\), it has to be that \((A + B) + C = A + (B + C)\). Unfortunately, it’s rather difficult to prove that this is always the case. You find explanations for this fact here and here. I’ll just visualize what associativity means geometrically:

As explained above, a point is at an intersection of an elliptic curve and a straight line if and only if its \(x\)-coordinate satisfies \(x^3 - s^2x^2 + (a - 2st)x + b - t^2 = 0\). The left-hand side of this equation is a cubic function, which crosses the \(x\) axis at least once because it is continuous and goes from \(\href{https://en.wikipedia.org/wiki/Limit_(mathematics)}{f(-\infin)} = \href{https://en.wikipedia.org/wiki/Infinity_symbol}{-\infin}\) to \(f(\infin) = \infin\) or vice versa. This can be visualized as follows:

The cubic function \(x^3 + x^2 + x + 1\) has only a single root because its factor \(x^2 + 1\) has no roots among the real numbers (but \(i\) and \(-i\) among the complex numbers). Other cubic functions cross the \(x\) axis three times, which is apparent from their factors:

Instead of crossing the \(x\) axis again, a cubic function, such as \(x^3 - x^2 - x + 1\), can just “touch” the \(x\) axis (at \((1, 0)\) in this case):

As you can see from its factors, the root at \(x = 1\) has a multiplicity of \(2\). This has to be the case because when you factor out two roots from a polynomial of degree \(3\), you’re left with a polynomial of degree \(1\), which always has a root. Therefore, a cubic function has either one or three real roots, which don’t have to be distinct. Since point addition involves two points (roots), you’re guaranteed to find a third point (root) on the same line, where a point of tangency is simply counted twice.

If we didn’t reflect the third intersection across the \(x\) axis, we would have \(A + B = C\), \(A + C = B\), and \(B + C = A\) because the collinearity of the three points is symmetric (i.e. if \(C\) lies on the same line as \(A\) and \(B\), \(B\) lies on the same line as \(A\) and \(C\)):

By inserting the value of \(B\) from the second equation into the first equation, we would get \(A + (A + C) = C\). Assuming that point addition forms a group (this is our goal after all), \(A + A\) would have to equal the identity element. Since \(A\) is an arbitrary point on the elliptic curve, every point on the curve would have an order of \(2\), which is not what we want. We can see this more directly by repeating an element \(D\). If \(D + D\) equaled \(E\), we would get back to \(D\) by adding \(D\) again, i.e. \(E + D = D\):

This would make any such point \(E\) an identity element, which contradicts the uniqueness of the identity element in a group. Moreover, the modified operation would not be associative, which can be seen on the basis of the following counterexample:

Now let’s go back to the three collinear points \(A\), \(B\), and \(C\) at the beginning of this box. If \(A + B = C\) and \(A + C = B\), then \(A + B - C = A - B + C\), which works only if each element is its own inverse. If, on the other hand, \(A + B = -C\) and \(A + C = -B\), which corresponds to the actual point addition above, we get the same expression in both cases, namely \(A + B + C = O\), where \(O\) is the identity element, which we’ll discuss next.

An elliptic curve separates into two components if its discriminant \(-4a^3 - 27b^2\) is positive:

We can combine the various cases of point addition into the following pseudocode, but make sure to read the warnings below:

While this code works and is exactly how I implemented point addition for the tools in this chapter, you should not use it for cryptographic purposes. In order to avoid timing attacks, cryptographic algorithms should run in constant time, i.e. perform the same operations no matter the inputs. How to achieve this is beyond the scope of this article. Common techniques include using homogeneous/projective coordinates instead of Cartesian coordinates and working with (twisted) Edwards curves, named after Harold Mortimer Edwards (1936 − 2020), instead of curves in Weierstrass form. The advantages of Edwards curves are that the formulas for addition and doubling are the same and that the identity element is an ordinary point.

The elements of an elliptic-curve group are \(\{ (x, y) \in \href{https://en.wikipedia.org/wiki/Cartesian_product}{\mathbb{F} \times \mathbb{F}} \mid y^2 = x^3 + a \cdot x + b \href{#logical-conjunction}{\land} 4a^3 + 27b^2 ≠ 0 \} \cup \{ O \}\). In order to determine the group’s order, we have to count the points on the elliptic curve. A naive approach of doing so is to determine for each possible \(x\) whether \(x^3 + a \cdot x + b\) is a quadratic residue. If this is the case, you increase your counter by \(2\). If \(x^3 + a \cdot x + b = 0\), you increase your counter by \(1\). However, this approach is computationally infeasible for the large finite fields that we need in elliptic-curve cryptography. René Schoof (born in 1955) published an efficient algorithm for counting the points on elliptic curves over finite fields in 1985. Unfortunately, his algorithm is too complicated for this introductory article.

Bitcoin, Ethereum, and many other cryptocurrencies use an elliptic curve called secp256k1 in their signature algorithm, which is defined in Standards for Efficient Cryptography (SEC) by the Standards for Efficient Cryptography Group (SECG). The letter p indicates that the curve is defined over a prime field. It is followed by the length of the prime \(p\) in bits. The letter k stands for Koblitz curve, named after Neal Koblitz (born in 1948), which allows for especially efficient implementations. The 1 at the end is just a sequence number. secp256k1 has the following curve parameters in hexadecimal notation (see section 2.4.1 on page 9):

• \(p =\) FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F \(= 2^{256} - 2^{32} - 2^{9} - 2^{8} - 2^{7} - 2^{6} - 2^{4} - 1\) (The proximity to \(2^{256}\) allows for faster implementations of the modulo operation.)

• \(a = 0\)

• \(b = 7\)

• \(G =\) (79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798, 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8)
• \(n =\) FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

• \(h = 1\)

You can click on the hexadecimal numbers to convert them to decimal numbers with the tool in the next box. You can verify with the Miller-Rabin primality test that \(p\) is indeed prime. Given the above \(a\) and \(b\), the curve equation is \(y^2 =_p x^3 + 7\). While counting the points on elliptic curves is complicated, you can verify with the point calculator above that \(nG = O\) (the tool also recovers the \(y\)-coordinate of \(G\) correctly). Since \(p\ \%\ 4 = 3\), computing square roots modulo \(p\) is simple. Since \(n\) is prime and \(G\) is not the point at infinity, the order of \(G\) cannot be smaller than \(n\). Since the cofactor is \(1\), \(G\) generates all points on the elliptic curve. Since \(n\) is prime, every element except \(O\) is a generator. And since \(n\) is odd, we know that the curve has no point with a \(y\)-coordinate of \(0\).

The following tools converts the given integer to the decimal and the hexadecimal numeral system in the preferred formatting:

The above tool shares its state with the other tools in this chapter. Since some algorithms for solving the discrete-logarithm problem work only if the order of the generator is known, we have to determine it even in the tools that don’t need it. In order to determine the order of an element, you have to know the prime factorization of the group’s order, which is itself not always easy to determine. Hence, the tools in this chapter have the following limitations:

• Multiplicative groups: In order to determine the order of a multiplicative group, we have to evaluate Euler’s totient function for its modulus \(m\), which requires the prime factorization of \(m\). If \(m\) isn’t prime, the tools in this chapter perform up to 100’000 rounds of Pollard’s rho factorization algorithm, which is usually enough to factorize the product of two 35-bit primes, i.e. numbers with up to 21 decimal digits. If successful, it performs at most another 100’000 rounds of the same algorithm to factorize the group’s order. If either of these factorizations fail, you have to enter the order of \(G\) yourself, which gives you the option of choosing the modulus in a smart way. If you just want to know the result of a modular exponentiation, you can use the calculator for rings above, which doesn’t have this limitation.
• Elliptic curves: Since I didn’t implement Schoof’s algorithm, the tool counts the number of points only for elliptic curves whose modulus \(p\) is smaller than 100’000. Once the order of the group has been determined, it also performs up to 100’000 rounds of Pollard’s rho factorization algorithm in order to determine the order of \(G\). If \(p\) > 100’000 or the factorization fails, you have to enter the order of \(G\) yourself, which you can determine with SageMath as explained in the next box. If you just want to know the result of a point multiplication, you can use the point calculator above, which doesn’t have this limitation.

SageMath is an open-source software library for mathematics. You can use its playground for many things, which includes computations on elliptic curves over finite fields (see the documentation of cardinality, order, lift_x, and plot):

The tools in this chapter don’t require that \(G\) generates the whole group. In the case of multiplicative groups, it can be desirable for \(G\) to generate just a subgroup so that its order can be prime (as mentioned earlier) and that the size of cryptographic keys and signatures can be smaller (as explained later). Moreover, some cryptosystems, such as RSA, use non-cyclic groups, which have no generators. If \(G\) doesn’t generate the whole group, you can set the output \(K\) to an element which isn’t in the subgroup generated by \(G\). While subgroup membership can be tested easily in cyclic groups, I didn’t implement this check because there is no simple formula to determine whether an elliptic curve is cyclic and I had to handle failures anyway for non-cyclic groups.

How can we solve an equation of the form \(a \cdot x =_m c\) for \(x\)? If \(a\) has a multiplicative inverse modulo \(m\), \(x =_m c \cdot a^{-1}\). If \(a\) has no multiplicative inverse, \(a \cdot x =_m c\) has \(d = \operatorname{\href{#greatest-common-divisor}{gcd}}(a, m)\) solutions in \(\mathbb{Z}_m\) if \(c\) is a multiple of \(d\) and no solution otherwise as we saw earlier. Using the extended Euclidean algorithm, we can find integers \(b\) and \(n\) so that \(d = a \cdot b + m \cdot n\). After multiplying both sides by \(c / d\), we get \(c = a \cdot (b \cdot c / d) + m \cdot (n \cdot c / d)\). Modulo \(m\), we have \(a \cdot (b \cdot c / d) =_m c\), which means that \(x =_m b \cdot c / d\) is a solution to \(a \cdot x =_m c\). Since the \(d\) solutions are equally apart, we get the other \(d - 1\) solutions by adding multiples of the offset \(o = m / d\) to \(x\). The following tool does all of that for you:

The birthday paradox denotes the counterintuitive fact that in a group of 23 people, it’s likelier than not that at least two of them have the same birthday. Since we’re not interested in birthdays, we analyze this problem more generally: When we put \(i\) items randomly into \(n\) buckets, how likely is it that at least one bucket contains at least two items? If \(i > n\), the probability of this happening is \(1\) according to the pigeonhole principle. If \(i ≤ n\), we first analyze the probability \(\overline{P}(i, n)\) that this is not happening, i.e. the probability that all buckets contain at most one item. The probability that the first item lands in an empty bucket is \(1\). For the second item, \(n - 1\) of the \(n\) buckets are still empty. The probability of landing in one of those is \(\frac{n - 1}{n}\). Thus:

The probability that at least one bucket contains at least two items is then \(P(i, n) = 1 - \overline{P}(i, n)\). Applied to the birthday paradox, we have \(P(23, 365) = 1 - 365! / (365^{23}(365 - 23)!) = \href{https://www.wolframalpha.com/input?i=1-365%21%2F%28365%5E23*%28365-23%29%21%29}{0.5073}\). So how is this related to Pollard’s rho algorithm? If the function \(f(S_i)\) gives us a random element in the subgroup generated by \(G\) of order \(n\), \(P(i, n)\) describes how likely it is that \(f\) returned at least one element twice after \(i\) invocations. Unlike the birthday paradox, we’re not interested in the median but rather in the expected number of iterations \(E(n)\) until we obtain an element twice. The expected value of a random variable is determined as the sum of each possible outcome multiplied by the probability of this outcome. The first possible outcome is that we get a repetition in the second iteration. The probability that we get the element from the first iteration again in the second iteration is \(\frac{1}{n}\). The probability that we get the first repetition in the third iteration is the probability that we don’t get a repetition in the second iteration (\(\frac{n - 1}{n}\)) times the probability that we get one of the first two elements in the third iteration (\(\frac{2}{n}\)). The probability that we sample \(n\) different elements and get the repetition only in the \((n + 1)\)th iteration is \(\frac{(n-1)!}{n^{n-1}} = \frac{n!}{n^n}\). Thus:

This formula determines the colored area of the following outcome × probability table by adding up the area of each column:

We can simplify \(E(n)\) by summing over the rows instead of the columns. After the first iteration, the probability that we need at least one more iteration is \(1\). After the second iteration, the probability that we didn’t get a repetition and thus need more iterations is \(\frac{n - 1}{n}\). After the third iteration, we have to multiply this probability times the probability that the third element wasn’t one of the first two: \(\frac{n - 1}{n} \cdot \frac{n - 2}{n}\). This gives us the following formula \(Q(n)\) for the blue area in the above graphic:

By adding \(1\) for the green area, we have \(E(n) = 1 + Q(n)\). To approximate the value of \(Q(n)\), we need another formula \(R(n)\):

For sufficiently large \(n\), \(Q(n) \approx R(n)\) because the difference between \(\frac{n - 1}{n}\) and \(\frac{n}{n + 1}\) gets smaller and smaller as \(n\) gets larger, and the addends from \(i = n + 1\) to \(\infty\) get vanishingly small as they are the product of lots of numbers smaller than \(1\). Using the Taylor series, named after Brook Taylor (1685 − 1731), of the exponential function (i.e. \(e^n = \sum_{i=0}^{\infty} \frac{n^i}{i!}\)) and Stirling’s formula, named after James Stirling (1692 − 1770), to approximate factorials (i.e. \(n! \approx \sqrt{2 \pi n}\frac{n^n}{\mathrm{e}^n}\)), we get:

Therefore, \(Q(n) \approx \frac{1}{2} \sqrt{2 \pi n} = \sqrt{\frac{\pi}{2} n} \approx 1.25 \sqrt{n}\) since \(\frac{1}{2} = \sqrt{\frac{1}{4}}\), which means that it takes in the order of \(\sqrt{n}\) iterations until you get a repetition when randomly sampling from \(n\) elements. The functions \(Q(n)\) and \(R(n)\) were introduced for this analysis by Donald Ervin Knuth (born in 1938) in section 1.2.11.3 in the first volume of his book The Art of Computer Programming.

While the function \(f(S_i)\) used by Pollard’s rho algorithm isn’t random, it is random enough for \(\sqrt{n}\) to be a really good estimate for how many steps are needed. In order to make it easier for you to judge this, the tool above displays the number of steps that it took to find a repetition at the top and the square root (sqrt) of \(G\)’s order \(n\) below the problem statement. The above graphic depicting \(\rho\) showed only the elements in the sequence defined by the starting element and \(f(S_i)\). However, \(f(S_i)\) maps any of the \(n\) elements to a somewhat random other element. No matter where you start, you get a first repetition and thus a cycle after around \(1.25 \sqrt{n}\) steps on average. The complete picture looks like this:

We can apply the same idea to integer factorization. Confusingly, this algorithm is also called Pollard’s rho algorithm. Given a composite number \(n\) and a divisor \(d\) of \(n\), we can use the function \(f(x) =_d x^2 + 1\) to define a sequence of integers \(s_i\), where \(s_{i+1} = f(s_i)\). Since we compute \(f(x)\) modulo \(d\), this function evaluates to at most \(d\) different values. If the sequence generated by \(f(x)\) is random enough, it revisits an already visited integer after around \(\sqrt{d}\) iterations on average as we saw in the previous box. We can use Floyd’s cycle-finding algorithm to find two integers \(a\) and \(b\) so that \(a =_d b\). If \(a - b\) is a multiple of \(d\), then so is \(\operatorname{\href{#greatest-common-divisor}{gcd}}(n, \lvert a - b \rvert)\) because \(d\) is a factor of \(n\). Now the problem is that we don’t know \(d\), otherwise we would have already found a factorization of \(n\). Instead of computing \(f(x)\) modulo \(d\) and checking whether \(a =_d b\), we can compute \(x^2 + 1\) modulo \(n\) and check whether \(\operatorname{gcd}(n, \lvert a - b \rvert) > 1\). Since we don’t have to reduce \(f(x)\) modulo any integer and the former condition still implies the latter, the latter algorithm takes at most as many iterations of Floyd’s cycle-finding algorithm as the former. If \(\operatorname{gcd}(n, \lvert a - b \rvert) > 1\) and \(a ≠_n b\), \(\operatorname{gcd}(n, \lvert a - b \rvert)\) is a non-trivial divisor of \(n\). Since this algorithm no longer depends on \(d\) and the above reasoning applies to all divisors of \(n\), the number of iterations it takes to find a factor of \(n\) is expected to be around the square root of the smallest prime factor of \(n\). We can implement Pollard’s rho algorithm in pseudocode as follows:

Usually, this algorithm finds the smallest prime factors of \(n\) first, but the returned \(d\) can be any divisor of \(n\) and doesn’t have to be prime. If you want to find the prime factorization of \(n\), you recursively factorize \(d\) and \(\frac{n}{d}\) until all factors are prime, which you can test efficiently with a probabilistic primality test, such as the Miller-Rabin primality test. If \(a =_n b\), \(\operatorname{gcd}(n, \lvert a - b \rvert) = n\), and the algorithm fails. In this case, you can increment the offset \(o\) in the function \(f(x)\) and try again. If the input \(n = 4\), neither incrementing \(o\) nor starting from a different value makes the algorithm succeed. For this reason, it’s common to halve the input \(n\) until it is odd and then to run Pollard’s rho factorization algorithm from there.

Pollard’s rho factorization algorithm can be optimized in the following two ways:

• Use Brent’s cycle-finding algorithm, named after Richard Peirce Brent (born in 1946): Instead of moving both the tortoise and the hare along the sequence in each iteration, you move only the hare one step ahead, replacing three evaluations of \(f(x)\) with one. After every power of \(2\) steps, you set the tortoise to the current value of the hare. The tortoise then acts as a waypoint so that it can stop the hare when it passes by. While Brent’s cycle-finding algorithm evaluates \(f(x)\) as often as Floyd’s one does in the worst case, Brent showed that his algorithm requires 36% fewer evaluations of \(f(x)\) on average.
• Combine several differences before running the Euclidean algorithm: Instead of computing the greatest common divisor in every iteration, you compute the product of the differences \(\lvert a - b \rvert\) modulo \(n\) over several iterations and run the Euclidean algorithm only once in a while. This works because if \(\operatorname{gcd}(n, x) > 1\), then \(\operatorname{gcd}(n, x \cdot y) > 1\) for any integers \(x\) and \(y\).

The following tool implements Pollard’s rho factorization algorithm. Unlike my implementation of trial division above, it checks whether the remaining factor is prime. Its running time is thus in the order of the square root of the second largest prime factor if the exponent of the largest prime factor is \(1\). (It’s possible to test for perfect powers efficiently as explained in the note 3.6 in the Handbook of Applied Cryptography and on Wikipedia; I just didn’t implement this because you rarely encounter them.)

Before you rely on a multiplicative group which was provided by someone else to be a linear one-way function, you have to verify that the group’s order has a sufficiently large prime factor. If the group’s order or its prime factorization is not known to you (because they aren’t provided to you or you can’t determine them), you shouldn’t use the group. Otherwise, an attacker can choose the modulus \(m\) as the product of two large primes \(p\) and \(q\), where both \(p - 1\) and \(q - 1\) have only relatively small prime factors. Since it’s difficult to factorize such a modulus \(m\), only the attacker can determine the group’s order \(\href{#eulers-totient-function}{\varphi}(m) = (p - 1) \cdot (q - 1)\) and use the Pohlig-Hellman algorithm to compute discrete logarithms in this group. In order to avoid such a backdoor, you must insist that the other party shares the group’s order and its prime factorization with you.

What if \(G\) generates only a proper subgroup of \(\mathbb{Z}_m^\times\)? Since the running time of the index-calculus algorithm depends on the modulus \(m\) rather than \(G\)’s order \(n\), Pollard’s rho algorithm is faster than the index-calculus algorithm when \(n\) is small enough. If \(n\) has many small factors, the Pohlig-Hellman algorithm is even faster, of course. (Since the index-calculus algorithm is not the best choice for relatively small subgroups, it usually doesn’t make sense to use it as the DL algorithm in the Pohlig-Hellman algorithm.) If \(n\) is neither small nor smooth, you can solve the discrete-logarithm problem \(G^k =_m K\) as follows according to section 3.6.6 of the Handbook of Applied Cryptography (I don’t divide \(h\) and \(g\) by the cofactor of the subgroup for simplicity):

1. Find an element \(H \in \mathbb{Z}_m^\times\), which generates the whole group. (We still assume that \(m\) is prime, and thus \(\lvert \mathbb{Z}_m^\times \rvert = m - 1\).)
2. Use the index-calculus algorithm to find an integer \(g\) so that \(H^g =_m G\).
3. Use the index-calculus algorithm to find an integer \(h\) so that \(H^h =_m K\).
4. Return \(k :=_n h \cdot g^{-1}\).

This works because \((H^g)^k =_m H^h\) implies that \(g \cdot k =_{m-1} h\). Since \(n\) divides \(m - 1\), we have that \(g \cdot k - h\) is also a multiple of \(n\), and thus \(g \cdot k =_n h\). Since \(k\) is unique up to a multiple of \(n\), \(g\) has to be invertible modulo \(n\). Therefore, \(k =_n h \cdot g^{-1}\).

Interestingly, the above tool succeeds even if one of the bases \(P_i\) is not in the subgroup generated by \(G\). For example, it solves discrete logarithms in the subgroup of order 32 modulo 96 just fine. I have no idea why the index-calculus algorithm still works in this case, and I haven’t found any information about this phenomenon. If you know the answer, please let me know.

If the modulus \(m\) is composite, the above tool fails to invert the matrix of exponents. I understand that the prime factors of \(G\)’s order \(n\) determine which exponents have a multiplicative inverse modulo \(n\), which is why the above tool displays the prime factorization of \(n\). However, \(n\) can have many small factors no matter whether \(m\) is composite or prime. If you find a composite modulus for which the tool succeeds for a subgroup larger than four, or if you know why this isn’t possible, please let me know.

Since the third axiom (G3) does not specify how many identity elements there are, this notation is still a bit sloppy as it leaves the meaning of the identity element in the last axiom (G4) open. Must each element have an inverse for some identity element or for all identity elements? Keeping the quantifiers at the beginning of the statement and using the logical conjunction \(\land\) (“and”), the group axioms can be written less ambiguously as:

If, on the other hand, we replace the invertibility axiom with the following, then we do not define a group:

For example, the binary operation could then be defined as \(X \circ Y = X\) so that every element is a right identity and every element is a right inverse for every element, which is clearly not the same (and therefore not a group). We will see soon that there can be only one identity element and that each element has a unique inverse, which is why this aspect is often ignored.

If you remove one or several axioms from the above definition, you get other algebraic structures, most of which have names:

Instead of requiring that there is an identity and that each element has an inverse, we can simply require the following axiom:

This means that any element can be reached from any other element both from the left and from the right. This implies that every element can be reached from itself, i.e. every element has an identity element. In order to prove that this axiom, together with closure and associativity, defines the same algebraic structure as above, we just need show that the identity element is the same for all elements:

As every equation with two known values and one unknown value has a solution (see the axiom), every element has an inverse.