-
October 14th, 2011, 12:36 AM
#1
Help with a modular reduction algorithm
Hello all,
I have a big number library consisting of 3 classes (BigInteger, BigDecimal, and BigFraction) that Ive been using for about 4 years now. I am finally getting rid of the java part (which I use to hold the actual number) and replacing it with an array of Integers, anyhow, I have all the basic operators working correctly(add, subtract, multiply, divide, exponentiation), but I am having a hard time with modular reduction. I am trying to implement the algorithms in handbook of applied cryptography, and I have them all working to the point they match the output of the texts, however, the output they give is not what I am looking for. For Example:
in the montgomery reduction the output is not T mod M but TR(-1) mod M (the multiplicative inverse of R times T mod M) which is not equal to T mod M. To use the example given in the book:
M=72639
T=7118368
so my point is 7118368 mod 72639 =72385
but the algorithm output TR(-1) mod M which using the above numbers gives 39796
Now, I know if I multiply the output of the algorithm by R (not the multiplicative inverse) mod M then it gives the correct value, however, how do I reduce the product of TR by M when M is in array format and too big to fit in any standard value type? I have tried running the output from the Montgomery reduction through the Modular Multiplication method but that does not give the correct result. I also have the Barret method implemnted, but all of those methods give the exact same results.
I know .net 4 has a bignumber class, but it doesnt have all the functionality mine does and all of my algorithms are allready written with mine and Im not inclined to rewrite everything. Besides, the only aspect the .net classes have over mine is speed which runs about 2 times faster then my implementation, however, I can live with that.
As a side note, I noticed it looks like people abandon quite a few posts in this forum, but I have been using these forums for a long time, I will be back, and even if I dont find an answer here (only happened once so far) I still really do appreaciate any help.
Thanks in advance
-
October 14th, 2011, 02:49 AM
#2
Re: Help with a modular reduction algorithm
Well I solved it partially at least, the Barret algorithm does output the correct result but I made a mistake in it. The montgomery algorithm still stands as a problem for me though because I was wanting to implement it for the modular exponentiation since its supposed to be fatser
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
|