chapter  9
20 Pages

Modular Arithmetic

Let n be a positive integer. The set Zn is {0,1, . . . ,n−1}. The set Zn is a ring with the following operations.

x+ y= (x+ y) mod n and x · y= (xy) mod n The goal for this chapter is to develop a C++ class for working in Zn. Most of the C++ techniques used in this chapter have already been developed in previous chapters, but a few new ideas are presented here as well. The creation of a C++ class for representing elements of Zn is necessary for our later work in general finite fields.

9.1 Designing the Mod type In order to design a C++ class to emulate Zn we need to decide what sort of data is

stored in each object as well as the methods and operations to be performed on these objects. We also need a name for the new class and we choose the name Mod. Each object of type Mod represents an element of Zn for some positive integer n.

The element 8 in Z10 is different from the element 8 in Z11. (Consider the result of the operation 8+8.) Thus, each Mod object needs to hold two integers: the value in Zn and the modulus, n. We call these val and mod and we declare these as private members of the Mod class. To represent 8 in Z11, we set val equal to 8 and mod equal to 11. We need a constructor to create Mod objects, and the natural choice is to have a

constructor with two arguments: one that specifies the value and one that specifies the modulus. However, all classes should provide a default constructor that takes no arguments. What sort of object should Mod() construct? A natural choice is to set val to zero, but what of the modulus? One idea is to choose a default modulus that is used when a user does not specify a modulus. We are then faced with a decision: What should that default modulus be? Rather than impose a solution, we let the user decide. So we need a mechanism to set the default modulus. The implementation of this leads us to some new C++ concepts (static class variables and methods) and we explain these later in this chapter. Now that we have the concept of a default modulus we may also create a single-

argument constructor. A call to Mod(x) should create a new Mod object with value