Oskar Sandberg wrote:
> Yes, I have no issues with writing the modular reduction myself. The problem
> is
> that the standard mpi library that comes with perl is way to slow (130 seconds
> for a normal exponentiation using reduction), and that the plugin ones are
> either borked or do not support bit shifts (needed for mod reduction).
>
> I'm guessing you are using an library for python, not writing mpi code
> yourself...
Python has built in support for arbitarily long integers, so the main
problem was simply converting from the binary format that Java sends into
something Python can use. You don't really need bit shifting for mod
reduction - integer division and a modulos operator are enough. Python has
a function divmod(a,b) that returns "a / b" and "a % b". The following
function calculates a to the power of b mod n:
def powmod(a, b, n):
result = 1L # long integer for arbitarily large integer math
while b > 0:
l, r = divmod(b, 10L)
result = (result * pow(a, r)) % n
a = pow(a, 10) % n
b = l
return result
based on the formula:
l
b (10l + r) r 10)
a = a = a * (a
The algorithms in Applied Cryptography are faster, but this algorithm works
decently too.
--
Itamar S.T. itamar at maxnm.com
_______________________________________________
Freenet-dev mailing list
Freenet-dev at lists.sourceforge.net
http://lists.sourceforge.net/mailman/listinfo/freenet-dev
