ALGORITHMS FROM CLASSICAL ALGEBRA*

0. Definition

If a, b are integers, we say that a divides b, and write this symbolically as a|b, if there exists an integer q, such that b=qa.


I. The Division Algorithm

If a, b are integers, where a>0, then there exists unique integers q and r such that,

b=qa+r where 0≤ r < a

Program: Write a function with the header,

void Division (int a, int b, int &q, int &r)

that accepts an divisor, a and dividend, b. The function determines the quotient, q, and the remainder, r. Write a main program that exercises the function for a number of well-chosen integer pairs.


II. The Euclidean Algorithm

The greatest common divisor of two integers a and b, GCD(a,b), not both of which are zero, is the largest positive integer that divides both a and b. The Euclidean algorithm for finding this greatest common denominator of a and b is as follows:

Divide a and b to obtain the integer quotient q and the remainder r, so that a=qr+b (if b=0, GCD(a,b)=a). Then GCD(a,b)=GCD(b,r). Replace a and b with b and r and repeat this procedure.

Because the remainders are decreasing, eventually a remainder of 0 will result. The last nonzero remainder is GCD(a,b). For example,

	1260 = 198×6+72		GCD(1260,198) = GCD(198,72)
	 198 = 72×2+54		              = GCD(72,54)
	  72 = 54×1+18		              = GCD(54,18)
	  54 = 18×3+0		              = 18	
(Note: If either a or b is negative, replace them with their absolute values in this algorithm.)

Program:  Write a recursive common divisor function and a main program that exercises it for a number of well-chosen integer pairs.


III. The Sieve of Eratosthenes

There is no known efficient procedure for finding prime numbers. A classical, but tedious, method attributed to Eratosthenes (276 - 196 BC), can be described as follows. First, write down a list of integers, paired with true values,

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T T T T T T T T  T  T  T  T  T  T  T  T  T  T  T

Then mark all multiples of 2 by switching its true to false,

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

T T F T F T F T F T F T F T F T T T F

Move to the next unmarked number, which in this case is 3, then mark all its multiples:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
T T F T F T F F  F  T  F  T  F  F  F  T  F  T  F 

Continue in this fashion, marking all multiples of the next unmarked number until there are no new unmarked numbers. The numbers which survive this marking process (the Sieve of Eratosthenses) are primes.

Task. Write the class, Sieve, that will implement the Sieve of Eratosthenes and determine the prime numbers from 2 to n-1, where the integer n is determined by the user. 

Your program will create an array of length n, initializing all cells to true. Starting with array index 2, (ignore index 0 and index 1), every time an array element is found to be true, loop through the remainder of the array and set to false every element whose index is a multiple of the starting index.

At the end of the implementation, array elements that remain true have an index which is a prime number. Display the prime numbers to the console.


IV. Linear Diophantine Equations
  1. A Diophantine equation is an equation in one or more variables with integer coefficients for which  integer solutions are sought. The linear Diophantine equation

    ax+by=c

    has a solution if and only if GCD(a,b)|c.

  2. If GCD(a,b)=d and x=x0, y=y0 is one particular solution, when a and b are not both zero, then the complete integer solution is 

    x= x0+(b/d)n,    y=y0-(a/d)n    for all integers, n.


V. Extended Euclidean Algorithm

The algorithm to determine the one particular solution, (x0,y0), of the Diophantine equation defined above is easily implemented. Consider the equation from part II above,

1260x+198y = 18

START: Write down the first two rows  in the table at left below.
si ti ri
1 0 1260
0 1 198
1 -6 72
-2 13 54
3 -19 18
-11 70 0
qi Euclidean Algorithm
   
   
6 1260 = 198·6 + 72
2 198 = 72·2 + 54
1 72 = 54·1 + 18
3 54 = 18·3 + 0

First step: Divide a by b using the Division algorithm, so that a=q1b+r1 where 0≤r1<b. Take the top row and subtract q1 times the next row from it.

GENERAL STEP: Continue through the Euclidean Algorithm, making use of the Division Algorithm.

STOP: Stop when rn+1=0.

Conclusions:

  1. GCD(a,b) = rn.
  2. Each row (si,ti,ri) satisfies the equation asi+bti=ri.
  3. The general integer solution to ax+by=c is

x=sn+sn+1n,        y=tn+tn+1n,    for all integer, n.

Program: Implement the Extended Euclidean Algorithm and test it with triples entered by the user from the keyboard. For example,

Input:    1260,198,18 
Output: One solution for 1260x+198y=18 is x=3 and y=-19.

Input:    28,35,60 
Output: 28x+35y=60 has no solution since GCD(28,35) does not divide 60.

Input:    21,15,9
Output: One solution for 21x+15y=9 is x=-6 and y=9.

Your program should terminate when a=0.


VI. Cryptography I

An early user of cryptography was Julius Cæsar. Messages sent to his troops were encrypted in a manner similar to the following. Each letter in the original message was replaced  with a letter n places to the right (or left). For example, if the original message was ATTACK, and n=3, its encryption is, DWWDFN. This technique is commonly referred to as a Cæsar cipher and is very easily broken.

Program:
Write functions, void Encrypt(apstring &s, int n) and void Decrypt(apstring &s, int n) that make use of the modulo operator, %, to demonstrate the Cæsar cipher. Write a main program to exercise your functions.


VII. RSA Encryption
*Much of this text has been adapted from, CLASSICAL ALGEBRA, FOURTH EDITION, William J. Gilbert, Scott A. Vanstone, University of Waterloo, Centre for Education in Mathematics and Computing, 4th Edition, June 2000.
(Thank you to Ivan Chin for bringing this wonderful text to my attention)