[sf-lug] Ex 11.7 Exponentiation (understandable) & RSA algorithm (not so!)

[jim]

   i'm sorry too: i still don't get it. for their 
example: 
3 * x = 1 (mod 11) 
their solution is 4. 

   i read this as x = 4, and therefore 
3 * 4 = 1 (mod 11) 

   assuming i'm reading correctly, the mystery is 
how to understand 1(mod 11) == 12 
   i read 1(mod 11) as 1%11 == the remainder after 
11 is divided into 1: integer arithmetic 1/11 == 0 
and 1%11 yields 1. 

   if my assumption is incorrect, then the mystery is 
3 * x = 1(mod 11) 



On Mon, 2009-01-12 at 09:09 -0800, Asheesh Laroia wrote:
> 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.
> _______________________________________________ sf-lug mailing list sf-lug at linuxmafia.com http://linuxmafia.com/mailman/listinfo/sf-lug