Modular reduction of non-integer numbers

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 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?

Hrm, it did not occur to me that moduli could be non-integer. Is your modular exponential algorithm pretty much of the form:

Code:

---

modexp(b, e, m):
    result = 1
    while e > 0:
        if e & 1 == 1:
            result = (result * b) % m
        b = (b * b) % m
        e >>= 1
    return result

---

And does it work correctly with integer base, modulus and exponent?

yes, only in my algorithm I start the return value = to the base, decrement the bit counter by one, and I do the squaring first. But yes, it does give correct results for integers. Ive got a program that generates random numbers and runs all the basic math operations (addition, subtraction, multiplication, division, modular reduction, exponentiation, and modular exponentiation) that compares my results to microsofts BigInteger for correctness. I pretty much leave it running whenever Im not on the computer and it says Im dead on so far.

I checked with microsofts calculator to see how they handled reducing non integer numbers, and the calculator works just as I described above. I havent found much info on the net about reducing non-integer numbers, probably because there isnt much use for them, the math seems correct though, but I still havent figured out how to get the modular exponentiation algorithm to kick out correct results for all values unless I change the algorithm to do the exponentiation first then do the modular reduction, but that route seriously hits the performance.

I am starting to think the algorithm wont work for decimal numbers, but havent figured out why yet.

I think the assumption of the modular exponentiation algorithm is that:

(a*b) % m = [(a % m) * (b % m)] % m

Which is true for integer values. But, for example consider some random-ish values:

a = .81
b = 15.32
m = 3.82

Then:

a % m = .81
b % m = .04

So [(a % m)*(b % m)] % m = .0324 % m = .0324

But

(a * b) % m = (.81*.1532) % m = 12.4092 % 3.82 = .9492

So the relationship does not hold and the fast modular exponential algorithm cannot work.

Thats the conclusion Ive been slowly coming to. I am trying to find some way around it, the beauty of modular exponentiation is that it keeps the variables (relatively) small, thereby speeding it up. Though in all actuality there is probably little use for modular exponentiation of non-integer numbers, I just figured Id have it in place just in case it was needed for something.