  CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's |Store|      CTK Exchange

 Subject: "modular arithmetic and encryption" Previous Topic | Next Topic
 Conferences The CTK Exchange College math Topic #7 Printer-friendly copy Email this topic to a friend Reading Topic #7
Dan Peabody
Charter Member
Oct-30-00, 09:37 AM (EST)   "modular arithmetic and encryption"

 I have been reading Simons singh's Book 'Code book' and found the section on Public key distributon very interesting. In the appendix he describes the method of encoding and decoding a number. In the decoding section he states the following formula:` e x d = 1(MOD(p-1) x (q-1)), e= 7 p=17 & q=11 7 x d = 1(MOD 160) d= 23` He says deducing d is not straight forward, but using Euclids algorithm, d can be calculated.Could you shed some light on probly what is a very trivial problemCheers Dan

Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
672 posts
Oct-31-00, 12:27 PM (EST)    1. "RE: modular arithmetic and encryption"
In response to message #0

 Well, the intention here is to this kind of problems that involve numbers much, much larger than 7 or 160. But as an example, let's solve(1) 7d = 1 (mod 160)The equation is equivalent to(2) 7d - 160x = 1An extension of Euclid's algorithm is used to solve such equations. Here's a solution:(3) 7·23 - 160·1 = 1Subtract (3) from (2):(4) 7·(d - 23) - 160·(x - 1) = 1It thus follows thatd = 23 + 160tx = 1 + 7tsolve (2). Therefore, d = 23 solves (1).All the best,Alexander Bogomolny

Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top

 Conferences | Forums | Topics | Previous Topic | Next Topic
 Select another forum or conference Lobby The CTK Exchange (Conference)   |--Early math (Public)   |--Middle school (Public)   |--High school (Public)   |--College math (Public)   |--This and that (Public)   |--Guest book (Public) You may be curious to visit the old CTK Exchange archive.    