1. 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).  2.

3. 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.  4. 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.  5. if anyone else will have problems understnading extended euclid, here is the link

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

finally got it right  6. 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".  7. 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.

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  