﻿ Modulus and Repeated Values

# Modulus and Repeated Values

(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 gN in the ordinary integers, then simply reduce mod N at the final step. This is because gN 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 gPhi(N), or it will start sooner. However, it will never start later than gPhi(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 ZN.

The applet will calculate g raised to each power within the group ZN, 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 {g0=1, g1=g, g2, g3...} as "<g>", but this notation is not often used in the context of cryptography.

Last modified by Alyssa Vorpahl on November 22nd, 2018. Updated to Python 3 by Prof. Bard on April 7th, 2020.