[sf-lug] Ex 11.7 Exponentiation (understandable) & RSA algorithm (not so!)
Asheesh Laroia
asheesh at asheesh.org
Mon Jan 12 09:09:48 PST 2009
On Mon, 12 Jan 2009, jim wrote:
> i'd like verification of my understanding of this:
> "Let d be the reciprocal of e mod r."
> my arithmetic:
> if e is 35 and r is 9111,
> then d = 1/(35%9111) ## == 1/35 == 0.028571429
No, sorry! Reciprocal isn't defined that way in modulo arithmetic. I'm
glad you asked.
Quoth Wikipedia: "In modular arithmetic, the modular multiplicative
inverse of x is also defined: it is the number a such that a*x ≡ 1 (mod
n). This multiplicative inverse exists if and only if a and n are coprime.
For example, the inverse of 3 modulo 11 is 4 because it is the solution to
3*x ≡ 1 (mod 11). The extended Euclidean algorithm may be used to compute
it."
In modular arithmetic, 1/a mod b is an *integer* (iff a and b are
relatively prime).
There are some Java (not JavaScript) calculators for this on the web, e.g.
http://www.mtholyoke.edu/~mpeterso/Applets/CalculatorApplet.html . I
haven't found any working ones in JavaScript yet; perhaps you or another
list member can.
-- Asheesh.
--
You're definitely on their list. The question to ask next is what list it is.
More information about the sf-lug
mailing list