partial mod reduction
Paul Underwood
paulunderwood at mindless.com
Mon Jun 17 01:53:20 CEST 2013
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
More information about the gmp-discuss
mailing list