As you saw in the lecture, using the RSA encryption scheme involves mathematics
ID: 3866918 • Letter: A
Question
As you saw in the lecture, using the RSA encryption scheme involves mathematics with large numbers. The key to the security of the RSA scheme is that it is mathematically time consuming to factor a very large number into 2 prime-number factors. Any integer of hundreds or even thousands of bits involves values way beyond the ability of the Java integer or long integer types to manage. But it must be done and it must be done quickly in order for the method to be useful. This exercise is intended to give you an appreciation of the difficulty of the solution to that problem.
Since very large numbers (Ex: integers of several hundred digits) are completely beyond the ability of Java to manage, you will create the capability to perform arithmetic on such values. The exercise will enable you to both add and multiply very large integer numbers. Addition and multiplication should be enough for relatively reasonably-sized numbers since we can raise a number to a very large power by repeated multiplication.
The result will be a class named intValue (int and Integer are already used by Java) which will exist for the purpose of containing a value of indeterminate but possibly vary large length. Since the numbers are too long to allow their implementation as Java built-in types, we will use the Java String or StringBuilder to hold the digits of a number. This will enable us to handle numbers of tens or even hundreds of digits since the String data type is expandable up to the limit of RAM.
Since a class should contain the capability for handling and manipulating its own objects, the intValue class will also be able to add and multiply intValue objects and raise an intValue to a power (by using its own capability for multiplication).
Sample methods for these capabilities may be;
· public intValue multiply(intValue n);
o allows an intValue object to multiply its own value by the value of another such object (n) and returns a new intValue object containing the result.
· public intValue add(intValue n);
o allows an intValue object to add its own value to the value of another such object (n) and returns a new intValue object containing the result.
Testing:
The main program will test by allowing the user to enter numbers of any size and request addition, multiplication or exponentiation. The following website
wolframalpha.com
contains the capability for adding and multiplying numbers of inordinately long digit strings. Use it to insure that your program is operating correctly.
You should have a list of tests showing a selection of values to be manipulated and the correct results of the additions, multiplications and exponentiations. Please also be prepared to show me how you arrived at the correct values with which you evaluated your test.
If this kind of stuff intrigues you, you might want to investigate several algorithms for multiplication of large numbers which are faster than the usual grade-school definition of multiplication. One of the simplest of these, although not quite the fastest, is Karatsuba’s algorithm, originally published in 1962.
Explanation / Answer
import java.util.Scanner;
public class intValue {
String value;
public intValue(String value) {
this.value = value;
}
public intValue() {
this.value = "";
}
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public intValue add(intValue other) {
String str1 = getValue();
String str2 = other.getValue();
StringBuilder output = new StringBuilder();
int l1 = str1.length();
int l2 = str2.length();
int len = 0;
// make the length of both numbers same by prepending 0s on shorter number
if(l1 > l2) {
len = l1;
str2 = prepend(str2, 0, l1 - l2);
} else if(l1 < l2) {
len = l2;
str1 = prepend(str1, 0, l2 - l1);
} else {
len = l1;
}
int carry = 0;
for(int i=len-1; i>=0; i--) {
// add the corresponding digits with carry..
int result = (str1.charAt(i) - '0') + (str2.charAt(i) - '0') + carry;
// check if carry need to be forwarded to next step
if(result > 9) {
result -= 10;
carry = 1;
} else {
carry = 0;
}
output.insert(0, String.valueOf(result));
}
// add carry if remaining
if(carry == 1) {
output.insert(0, String.valueOf(carry));
}
return new intValue(output.toString());
}
/* 1234
* X 56
* =====
* 7404
* 6170X
* =====
* 69104
*
* The above is the algorithm
* It uses the above method to add two int values together
*/
public intValue multiply(intValue other) {
String value = getValue();
intValue result = new intValue();
int len = value.length();
int digitsMultiplied = 0;
for(int i=len-1; i>=0; i--) {
// multiply the second intValue with the digit at ith position in first number
intValue multiplyResult = singleDigitMultiply(other, value.charAt(i)-'0');
// add the zeroes at the last depending upon how many digits have been multiplied
multiplyResult = new intValue(append(multiplyResult.toString(), 0, digitsMultiplied++));
// add this result to main result
result = result.add(multiplyResult);
}
return result;
}
public boolean isZero() {
for(int i=0; i<value.length(); i++) {
if(value.charAt(i) != '0') {
return false;
}
}
return true;
}
public intValue reduceByOne() {
if(isZero()) {
return this;
}
String str = this.value;
char[] chs = str.toCharArray();
for(int i=chs.length-1; i >=0; i-- ) {
char ch = chs[i];
if((ch-'0') > 0) {
chs[i] = (char) ('0' + ch - '1');
return new intValue(String.valueOf(chs));
} else {
chs[i] = '9';
}
}
return new intValue(String.valueOf(chs));
}
public intValue raiseToPower(intValue power) {
intValue times = new intValue(power.getValue());
intValue result = new intValue(this.getValue());
while(!times.isZero()) {
result = result.multiply(this);
times = times.reduceByOne();
}
return result;
}
private static intValue singleDigitMultiply(intValue other, int digit) {
StringBuilder output = new StringBuilder();
String value = other.getValue();
int carry = 0;
for(int i=value.length()-1; i>=0; i--) {
int result = (value.charAt(i) - '0') * digit + carry;
if(result > 9) {
carry = result/10;
result = result % 10;
} else {
carry = 0;
}
output.insert(0, String.valueOf(result));
}
// add carry if remaining
if(carry > 0) {
output.insert(0, String.valueOf(carry));
}
return new intValue(output.toString());
}
private static String append(String number, int digit, int times) {
for(int i=0; i<times; i++) {
number += String.valueOf(digit);
}
return number;
}
private static String prepend(String number, int digit, int times) {
for(int i=0; i<times; i++) {
number = String.valueOf(digit) + number;
}
return number;
}
@Override
public String toString() {
return value;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.print("Enter first value: ");
intValue i1 = new intValue(s.next());
System.out.print("Enter second value: ");
intValue i2 = new intValue(s.next());
System.out.println(" adding " + i1 + " and " + i2);
System.out.println(i1.add(i2));
System.out.println(" multipling " + i1 + " and " + i2);
System.out.println(i1.multiply(i2));
System.out.println(" " + i1 + " raise to power of " + i2);
System.out.println(i1.raiseToPower(i2));
s.close();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.