
Store







CTK Exchange
Dan Peabody
Charter Member

Oct3000, 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(p1) x (q1)), 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 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 


alexb
Charter Member
672 posts 
Oct3100, 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 = 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 
Printerfriendly page  Edit 
Reply 
Reply With Quote  Top 


You may be curious to visit the old CTK Exchange archive.
Front page
Contents
Copyright © 19962018 Alexander Bogomolny
[an error occurred while processing this directive]

Advertise
