Assignment 8 - due Monday, November 22, midnight, by email
Please do work on your own - no group work. If you are stuck,
contact me. Collaborating on this assignment will be viewed
as cheating.
Important Note
I want you to email me your assignment this week. You can either zip together
a set of files, or send them separately. My address: fickas@cs.uoregon.edu.
Problem 1
For the last part of the course, we will look at cryptography. Chapter 50 is a lead in
to primes, and we will find that prime numbers play a big role in cryptography.
Read chapter 50 in Dewdney. Note that "witness" simply means a number that divides
another number evenly. So 3 is a witness to 3, 6, 9, 12, 15, etc. If we choose some
number p and believe it is a prime number, then it better not have any witnesses, right?
No other numbers (other than 1 and p, itself) should divide p evenly.
Part a. One thing we will need to compute Rabin's prime detector is a GCD (Greatest Common
Divisor) function. The GCD function takes two inputs a and b, and outputs the largest
number that divides both a and b evenly. You are probably familiar with this function when
you are working with fractions. Some examples:
<![CDATA[
GCD( 4, 2 ) = 2
GCD( 9, 27 ) = 9
GCD( 9, 28 ) = 1
GCD( 27, 12 ) = 3
]]>
Now what if we want to know if a number k is a witness to p, where k < p? What if I set it up as
GCD( k, p )? If k is a witness to p, I should get a value that is greater than 1. If k is not a
witness to p, then I should get the value 1.
Once I have the GCD method, I can begin to work on the rest of Rabin's algorithm. For this assignment,
I would like you to program the GCD method. First, I'll give you its mathematical definition according
to Euclid (an old algorithm hacker, circa 300 BCE):
<![CDATA[
GCD( a, 0 ) = a.
GCD( a, b ) = if a < b then GCD( b, a ) else GCD( b, a%b ).
]]>
That is called a "recursive" definition because the definition of GCD makes reference
back to GCD. Kind of a circular argument. We can turn this definition into a non-recursive
form as follows:
<![CDATA[
GCD( a, b ) =
while b is not 0
if a < b then swap a and b else assign a to b and b to a%b.
return a as the answer
]]>
Note that the assignments necessary in the then and else clauses are a bit tricky:
they will require you to use a third, temporary variable.
For this problem, use the skeleton below. Program the while loop where commented.
Instead of "returning" an answer, just print out the value of a.
<![CDATA[
class GCD {
public static void main( String [] args ){
int a = ...;
int b = ...;
//while loop goes here
System.out.println( "The answer is " + a );
} //main
} //GCD
]]>
You can fill in the values of a and b with various values to make sure your code works.
Part b. Once your GCD is working, you are ready to use Rabin's algorithm to find if a number
p is a prime. I'll give you a skeleton:
<![CDATA[
import java.util.*;
class Rabin {
public static void main( String [] args ){
int p = ...; //number we want to check for prime-ness
int m = ...; //number of witnesses we want to try (can range from 1 to p-1)
//Loop here, trying m witnesses. Can stop as soon as find a witness that divides p.
//If none of the witnesses you try will divide p, conclude p is prime.
//get the next candidate witness
int witness = (int)(Math.random() * p)+2; //will return a random int between 2 and p
//your answer from part a goes here, with modifications below
int a = p;
int b = witness;
//GCD while loop goes here
//if b divides a, then p is not a prime else keep trying
//end of loop
double prob = Math.pow( .5, m ); //.5**m
if( ... )
System.out.println( p + " is prime with probability " + (...));
else
System.out.println( p + " is not prime with probability " + ...);
} //main
} //Rabin
]]>
The probability definitions you will need in the println statements are given on page 337.
Turn-in: For both parts a and b, I would like a file that I can load. I will then try
different numbers where I have the three dots to make sure your code works.
Problem 2
No second problem this week.