Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Modular reduction of non-integer numbers
Replies: 0

 Richard Foreman Posts: 1 From: CA Registered: 3/2/13
Modular reduction of non-integer numbers
Posted: Mar 2, 2013 5:57 AM

Hello all,

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 exponentiation 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 requires only using integer modulus?