
March 1st, 2013, 06:22 AM
#1
Modular reduction of noninteger 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 noninteger 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 noninteger 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?

March 3rd, 2013, 01:24 AM
#2
Re: Modular reduction of noninteger numbers
Hrm, it did not occur to me that moduli could be noninteger. 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?
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

March 3rd, 2013, 07:08 AM
#3
Re: Modular reduction of noninteger numbers
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 noninteger 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.

March 4th, 2013, 11:20 PM
#4
Re: Modular reduction of noninteger numbers
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 randomish 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.
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

March 7th, 2013, 11:11 PM
#5
Re: Modular reduction of noninteger numbers
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 noninteger numbers, I just figured Id have it in place just in case it was needed for something.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
