I\'m having trouble with some of the incomplete methods in this code. If i could
ID: 3807657 • Letter: I
Question
I'm having trouble with some of the incomplete methods in this code. If i could get some help, that would be great.
import components.naturalnumber.NaturalNumber;
import components.naturalnumber.NaturalNumber2;
import components.random.Random;
import components.random.Random1L;
import components.simplereader.SimpleReader;
import components.simplereader.SimpleReader1L;
import components.simplewriter.SimpleWriter;
import components.simplewriter.SimpleWriter1L;
/*
*
* Utilities that could be used with RSA cryptosystems.
*
* @author Put your name here
*
*/
public final class CryptoUtilities {
/*
*
* Private constructor so this utility class cannot be instantiated.
*/
private CryptoUtilities() { }
/*
*
* Useful constant, not a magic number: 3.
*/
private static final int THREE = 3;
/*
*
* Pseudo-random number generator.
*/
private static final Random GENERATOR = new Random1L();
/*
*
* Returns a random number uniformly distributed in the interval [0, n].
*
* @param n
* top end of interval
* @return random number in interval
* @requires n > 0
* @ensures
* randomNumber = [a random number uniformly distributed in [0, n]]
*
*/
public static NaturalNumber randomNumber(NaturalNumber n) {
assert !n.isZero() : "Violation of: n > 0"; final int base = 10;
NaturalNumber result; int d = n.divideBy10();
if (n.isZero()) {
/*
* Incoming n has only one digit and it is d, so generate a random
* number uniformly distributed in [0, d]
*/
int x = (int) ((d + 1)* GENERATOR.nextDouble()); result = new NaturalNumber2(x); n.multiplyBy10(d);
} else {
/*
* Incoming n has more than one digit, so generate a random number
* (NaturalNumber) uniformly distributed in [0, n], and another
* (int) uniformly distributed in [0, 9] (i.e., a random digit)
*/
result = randomNumber(n);
int lastDigit = (int) (base * GENERATOR.nextDouble());
result.multiplyBy10(lastDigit);
n.multiplyBy10(d);
if (result.compareTo(n) > 0) {
/*
* In this case, we need to try again because generated number
* is greater than n; the recursive call's argument is not
* "smaller" than the incoming value of n, but this recursive
* call has no more than a 90% chance of being made (and for
* large n, far less than that), so the probability of
* termination is 1
*/
result = randomNumber(n);
}
}
return result;
}
/*
*
* Finds the greatest common divisor of n and m.
*
* @param n
* one number
* @param m
* the other number
* @updates n
* @clears m
* @ensures n = [greatest common divisor of #n and #m]
*/
public static void reduceToGCD(NaturalNumber n, NaturalNumber m) {
/*
* Use Euclid's algorithm; in pseudocode: if m = 0 then GCD(n, m) = n
* else GCD(n, m) = GCD(m, n mod m)
*/
// TODO - fill in body
}
/*
*
* Reports whether n is even.
*
* @param n
* the number to be checked
* @return true iff n is even
* @ensures isEven = (n mod 2 = 0)
*/
public static boolean isEven(NaturalNumber n) {
// TODO - fill in body
/*
* This line added just to make the program compilable. Should be
* replaced with appropriate return statement.
*/
return true;
}
/*
*
* Updates n to its p-th power modulo m.
*
* @param n
* number to be raised to a power
* @param p
* the power
* @param m
* the modulus
* @updates n
* @requires m > 1
* @ensures n = #n ^ (p) mod m
*/
public static void powerMod(NaturalNumber n, NaturalNumber p, NaturalNumber m) {
assert m.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: m > 1";
/*
* Use the fast-powering algorithm as previously discussed in class,
* with the additional feature that every multiplication is followed
* immediately by "reducing the result modulo m"
*/
// TODO - fill in body
}
/*
*
* Reports whether w is a "witness" that n is composite, in the sense that
* either it is a square root of 1 (mod n), or it fails to satisfy the
* criterion for primality from Fermat's theorem.
*
* @param w
* witness candidate
* @param n
* number being checked
* @return true iff w is a "witness" that n is composite
* @requires n > 2 and 1 < w < n - 1
* @ensures
* isWitnessToCompositeness =
* (w ^ 2 mod n = 1) or (w ^ (n-1) mod n /= 1)
*
*/
public static boolean isWitnessToCompositeness(NaturalNumber w, NaturalNumber n) {
assert n.compareTo(new NaturalNumber2(2)) > 0 : "Violation of: n > 2";
assert (new NaturalNumber2(1)).compareTo(w) < 0 : "Violation of: 1 < w";
n.decrement();
assert w.compareTo(n) < 0 : "Violation of: w < n - 1"; n.increment();
// TODO - fill in body
/*
* This line added just to make the program compilable. Should be
* replaced with appropriate return statement.
*/
return true; }
/*
*
* Reports whether n is a prime; may be wrong with "low" probability.
*
* @param n
* number to be checked
* @return true means n is very likely prime; false means n is definitely
* composite
* @requires n > 1
* @ensures
* isPrime1 = [n is a prime number, with small probability of error
* if it is reported to be prime, and no chance of error if it is * reported to be composite]
*
*/
public static boolean isPrime1(NaturalNumber n) {
assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1";
boolean isPrime;
if (n.compareTo(new NaturalNumber2(THREE)) <= 0) {
/*
* 2 and 3 are primes
*/
isPrime = true;
}
else if (isEven(n)) {
/*
* evens are composite
*/
isPrime = false;
} else {
/*
* odd n >= 5: simply check whether 2 is a witness that n is
* composite (which works surprisingly well :-)
*/
isPrime = !isWitnessToCompositeness(new NaturalNumber2(2), n); }
return isPrime; }
/*
*
* Reports whether n is a prime; may be wrong with "low" probability.
*
* @param n
* number to be checked
* @return true means n is very likely prime; false means n is definitely
* composite
* @requires n > 1
* @ensures
* isPrime1 = [n is a prime number, with small probability of error
* if it is reported to be prime, and no chance of error if it is * reported to be composite]
*
*/
public static boolean isPrime2(NaturalNumber n) {
assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1";
/*
* Use the ability to generate random numbers (provided by the
* randomNumber method above) to generate several witness candidates --
* say, 10 to 50 candidates -- guessing that n is prime only if none of
* these candidates is a witness to n being composite (based on fact #3
* as described in the project description); use the code for isPrime1
* as a guide for how to do this, and pay attention to the requires
* clause of isWitnessToCompositeness
*/
// TODO - fill in body
/*
* This line added just to make the program compilable. Should be
* replaced with appropriate return statement.
*/
return true;
}
/*
*
* Generates a likely prime number at least as large as some given number.
*
* @param n
* minimum value of likely prime
* @updates n
* @requires n > 1
* @ensures n >= #n and [n is very likely a prime number]
*/
public static void generateNextLikelyPrime(NaturalNumber n) {
assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1";
/*
* Use isPrime2 to check numbers, starting at n and increasing through
* the odd numbers only (why?), until n is likely prime
*/
// TODO - fill in body
}
/*
*
* Main method.
*
* @param args
* the command line arguments
*/
public static void main(String[] args) {
SimpleReader in = new SimpleReader1L();
SimpleWriter out = new SimpleWriter1L();
/*
* Sanity check of randomNumber method -- just so everyone can see how
* it might be "tested"
*/
final int testValue = 17;
final int testSamples = 100000;
NaturalNumber test = new NaturalNumber2(testValue);
int[] count = new int[testValue + 1];
for (int i = 0; i < count.length; i++) { count[i] = 0;
} for (int i = 0; i < testSamples; i++) {
NaturalNumber rn = randomNumber(test);
assert rn.compareTo(test) <= 0 : "Help!";
count[rn.toInt()]++;
} for (int i = 0; i < count.length; i++) {
out.println("count[" + i + "] = " + count[i]);
}
out.println(" expected value = " + (double) testSamples / (double) (testValue + 1));
/*
* Check user-supplied numbers for primality, and if a number is not
* prime, find the next likely prime after it
*/
while (true) { out.print("n = ");
NaturalNumber n = new NaturalNumber2(in.nextLine());
if (n.compareTo(new NaturalNumber2(2)) < 0) { out.println("Bye!");
break;
} else {
if (isPrime1(n)) { out.println(n + " is probably a prime number" + " according to isPrime1.");
} else {
out.println(n + " is a composite number" + " according to isPrime1.");
}
if (isPrime2(n)) { out.println(n + " is probably a prime number" + " according to isPrime2.");
} else {
out.println(n + " is a composite number" + " according to isPrime2.");
generateNextLikelyPrime(n);
out.println(" next likely prime is " + n);
}
}
}
/*
* Close input and output streams
*/
in.close();
out.close();
Explanation / Answer
//Codes for require methods are updated.
import components.naturalnumber.NaturalNumber;
import components.naturalnumber.NaturalNumber2;
import components.random.Random;
import components.random.Random1L;
import components.simplereader.SimpleReader;
import components.simplereader.SimpleReader1L;
import components.simplewriter.SimpleWriter;
import components.simplewriter.SimpleWriter1L;
/*
*
* Utilities that could be used with RSA cryptosystems.
*
* @author Put your name here
*
*/
public final class CryptoUtilities
{
/*
*
* Private constructor so this utility class cannot be instantiated.
*/
private CryptoUtilities() { }
/*
*
* Useful constant, not a magic number: 3.
*/
private static final int THREE = 3;
/*
*
* Pseudo-random number generator.
*/
private static final Random GENERATOR = new Random1L();
/*
* Returns a random number uniformly distributed in the interval [0, n].
* @param n
* top end of interval
* @return random number in interval
* @requires n > 0
* @ensures
* randomNumber = [a random number uniformly distributed in [0, n]]
*/
public static NaturalNumber randomNumber(NaturalNumber n)
{
assert !n.isZero() : "Violation of: n > 0"; final int base = 10;
NaturalNumber result; int d = n.divideBy10();
if (n.isZero())
{
/*
* Incoming n has only one digit and it is d, so generate a random
* number uniformly distributed in [0, d]
*/
int x = (int) ((d + 1)* GENERATOR.nextDouble()); result = new NaturalNumber2(x); n.multiplyBy10(d);
}
else
{
/*
* Incoming n has more than one digit, so generate a random number
* (NaturalNumber) uniformly distributed in [0, n], and another
* (int) uniformly distributed in [0, 9] (i.e., a random digit)
*/
result = randomNumber(n);
int lastDigit = (int) (base * GENERATOR.nextDouble());
result.multiplyBy10(lastDigit);
n.multiplyBy10(d);
if (result.compareTo(n) > 0)
{
/*
* In this case, we need to try again because generated number
* is greater than n; the recursive call's argument is not
* "smaller" than the incoming value of n, but this recursive
* call has no more than a 90% chance of being made (and for
* large n, far less than that), so the probability of
* termination is 1
*/
result = randomNumber(n);
}
}
return result;
}
/*
*
* Finds the greatest common divisor of n and m.
*
* @param n
* one number
* @param m
* the other number
* @updates n
* @clears m
* @ensures n = [greatest common divisor of #n and #m]
*/
public static void reduceToGCD(NaturalNumber n, NaturalNumber m)
{
/*
* Use Euclid's algorithm; in pseudocode: if m = 0 then GCD(n, m) = n
* else GCD(n, m) = GCD(m, n mod m)
*/
// TODO - fill in body
if(m==0)
n=n;
else
n=reduceToGCD(m,n%m);
}
/*
*
* Reports whether n is even.
*
* @param n
* the number to be checked
* @return true iff n is even
* @ensures isEven = (n mod 2 = 0)
*/
public static boolean isEven(NaturalNumber n)
{
// TODO - fill in body
/*
* This line added just to make the program compilable. Should be
* replaced with appropriate return statement.
*/
if(n%2==0)
return true;
return false;
}
/*
*
* Updates n to its p-th power modulo m.
*
* @param n
* number to be raised to a power
* @param p
* the power
* @param m
* the modulus
* @updates n
* @requires m > 1
* @ensures n = #n ^ (p) mod m
*/
public static void powerMod(NaturalNumber n, NaturalNumber p, NaturalNumber m)
{
assert m.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: m > 1";
/*
* Use the fast-powering algorithm as previously discussed in class,
* with the additional feature that every multiplication is followed
* immediately by "reducing the result modulo m"
*/
// TODO - fill in body
for(int i=0;i<p;i++)
n=(n*n)%m;
n=n%m;
}
/*
*
* Reports whether w is a "witness" that n is composite, in the sense that
* either it is a square root of 1 (mod n), or it fails to satisfy the
* criterion for primality from Fermat's theorem.
*
* @param w
* witness candidate
* @param n
* number being checked
* @return true iff w is a "witness" that n is composite
* @requires n > 2 and 1 < w < n - 1
* @ensures
* isWitnessToCompositeness =
* (w ^ 2 mod n = 1) or (w ^ (n-1) mod n /= 1)
*
*/
public static boolean isWitnessToCompositeness(NaturalNumber w, NaturalNumber n)
{
assert n.compareTo(new NaturalNumber2(2)) > 0 : "Violation of: n > 2";
assert (new NaturalNumber2(1)).compareTo(w) < 0 : "Violation of: 1 < w";
n.decrement();
assert w.compareTo(n) < 0 : "Violation of: w < n - 1"; n.increment();
// TODO - fill in body
/*
* This line added just to make the program compilable. Should be
* replaced with appropriate return statement.
*/
//NaturalNumber ans=
if((w*w)%n==1 || (Math.pow(w,n-1)%n)!=1)
return true;
return false;
}
/*
* Reports whether n is a prime; may be wrong with "low" probability.
*
* @param n
* number to be checked
* @return true means n is very likely prime; false means n is definitely
* composite
* @requires n > 1
* @ensures
* isPrime1 = [n is a prime number, with small probability of error
* if it is reported to be prime, and no chance of error if it is * reported to be composite]
*
*/
public static boolean isPrime1(NaturalNumber n)
{
assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1";
boolean isPrime;
if (n.compareTo(new NaturalNumber2(THREE)) <= 0)
{
/*
* 2 and 3 are primes
*/
isPrime = true;
}
else if (isEven(n)) {
/*
* evens are composite
*/
isPrime = false;
} else {
/*
* odd n >= 5: simply check whether 2 is a witness that n is
* composite (which works surprisingly well :-)
*/
isPrime = !isWitnessToCompositeness(new NaturalNumber2(2), n); }
return isPrime;
}
/*
*
* Reports whether n is a prime; may be wrong with "low" probability.
*
* @param n
* number to be checked
* @return true means n is very likely prime; false means n is definitely
* composite
* @requires n > 1
* @ensures
* isPrime1 = [n is a prime number, with small probability of error
* if it is reported to be prime, and no chance of error if it is * reported to be composite]
*
*/
public static boolean isPrime2(NaturalNumber n)
{
assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1";
/*
* Use the ability to generate random numbers (provided by the
* randomNumber method above) to generate several witness candidates --
* say, 10 to 50 candidates -- guessing that n is prime only if none of
* these candidates is a witness to n being composite (based on fact #3
* as described in the project description); use the code for isPrime1
* as a guide for how to do this, and pay attention to the requires
* clause of isWitnessToCompositeness
*/
// TODO - fill in body
/*
* This line added just to make the program compilable. Should be
* replaced with appropriate return statement.
*/
return true;
}
/*
*
* Generates a likely prime number at least as large as some given number.
*
* @param n
* minimum value of likely prime
* @updates n
* @requires n > 1
* @ensures n >= #n and [n is very likely a prime number]
*/
public static void generateNextLikelyPrime(NaturalNumber n) {
assert n.compareTo(new NaturalNumber2(1)) > 0 : "Violation of: n > 1";
/*
* Use isPrime2 to check numbers, starting at n and increasing through
* the odd numbers only (why?), until n is likely prime
*/
// TODO - fill in body
}
/*
*
* Main method.
*
* @param args
* the command line arguments
*/
public static void main(String[] args) {
SimpleReader in = new SimpleReader1L();
SimpleWriter out = new SimpleWriter1L();
/*
* Sanity check of randomNumber method -- just so everyone can see how
* it might be "tested"
*/
final int testValue = 17;
final int testSamples = 100000;
NaturalNumber test = new NaturalNumber2(testValue);
int[] count = new int[testValue + 1];
for (int i = 0; i < count.length; i++) { count[i] = 0;
} for (int i = 0; i < testSamples; i++) {
NaturalNumber rn = randomNumber(test);
assert rn.compareTo(test) <= 0 : "Help!";
count[rn.toInt()]++;
} for (int i = 0; i < count.length; i++) {
out.println("count[" + i + "] = " + count[i]);
}
out.println(" expected value = " + (double) testSamples / (double) (testValue + 1));
/*
* Check user-supplied numbers for primality, and if a number is not
* prime, find the next likely prime after it
*/
while (true) { out.print("n = ");
NaturalNumber n = new NaturalNumber2(in.nextLine());
if (n.compareTo(new NaturalNumber2(2)) < 0) { out.println("Bye!");
break;
} else {
if (isPrime1(n)) { out.println(n + " is probably a prime number" + " according to isPrime1.");
} else {
out.println(n + " is a composite number" + " according to isPrime1.");
}
if (isPrime2(n)) { out.println(n + " is probably a prime number" + " according to isPrime2.");
} else {
out.println(n + " is a composite number" + " according to isPrime2.");
generateNextLikelyPrime(n);
out.println(" next likely prime is " + n);
}
}
}
/*
* Close input and output streams
*/
in.close();
out.close();
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.