Cryptographic Applications - Introduction to Cryptography with Java Applets - page 310

But why should we do this? There are two good reasons:

1. We can reduce arithmetic with very large integers to arithmetic with much smaller inte-

gers. If we choose the moduli carefully, we can arrange it so that none of the integers
exceeds the word size of our computer. Thus, we can work quickly with a language's prim-
itive integer type. Integer need to be converted to and from their “large” representation
only for input and output purposes.

2. The arithmetic operations with the decomposed representation are completely indepen-

dent of each other, so they can be done in parallel, significantly reducing operation time
on multiprocessor machines. This is not true with arithmetic using normal radix repre-
sentation.

The IntCRT Class This class represents nonnegative integers as a series of residues
modulo a series of moduli, where the moduli are all unique primes. It adds/multiplies two
IntCRT objects together by adding/multiplying their residues together. The moduli are all
primes not exceeding the largest value for a Java int, and hence the residues do not exceed
the maximum int value either. This allows us to implement the moduli and residues as dual
arrays of primitive type long (we use long since a multiplication of two residues may exceed
the maximum int value). Here is an outline of the IntCRT class, with descriptions inter-
spersed with the code.

import java.util.*;
import java.math.*;
public class IntCRT {

IntCRT objects will consist of

1. The moduli, which are stored in a static array of type long. Once they are set up, they are

used by all subsequently declared IntCRT objects. Since they use the same moduli, they
must all specify the same maximum modulus bit length (the bit length of the product of
all the moduli) to be added or multiplied together.

2. The residues, which are the corresponding residues for each modulus.

3. A variable to record the maximum modulus bit length.

//IntCRT objects are based on a series of ints modulo a series of long primes
//The primes are stored here in this static array-all IntCRT objects will share
this array
static long[] moduli=null;

//A parallel array of residues for each IntCRT object holds its mixed radix
representation
long[] residues=null;

//The maximum size of the modulus - computations must not exceed this modulus
int maxModulusBitLength=0;