I am trying to implement RSA for my FPGA.



And there is a inverse modulo operation that is bugging me for 3 days now, problem is--

(551)^-1 mod 1517 = 1082 !!

i dont know how, but this is the result.

taken from--
"An efficient Montgomery exponentiation Algorithm for cryptographic applications"--p 462
http://www.mii.lt/Informatica/pdf/INFO600.pdf (152 KB)

first, i cant understand how he got that result, second i cant find a algorithm for multiplicative
inverse with modular operation. and So, i am in big big trouble.


In the following pdf, there is a efficient solution for inverse--

"Bit serial Systolic architectures for multiplicative inversion and division" (p -51)
http://etd.uwaterloo.ca/etd/akdanesh2005.pdf (879 KB)

since, i dont know how

(551)^-1 mod 1517 = 1082 !!

was computed, i couldn't figure out how to debug and what to expect.

please please help if possible.