partial mod reduction

[Paul Underwood]

I had an idea for partial mod reduction, equivalent to 1 schoolbook multiplication during exponentiation, to be followed by full reduction at the end of the loop. Two initial full mod reductions are needed. Optionally, a table of such initial values could be done, the size of which is log_2(W) where W is the number of limbs of n. The latter method would allow Karasuba/Toom-Cook to be done for some of the bigger multiplications.

Working in base 1000 for example, suppose the modulus is n=12,345,678,910,111.

1. Compute 1,000,000,000,000,000 (mod n)

2. Compute 1,000,000,000,000,000,000 (mod n)

3. During the exponentiation loop maintain partial mods, by multiplying the top word of the result of multiplication/squaring by the value "2." shifted and adding it to the mult. result. and so on with the next word down to the limb size of W+1, and then multiply the {W+1}st word by "1." and adding to the lower W limbss, until there are W limbs left.

I have written the two initial version in JavaScript:

ArrayObject.prototype.partialModReduce = function( thou, mill, nLength ) {
 var i;
 var j;
 var carry;
 var temp;
 var aValue;
 var theLength;
 var theIndex;
 var thouArray = thou.array;
 var millArray = mill.array;
 var thisArray = this.array;
 for( i = this.LEN - 1; i > nLength; i-- ) {
 while( thisArray[i] > 0 ) {
 carry = 0;
 theLength = mill.LEN;
 theIndex = i - nLength - 1;
 aValue = thisArray[i]
 for( j = 0; j < theLength; ) {
 temp = aValue * millArray[j++] + thisArray[theIndex] + carry;
 carry = ~~( temp / 67108864 );
 thisArray[theIndex++] = temp - carry * 67108864;
 }
 thisArray[i] = 0; 
 while( carry ) {
 temp = thisArray[theIndex] + carry;
 carry = ~~( temp / 67108864 );
 thisArray[theIndex++] = temp - carry * 67108864;
 }
 }
 }
 while( thisArray[nLength] ) {
 carry = 0;
 theLength = thou.LEN;
 aValue = thisArray[nLength];
 for( j = 0; j < theLength; ) {
 temp = aValue * thouArray[j] + thisArray[j] + carry;
 carry = ~~( temp / 67108864 );
 thisArray[j++] = temp - carry * 67108864; 
 }
 thisArray[nLength] = 0;
 j = thou.LEN; 
 while( carry ) {
 temp = thisArray[j] + carry;
 carry = ~~( temp / 67108864 );
 thisArray[j++] = temp - carry * 67108864
 }
 }
 i = this.LEN;
 while( ( !thisArray[i - 1] ) && ( i > 1 ) ) {
 i--;
 }
 this.LEN = i;
}

"thou" is like "1." above and "mill" is like "2." above.

Is it any better than what GMP uses now?

Paul