CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2
  1. #1
    Join Date
    Aug 2009
    Location
    Finally back in Alaska
    Posts
    141

    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

  2. #2
    Join Date
    Aug 2009
    Location
    Finally back in Alaska
    Posts
    141

    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
  •  





Click Here to Expand Forum to Full Width

Featured