[ Pobierz całość w formacie PDF ]

from (∗) that
log2 (2r) ≤ log2(n) log2 2r+1
2
3
110
CHAPTER 26. COMPUTATION OF AN MOD M
or
r ≤ log2(n) r +1.
Hence r = log2(n) . Note that r is the number of times we need to apply
the Division Algorithm to obtain the binary representation n =[ar, . . . , a0]2,
ar = 1. To compute the powers x, x2, x2 , . . . , x2 by successive squaring
requires r = log2(n) multiplications and similarly to compute the product
x2 · xa
2r-1 · · · xa
2 · xa
requires r multiplicatons. So after obtaining the binary representation we
need at most 2r =2 log2(n) multiplications.
Use of a calculator to compute log2(x): To find log2(x) one may use
the formula
1
log2(x) =
ln(x)
ln(2)
or
log2(x) ≈
ln(x)
where ln(x) is the natural logarithm of x. For small values of x it is sometimes
faster to use the fact that r = log2(x) is equivalent to
2r ≤ x2r+1,
that is, r is the largest positive integer such that 2r ≤ x. The Maple command
for log2(x) islog[2](x).
Note that if we count an application of the Division Algorithm and a
multiplication as the same, the above tells us that we need at most 3 log2(n)
operations to compute xn. So, for example, if n =106, then it is easy to see
that 3 log2(n) = 57. So we may compute x1,000,000 with only 57 operations.
Exercise 26.1. Calculate 3 log2(n) for n =2, 000, 000.
Exercise 26.2. Use the binary method to compute 225.
Exercise 26.3. Approximately how many operations would be required to
compute 2n when n =10100? Explain.
Exercise 26.4. Note that 6 multiplications are used to compute 315 using
the binary method. Show that one can compute 315 with fewer than 6 mul-
tiplications. [You will have to experiment.]
2
r
r
r-1
1
1
(0.69314718)
111
Computing an mod m. We use the binary method for exponentiation
with the added trick that after every multiplication we reduce modulo m,
that is, we divide by m and take the remainder. This keeps the products
from getting too big.
Example 26.2. We compute 315 mod 10:
32 =3 · 3 =9 ≡ 9
(mod 10)
34 =9 · 9 =81 ≡ 1
(mod 10)
38 ≡ 1 · 1 ≡ 1 ≡ 1
(mod 10)
∴ 315 =38 · 34 · 32 · 31 ≡ 1 · 1 · 9 · 3 =27 ≡ 7
(mod 10).
Note that 315 ≡ 7 (mod 10) implies that 315 mod 10 = 7. [Recall that on
page 109 we calculated that 315 = 14348907 which is clearly congruent to
7 mod 10, but the multiplications were not so easy.]
Example 26.3. Let’s find 2644 mod 645. It is easy to see that
644 = [1, 0, 1, 0, 0, 0, 0, 1, 0, 0]2
That is, 644 = 29 +27 +22 = 512 + 128 + 4. Now by successive squaring and
reducing modulo 645 we get
22 =2 · 2 =4 ≡ 4
24 ≡ 4 · 4 =16 ≡ 16
(mod 645)
(mod 645)
28 ≡ 16 · 16 = 256 ≡ 256
(mod 645)
216 ≡ 256 · 256 = 65, 536 ≡ 391
232 ≡ 391 · 391 = 152, 881 ≡ 16
264 ≡ 16 · 16 = 256 ≡ 256
2128 ≡ 256 · 256 = 65, 536 ≡ 391
2256 ≡ 391 · 391 = 152, 881 ≡ 16
2512 ≡ 16 · 16 = 256 ≡ 256
Now
2644 =2512 · 2128 · 24,
hence
(mod 645)
(mod 645)
(mod 645)
(mod 645)
(mod 645)
(mod 645).
2644 ≡ 256 · 391 · 16
(mod 645).
112
CHAPTER 26. COMPUTATION OF AN MOD M
So
256 · 391 = 100099 ≡ 121
(mod 645)
and
121 · 16 = 1936 ≡ 1
(mod 645)
so we have 2644 ≡ 1 (mod 645). Hence 2644 mod 645 = 1.
Exercise 26.5. Calculate 2513 mod 10.
Exercise 26.6. Calculate 2517 mod 100.
Exercise 26.7. If you multiplied out 2517, how many decimal digits would
you obtain? [See Exercise 4.3 on page 14.]
Exercise 26.8. Note that on page 96 we calculated 12347865435 mod 11 with
very few multiplications.
12347865435 mod 12?
Why can we not use that method to compute
Chapter 27
The RSA Scheme
In this chapter we discuss the basis of the so-called RSA scheme. This is
the most important example of a public key cryptographic scheme. The RSA
scheme is due to R. Rivest, A. Shamir and L. Adelman
and was discovered
by them in 1977. We show how to implement it in more detail later using
Maple. Here we give the number-theoretic underpinning of the scheme.
We assume that the message we wish to send has been converted to an
integer in the set Jm = {0, 1, 2, . . . , m- 1} where m is some positive integer
to be determined. Generally this is a large integer. We will require two
functions:
E : Jm → Jm
(E for encipher)
and
D : Jm → Jm
(D for decipher).
To be able to use D to decipher what E has enciphered we need to have
D(E(x)) = x for all x ∈ Jm. To show how m, E, and D are chosen we first
prove a lemma:
Lemma 27.1. Let p and q be any two distinct primes and let m = pq. Let
e and d be any two positive integers which are inverses of each other modulo
φ(m). Then
xed ≡ x
(mod m)
for all x.
1
1
A copy of the paper “A Method for Obtaining Digital Signatures and Public-Key
Cryptosystems” may be downloaded from http://citeseer.nj.nec.com/rivest78method.html
113
114
CHAPTER 27. THE RSA SCHEME
Proof. By Theorem 22.6, φ(m) =(p - 1)(q - 1). Since ed ≡ 1 (mod φ(m))
we have ed - 1 =kφ(m) =k(p - 1)(q - 1) for some k. Note k 0 unless
ed = 1 in which case the theorem is obvious. So we have
(∗)
ed = kφ(m) +1=k(p - 1)(q - 1) + 1
for some k 0.
Now by Fermat’s Little Theorem, if gcd(x, p) = 1 we have xp-1 ≡ 1
(mod p) and raising both sides of the congruence to the power (q - 1)k we
obtain:
x(p-1)(q-1)k ≡ 1
(mod p)
and multiplying both sides by x we have
x(p-1)(q-1)k+1 ≡ x [ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • moje-waterloo.xlx.pl

    •