Big-Integer Operations In JAVA

Problem Description:

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);

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);

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 Karatsubas algorithm, originally published in 1962.