C++ For Mathematicians (2006) [eng]

Chapter 9

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.1Designing 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 singleargument constructor. A call to Mod(x) should create a new Mod object with value x in the default modulus.

157

158 C++ for Mathematicians

So far, the Mod class looks like this:

class Mod { private:

long val; long mod;

public:

Mod(); Mod(long x);

Mod(long x, long m);

};

The operations and methods we want to perform with Mod objects are these.

•Given a Mod object, we need to inspect and to modify both its value and its modulus. Changing either the value or the modulus may require us to change the other because a value x Zn must satisfy 0 ≤ x ≤ n −1.

•Given two Mod objects, we should be able to check whether they are equal. In addition, we define a < operator to compare Mod objects; this enables us to store Mod objects in containers such as a set that require a < operator.

•We want to be able to perform the usual arithmetic operations:

x+y; x-y; x*y; x/y;

x += y; x -= y; x *= y; x /= y; -x;

For these operations, we need to be concerned about two situations that may arise: combining objects of different moduli and division by a noninvertible element of Zn. We handle these by returning an invalid Mod object. This invalid value is represented internally with value and modulus equal to zero. (Valid Mod objects have a positive modulus.)

Furthermore, it is convenient to be able to combine Mod and long objects with a single operation. For example, suppose x and y are Mod objects, then a statement such as y = x+1; should assign to y a value one greater than x’s and the same modulus as x.

•In addition to the operations listed above, we want to perform exponentiation ak where a Zn and k Z. Negative exponentiation gives a valid result provided a is invertible.

9.2The code

We now present the Mod.h and Mod.cc files. The header file is long; to make it more manageable for you to read we have removed most of the comments.

In the sections that follow, we work our way through the various features of the Mod class that these files implement.

Modular Arithmetic

159

Program 9.1: Header file for the Mod class, Mod.h.

1 #ifndef MOD_H

2#define MOD_H

3 #include <iostream>

4using namespace std;

5

6const long INITIAL_DEFAULT_MODULUS = 2;

7

8 class Mod {

9private:

10long mod;

11long val;

12static long default_modulus;

13void adjust_val() {

14val = val%mod;

15if (val<0) val += mod;

16}

17

18public:

19Mod() {

20mod = get_default_modulus();

21val = 0;

22}

23

24Mod(long x) {

25mod = get_default_modulus();

26val = x;

27adjust_val();

28}

29

30Mod(long x, long m) {

31if (m <= 0) {

32val = 0;

33mod = 0;

34}

35else {

36mod = m;

37val = x;

38adjust_val();

39}

40}

41

42 long get_val() const { return val; }

43

44void set_val(long x) {

45if (mod == 0) return; // no change for an invalid object

46val = x;

47adjust_val();

48}

49

50 long get_mod() const { return mod; }

51

52void set_mod(long m) {

53if (m <= 0) {

54mod = 0;

160	C++ for Mathematicians

55val = 0;

56}

57else {

58mod = m;

59adjust_val();

60}

61}

62

63static void set_default_modulus(long m) {

64if (m <= 0) {

65default_modulus = INITIAL_DEFAULT_MODULUS;

66}

67else {

68default_modulus = m;

69}

70}

71

72static long get_default_modulus() {

73if (default_modulus <= 0)

74set_default_modulus(INITIAL_DEFAULT_MODULUS);

75return default_modulus;

76}

77bool is_invalid() const { return mod==0; }

78

79bool operator==(const Mod& that) const {

80return ( (val==that.val) && (mod==that.mod) );

81}

82

83bool operator==(long that) const {

84return (*this) == Mod(that,mod);

85}

86

87bool operator!=(const Mod& that) const {

88return ( (val != that.val) || (mod != that.mod) );

89}

90

91bool operator !=(long that) const {

92return (*this) != Mod(that,mod);

93}

94

95bool operator<(const Mod& that) const {

96if (mod < that.mod) return true;

97if (mod > that.mod) return false;

98if (val < that.val) return true;

99return false;

100}

101

102 Mod add(Mod that) const;

103

104 Mod operator+(const Mod& x) const { return add(x); }

105

106 Mod operator+(long x) const { return add(Mod(x,mod)); }

107

108Mod operator+=(const Mod& x) {

109*this = add(x);

110return *this;

	Modular Arithmetic	161
111
	}
112
113	Mod operator+=(long x) {
114	*this = add(Mod(x,mod));
115	return *this;
116	}
117
118	Mod operator-() const { return Mod(-val,mod); }
119

120Mod operator-(const Mod& x) const {

121return (*this) + (-x);

122}

123

124Mod operator-(long x) const {

125return (*this) + (-x);

126}

127

128Mod operator-=(const Mod& x) {

129*this = add(-x);

130return *this;

131}

132

133Mod operator-=(long x) {

134*this = *this + (-x);

135return *this;

136}

137

138 Mod multiply(Mod that) const;

139

140 Mod operator*(const Mod& x) const { return multiply(x); }

141

142 Mod operator*(long x) const { return multiply(Mod(x,mod)); }

143

144Mod operator*=(const Mod& x) {

145*this = multiply(x);

146return *this;

147}

148

149Mod operator*=(long x) {

150*this = multiply(Mod(x,val));

151return *this;

152}

153

154 Mod inverse() const;

155

156 Mod operator/(const Mod& x) const { return multiply(x.inverse()); }

157

158Mod operator/(long x) const {

159return multiply(Mod(x,mod).inverse());

160}

161

162Mod operator/=(const Mod& x) {

163*this = multiply(x.inverse());

164return *this;

165}

166

162	C++ for Mathematicians

167Mod operator/=(long x) {

168*this = multiply(Mod(x,mod).inverse());

169return *this;

170}

171

172 Mod pow(long k) const;

173

174 };

175

176 ostream& operator<<(ostream& os, const Mod& M);

177

178inline bool operator==(long x, const Mod& y) {

179return (y==x);

180}

181

182inline bool operator!=(long x, const Mod& y) {

183return (y!=x);

184}

185

186inline Mod operator+(long x, Mod y) {

187return y+x;

188}

189

190inline Mod operator-(long x, Mod y) {

191return (-y) + x;

192}

193

194inline Mod operator*(long x, Mod y) {

195return y*x;

196}

197

198inline Mod operator/(long x, Mod y) {

199return y.inverse() * x;

200}

201

202 #endif

Program 9.2: Source file for the Mod class, Mod.cc.

1 #include "Mod.h"

2#include "gcdx.h"

3

4long Mod::default_modulus = INITIAL_DEFAULT_MODULUS;

5

6 ostream& operator<<(ostream& os, const Mod& M) {

7if (!M.is_invalid()) {

8os << "Mod(" << M.get_val() << "," << M.get_mod() << ")";

9}

10else {

11os << "INVALID";

12}

13return os;

14}

15

16 Mod Mod::add(Mod that) const {

Modular Arithmetic

163

17if (is_invalid() || that.is_invalid()) return Mod(0,0);

18if (mod != that.mod) return Mod(0,0);

19return Mod(val + that.val, mod);

20}

21

22Mod Mod::multiply(Mod that) const {

23if (is_invalid() || that.is_invalid()) return Mod(0,0);

24if (mod != that.mod) return Mod(0,0);

25return Mod(val * that.val, mod);

26}

27

28Mod Mod::inverse() const {

29long d,a,b;

30if (is_invalid()) return Mod(0,0);

31

32 d = gcd(val, mod, a, b);

33

34if (d>1) return Mod(0,0); // no reciprocal if gcd(v,x)!= 1

35return Mod(a,mod);

36}

37

38Mod Mod::pow(long k) const {

39if (is_invalid()) return Mod(0,0); // invalid is forever

40

41// negative exponent: reciprocal and try again

42if (k<0) {

43return (inverse()).pow(-k);

44}

45

46// zero exponent: return 1

47if (k==0) return Mod(1,mod);

48

49// exponent equal to 1: return self

50if (k==1) return *this;

51

52// even exponent: return ( mˆ(k/2) )ˆ2

53if (k%2 == 0) {

54Mod tmp = pow(k/2);

55return tmp*tmp;

56}

57

58// odd exponent: return ( mˆ((k-1)/2) )ˆ2 * m

59Mod tmp = pow((k-1)/2);

60return tmp*tmp*(*this);

61}

9.3 The default modulus: Static class variables and methods

The design of the Mod type calls for the notion of a default modulus. The default modulus is employed when the user does not specify a modulus. This occurs with the

164	C++ for Mathematicians

single-argument constructor Mod(long) (described in detail in Section 9.4). Consider the following code.

Mod x(6); Mod y;

y = 5; Mod z;

z = Mod(1);

For x, we explicitly invoke the single-argument constructor to set x equal to the element 6 in Zn where n is the current default modulus. The variable y is first built using the default (no-argument) constructor with value 0 in Zn where, as before, n is the default modulus. Then the assignment y = 5; implicitly calls the singleargument constructor to give y the value 5 in Zn. Finally, the variable z is assigned the value 1 Zn; in this case, we explicitly invoke the single-argument constructor.

To create and to use a default modulus value, we need to accomplish the following tasks.

•We need a variable to hold the current value of the default modulus.

•We need an initial value for the default modulus.

•We need the ability to inspect and to change the value of the default modulus.

Let’s tackle these one at a time.

Where should the value of the default modulus be held? The simplistic answer is to save it in a variable named default_modulus of type long. However, this does not completely answer the question; we need to know where this variable is declared.

We might make default_modulus a variable in the main procedure, but there are many drawbacks to this: we need to remember to include the declaration and then we would need to pass it to every Mod method that might need it. This makes life too difficult for the programmer.

Could we make default_modulus an ordinary member variable for the class Mod? No. The problem is that each Mod object would hold its own “personal” default_modulus. We want one and only one value for default_modulus that is common to all Mod objects.

Could we make default_modulus a global variable? A global variable is one that is accessible to all procedures of a program. This is possible, but undesirable. If default_modulus were global, any procedure would be able to modify default_modulus and set it to a nonsensical value (such as 0 or −1). We want to hide the variable default_modulus and limit access by get and set procedures. The set method would ensure that default_modulus always holds a sensible value. Furthermore, global variables are a dangerous programming trick; different parts of the program can access and modify these values in unpredictable ways.

What we need is a private variable that “belongs” to the entire class Mod and not to any one particular object of type Mod. Such a variable is called a static class variable.

Inside the private section of the Mod class declaration, we have this (line 12 of Program 9.1, Mod.h):

Modular Arithmetic

165

static long default_modulus;

This line announces that the class Mod contains a variable named default_modulus (of type long) and this value is common to all Mod objects. (By contrast, the private class values mod and val vary from one Mod object to another.)

Unfortunately, this one line does not quite finish the job of setting up this variable. Somewhere in our program, but outside the class definition, we need to declare this variable. (The long class { ... }; just describes the class Mod. The actual declaration of a variable takes place in a .cc file.)

The declaration of default_modulus takes place on line 4 of the file Mod.cc (Program 9.2) and looks like this:

long Mod::default_modulus = INITIAL_DEFAULT_MODULUS;

Let’s examine this line one step at a time. First, we are declaring a variable of type long, so the keyword long begins this line. The name of the variable is default_modulus, but it is a member of the Mod class; hence, the full name of this variable is Mod::default_modulus. Finally, we give this variable a value (rather than letting C++ give it one). We could have typed a specific number, such as 10. Thus long Mod::default_modulus= 10; would be acceptable. However, we should avoid nameless constants in our programs. So, the header file (see line 6 of Mod.h, Program 9.1) declares a global constant equal to 2 like this:

const long INITIAL_DEFAULT_MODULUS = 2;

(Global constants are good; global variables are bad.) Thus, whenever the program starts up, the variable default_modulus has a known value.

The variable default_modulus is hidden from view because it is sequestered in the private section of the class declaration. It is not possible to change this value directly in, say, a main() procedure. Only methods belonging to the class Mod can access and modify this value. To do this, we create two procedures named get_default_modulus and set_default_modulus.

If we so chose, we could define such methods inside (i.e., inline) the class declaration like this:

class Mod {

...

public:

...

void set_default_modulus(long m) { default_modulus = m; }

long get_default_modulus() { return default_modulus; }

...

};

(Because these are class methods, the keyword inline is not required.)

The problem with this approach is that to change the default modulus, we would need to have a variable of type Mod (let’s call it x) and use a statement of the form x.get_default_modulus(17);. Although this would work, the necessity to connect these methods to a particular Mod object doesn’t make sense. There’s nothing about x that is relevant here. (Note: The proposed code for set_default_modulus