|
|Store|
|
|
|
|
|
|
|
CTK Exchange
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 problem Cheers 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 = 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 |
|
|
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]
|
Advertise
|
Printer-friendly copy
Email this topic to a friend