Modulus and Repeated Values

An Interactive Applet powered by Sage and MathJax.

(By Alyssa Vorpahl and Prof. Gregory V. Bard)

Overview

This is an introductory page to show what happens when we raise an element of the integers mod N to higher and higher powers.

Discussion

Most of the math that is done in cryptography is modular arithmetic - that is, you select a modulus (N). Then, if a number would be ≥ N, you subtract a multiple of N such that the result is between 0 and N-1 (N is equivalent to 0 mod N). This is true of every mathematical operation under the modulus - at every step, the result is reduced mod N. This has an added benefit of making certain calculations much easier on computer hardware, as well as obfuscating the steps to reach a result (since the results of each step are reduced).

One of the most important operations in modern cryptography is modular exponentiation - raising a number to a certain power while working mod N. It is important to note that we do not just calculate g^N in the ordinary integers, then simply reduce mod N at the final step. This is because g^N might be incredibly large in the ordinary integers, and that calculation would require a large amount of time and memory. Instead, we use an algorithm called Rapid Modular Exponentiation.

This app will allow you to select a base number (g) and the modulus (N). It will then raise g to each power between 0 and N. You will notice that eventually, the numbers start repeating themselves.

Sometimes, the repetition will start at g^Phi(N), or it will start sooner. However, it will never start later than g^Phi(N). Later, we will learn that there is a term for those choices of g where the repetition begins at the last possible value. Those g values will be called "generators mod N".

Instructions

Once you load the applet, there will be two sliders: one to control the g value, and one to control the modulus N.

• g must be < N because it has to be an element of the group Z_N.

The applet will calculate g raised to each power within the group Z_N, then return the result. If it catches any repeated results, those results will be flagged. (Note that the final one will always be flagged as a repeat.)

As an aside, in courses such as 'abstract algebra', 'modern algebra', or 'groups, rings, and fields', this type of sequence is frequently studied. We can abbreviate {g⁰=1, g¹=g, g², g³...} as "<g>", but this notation is not often used in the context of cryptography.