CTK Exchange
Front Page
Movie shortcuts
Personal info
Reciprocal links
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot

CTK Exchange

Subject: "modular arithmetic and encryption"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #7
Reading Topic #7
Dan Peabody
Charter Member
Oct-30-00, 09:37 AM (EST)
Click to EMail Dan%20Peabody Click to send private message to Dan%20Peabody Click to add this user to your buddy list  
"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 problem

Cheers Dan

  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
Charter Member
672 posts
Oct-31-00, 12:27 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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 = 1

An extension of Euclid's algorithm is used to solve such equations. Here's a solution:

(3) 7·23 - 160·1 = 1

Subtract (3) from (2):

(4) 7·(d - 23) - 160·(x - 1) = 1

It thus follows that

d = 23 + 160t
x = 1 + 7t

solve (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

You may be curious to visit the old CTK Exchange archive.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]

New Books
Second editions of J. Conway's classic On Numbers And Games and the inimitable Winning Ways for Your Mathematical Plays