March 1st, 2013, 05:22 AM
Modular reduction of non-integer numbers
I am working on a big number library, and noticed that when the modulus isnt a whole number and I run it through the modular expnentiation routine it doesnt give the same result as when I compute the exponentiation as a whole first then reduce. For example:
537330187808824024 ^ 29 mod 1384310071314823439.3 == 23811382621880482.97672704
when run through the modular exponentiation routine, but if I compute the exponentiation as a whole first then reduce it I get:
x == 537330187808824024 ^ 29
x mod 1384310071314823439.3 == 841533308780060155.3
from what little Ive found on the web about reducing non-integer numbers (and apparantly the way Microsoft solves it) the reduction would be equivalent to:
A mod B == A - X * B where X= flooring (A / B).
The way I handled the reduction of non-integer numbers was by aligning the decimal points of the numbers by multiplying the number with fewer decimal places by 10^(the difference in decimal places of the two numbers).
using the above numbers again if I were to square 537330187808824024 then reduce by 841533308780060155.3, the result of the squaring would be multiplied by 10 first then reduced by 8415333087800601553 (without the decimal point). the result of this reduction would have one decimal place (862723789466456803.0). This appears to give correct results with straight modular reduction, but gives me wonky results when applied to modular exponentiation.
Am I not aproaching the solution correctly? I am using the repeated square and multiply algorithm for modular exponentiation, is there something about the algorithm that would that requires only using integer modulus?
Click Here to Expand Forum to Full Width
This is a CodeGuru survey question.