Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » Math Topics » alt.math.recreational.independent

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

Advanced Search

Back to Topic List Back to Topic List  
Richard Foreman

Posts: 1
From: CA
Registered: 3/2/13
Modular reduction of non-integer numbers
Posted: Mar 2, 2013 5:57 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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?



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.