Notices
Results 1 to 6 of 6

Thread: montgomery reduction

  1. #1 montgomery reduction 
    Forum Freshman
    Join Date
    Feb 2011
    Posts
    29
    I am looking to understand this. I need to calculate large ab mod c as fast as possible with as little memory as i can.
    Could someone explain me step by step this? I dont understand much from wiki, math was never my strong point and its written for someone who already knows it. Im lost while reading it (also english isnt my native language).


    Reply With Quote  
     

  2.  
     

  3. #2 Re: montgomery reduction 
    Forum Ph.D.
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    846
    Quote Originally Posted by phy_11
    I am looking to understand this. I need to calculate large ab mod c as fast as possible with as little memory as i can.
    Could someone explain me step by step this? I dont understand much from wiki, math was never my strong point and its written for someone who already knows it. Im lost while reading it (also english isnt my native language).
    I assume ab means a times b. Step 1 calculate p=ab. Step 2 divide p by c and keep d the integer part of the quotient. Step 3 compute x=p-dc. x is the result you want.


    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Feb 2011
    Posts
    29
    Ive managed to understand it on my own. And this what you propose isnt montgomery reduction. The whole point of it is to make a modulo without making any division (just shifts).

    However now its time for extended Euclids.
    I dont know how to calculate inverse modulo. I understand basic Euclid, but not extended.

    17^-1 mod 99 <=> 17 * x mod 99 = 1.
    Find x.
    Reply With Quote  
     

  5. #4  
    Forum Freshman
    Join Date
    Feb 2011
    Posts
    29
    if anyone else will have problems understnading extended euclid, here is the link

    http://marauder.millersville.edu/~bi.../exteucex.html

    finally got it right
    Reply With Quote  
     

  6. #5  
    Forum Ph.D.
    Join Date
    Jul 2008
    Location
    New York State
    Posts
    846
    Quote Originally Posted by phy_11
    Ive managed to understand it on my own. And this what you propose isnt montgomery reduction. The whole point of it is to make a modulo without making any division (just shifts).

    However now its time for extended Euclids.
    I dont know how to calculate inverse modulo. I understand basic Euclid, but not extended.

    17^-1 mod 99 <=> 17 * x mod 99 = 1.
    Find x.
    I have never heard of or seen the term "montgomery reduction".
    Reply With Quote  
     

  7. #6  
    Forum Freshman
    Join Date
    Feb 2011
    Posts
    29
    its a method to calculate modular exponent without making modulo.
    instead of making a*b mod n thousands of times, you do:
    convert a and b to mont~ form. its a*r mod n, b*r md r, where r is 2^number of bits of n.

    then you make a1*b1. After that, if LSB is 1 you add n. otherwise not. times 2^r length. each time shift n left. so instead of modulo you have addition.
    compare steps are replaced by logocal and (or test in hardware, wich is read-only and) and subtracts by additions.
    At the end, convert mont~ to normal by a1*invmod r mod n.

    in theory its supposed to speed up modular exponentation, but im having doubts about it. I havent implemented it yet because i dont understand it quite yet (i know what to do, i just dont know why it does work). But from what i see i dont think its that much good.

    Normally, in straight forward method i would usemodulo instead of additions.
    modulo is diffrent in way, that i do:

    times modulus base length - modulus length + 1
    compare
    subtract
    i shift double precision each time, it also cost time.

    and in montgomery multiplicaiton:
    times modulus length
    test bit
    add

    so its ocmpare vs bit test. compare is done from highest to lowest word, and propably i will have a result after first one because modulus is usually filled to last MSB. I dont know. Im interested in fast and memory efficient way of performing modular exponent on modulus length > 4096 bits.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •