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

Thomas DiZoglio tomdiz at yahoo.com
Mon Jan 12 10:28:34 PST 2009

```I don't think that is an equal sign. It has 3 horizontal lines, not two. Not sure what that means, but think it is "inverse".
-------------------
t0md

--- On Mon, 1/12/09, jim <jim at well.com> wrote:

> From: jim <jim at well.com>
> Subject: Re: [sf-lug] Ex 11.7 Exponentiation (understandable) & RSA algorithm (not so!)
> To: "Asheesh Laroia" <asheesh at asheesh.org>
> Cc: sf-lug at linuxmafia.com
> Date: Monday, January 12, 2009, 10:13 AM
> 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
> >
> > 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
>
>
> _______________________________________________
> sf-lug mailing list
> sf-lug at linuxmafia.com
> http://linuxmafia.com/mailman/listinfo/sf-lug

```