Protocols, Discrete Log,

and Diļ¬e-Hellman

The past, at least, is secure.

Daniel Webster (1782ā“1852) American politician

2.1 Cryptographic Protocols

In this chapter, we will require increasingly more number theoretic results.

Appendix C on page 212 is provided as a quick reminder and ļ¬nger-tip reference

for the reader. We begin this section with a formalization of certain terms; some

of which we have been using in Chapter 1. First of all, an entity is any person,

such as Bob, Alice, Eve, or Mallory introduced in Chapter 1, or a thing, such as a

computer terminal, which sends, receives, or manipulates information. We have

used the term communication channel, which we now deļ¬ne to be any means of

communicating information from one entity to another. If two entities, such as

Alice and Bob, are communicating and a third entity, such as Eve or Mallory,

tries to interfere, passively or actively, with the data over the communication

channel, then that third entity is called an adversary or opponent. A secure

channel is one that is not physically accessible to an adversary. An unsecured

channel is one from which entities other than those for whom the information

was intended, can delete, insert, read, delay, or reorder data. A cryptosystem

is said to be secure (against eavesdropping) if an adversary, such as Eve, who

eavesdrops on a channel which is sending cryptograms, gains nothing over an

entity which does not listen to the communication channel.

A protocol, in general human terms, may be regarded as prearranged eti-

quette, such as understood behaviour at a formal dinner party. On the other

hand, a cryptographic protocol is an algorithm, involving two or more entities,

using cryptography, designed to achieve a security goal. A security goal will

involve issues of authentication (see Chapter 7), privacy (see Chapter 9), and

secrecy. A protocol, by deļ¬nition, can be no more secure than the underlying

33

Ā© 2003 by CRC Press LLC

34 2. Protocols, Discrete Log, and Diļ¬e-Hellman

cryptosystem.

Of course there are attacks against protocols, which may be any of the types

that we studied in Section 1.3. For instance, Eve could eavesdrop and learn the

key in a symmetric-key protocol, and if Mallory knows the key, he can substitute

or alter messages. We may also use public-key encryption for protocols, about

which we will learn in Chapter 3. We will leave this issue for now and turn to

the details of protocols in general.

Before setting out to classify protocols, we need to discuss why protocols are

useful and what is necessary to make them work. One of the most important

reasons for using cryptographic protocols is to allow us to examine means by

which dishonest entities can try to cheat, thereby giving us methods for devel-

oping protocols to thwart them. We need to do this since computer protocols

are not āface-to-faceā so the lack of personal presence means that it is diļ¬cult

to thwart cheaters.

In order for protocols to operate properly, we assume that all entities in

the protocol are aware in advance of the (unequivocal) steps necessary for the

protocol to function. Moreover, every entity involved must be in agreement to

follow these steps, and to complete the protocol to the ļ¬nish.

With these conventions in mind, we proceed with a detailed classiļ¬cation.

q Classiļ¬cation of Cryptanalytic Protocols

There are three kinds of protocols that we now outline. In order to describe

the ļ¬rst type of protocol, we introduce another entity in our cryptographic cast

of characters: Trent, the trusted arbitrator.

x Arbitrated Protocols

This type of protocol relies on Trent who is trusted not to render preferential

treatment to Alice, Bob, or any other participants. Trent has no allegiances

to any of the entities involved in the protocol and has no particular reason

to complete the protocol. (Think of Trent as a disinterested lawyer.) Thus, a

characteristic of this type of protocol is that all entities can accept, not only that

what is done is correct, but also that their portion of the protocol is complete.

An example of this type of protocol is given as follows.

The following type of protocol is ideally suited for identiļ¬cation of an owner,

Alice (who has a PIN or password S) of a credit card, ID card, or computer

account. It does so by allowing Alice to convince a merchant, Bob, of knowledge

of S without revealing even a single bit of S. This was introduced in [88] by

Fiat and Shamir in 1987 as an authentication and digital signature scheme (see

Chapter 7), and it was modiļ¬ed in [85]ā“[86] to an identiļ¬cation protocol. (For

a very intriguing story involving patents, the military, and this protocol, see

[132].)

s Feige-Fiat-Shamir Identiļ¬cation Protocol ā” Simpliļ¬ed Version

In the following protocol, Alice has to prove her identity, via demonstration

of knowledge of a secret, to Bob.

Ā© 2003 by CRC Press LLC

2.1. Cryptographic Protocols 35

Setup Stage

(1) Trent chooses a modulus n = pq, where p and q are large primes of roughly

the same size to be kept secret. (We will formally study these types, called

RSA moduli in Chapter 3.) Also, a parameter a ā N is chosen.

(2) Next, Alice and Bob, respectively, randomly select secret natural numbers

sA ,sB ā¤ n ā’ 1, with gcd(sA sB , n) = 1. Then they compute, respectively,

the smallest natural numbers tA and tB such that tA ā” s2 (mod n) and

A

tB ā” s2 (mod n). They register their secrets sA and sB with Trent,

B

whereas tA and tB do not need to be kept secret.

Protocol

Execute the following steps.

(1) Alice selects an m ā N, called a commitment, such that m ā¤ n ā’ 1 and

sends w ā” m2 (mod n), called the witness, to Bob.

(2) Bob chooses c ā {0, 1}, called a challenge, and sends it to Alice.

(3) Alice computes r ā” msc (mod n), called the response, and sends it to Bob.

A

(4) Bob computes r2 modulo n. If r2 ā” wtc (mod n), then reset aā™s value to

A

a ā’ 1 and go to step (1) if a > 0. If a = 0, then terminate the protocol

with Bob accepting the proof. If r2 ā” wtc (mod n), then terminate the

A

protocol with Bob rejecting the proof.

Remark 2.1 This protocol is an example of what is known as a zero-knowledge

proof of identity, which we will not cover in this text (see [165] for details on the

subject of zero-knowledge in general). The Feige-Fiat-Shamir Protocol is also

what is called a zero-knowledge proof of knowledge of a modular square root of

tA , namely, the secret sA . (See Exercise 2.1.)

Suppose that Mallory tries to impersonate Alice. Some methods can have a

50% chance of fooling Bob in any one round as follows. Suppose that Mallory

picks an m so that 0 < m < n ā’ 1. If Mallory decides he will defeat Bobā™s

selection of c = 0, he sends w = m2 . If he decides he will defeat Bobā™s selection

of c = 1, he sends w = m2 tā’1 . Now, if Mallory sends w = m2 , having guessed

A

that Bob will send c = 0, and Bob does challenge with c = 0, then Mallory

sends r = m, and Bob computes r2 ā” m2 ā” wt0 (mod n). This passes step (4).

A

If Mallory sends w = m2 tā’1 and Bob challenges with c = 1, then Mallory sends

A

r = m and Bob computes r2 ā” m2 ā” m2 tā’1 t1 ā” wt1 (mod n), and this passes

AA A

step (4). However, if Mallory sends w = m2 (guessing Bob will challenge with

c = 0) and Bob challenges with c = 1, then Mallory cannot produce an r that

will fool Bob. In this case, Mallory needs an r so that r2 ā” wtA (mod n) or

r2 ā” m2 tA (mod n). If he could ļ¬nd such an r, then x ā” rmā’1 (mod n) would

Ā© 2003 by CRC Press LLC

36 2. Protocols, Discrete Log, and Diļ¬e-Hellman

be a solution to x2 ā” tA (mod n), but we are assuming that he cannot solve this

congruence. Also, if Mallory sends w = m2 tā’1 and Bob challenges with c = 0,

A

then Mallory needs an r so that r2 ā” w ā” m2 tā’1 (mod n). If he can ļ¬nd such

A

an r, then x ā” mrā’1 (mod n) would solve x2 ā” tA (mod n). Hence, if Mallory

guesses which c Bob will send he can fool Bob for that round. But if he guesses

wrong, he will not be able to provide an r that will pass step (4). Furthermore,

Mallory cannot do any better than this. It is not hard to see that there is no w

Mallory can send that will allow him to reply with an appropriate r, whether

Bob sends c = 0 or c = 1. Suppose that there is such a w. Then if Bob sends

c = 0, Mallory needs to have ready an r = r0 so that r0 ā” w (mod n), and in

2

case Bob sends c = 1, he needs to have an r = r1 with r1 ā” wtA (mod n). Yet,

2

ā’1 ā’1

if r0 exists, (r1 r0 )2 ā” tA (mod n), so if Mallory really had this r0 and r1 , he

ā’1

could compute x ā” r1 r0 (mod n), and he could solve x2 ā” tA (mod n), which

we are assuming to be impossible. The bottom line is that when Mallory picks

a witness, he can decide whether his witness will defeat c = 0 or whether it will

defeat c = 1. He can always pick a witness that will work against whichever

one of these he wants, but he cannot pick a witness that will work against both.

Only Alice can do that. (See Exercise 2.2.)

The following protocol classiļ¬cation requires the introduction of another in

our cast of cryptographic characters, Judy, the adjudicator.

x Adjudicated Protocols

This is actually a variation of an arbitrated protocol. If all entities follow

the sequence of steps in the protocol and no entity believes that any other

entity is cheating, then an adjudicator is not needed. However, if cheating is

suspected by any entity, then Judy the adjudicator comes into play to analyze

the dispute, render a ruling on who is right, and determine what punishment

should be dispensed to the entity in the wrong. For instance, consider the āreal

lifeā scenario where Alice and Bob agree that Alice will sell her car to Bob. First,

Alice gives the car keys to Bob, who gives her a cheque for the car. If the keys

are fake or the cheque is fraudulent, then they go before Judy the adjudicator

to present their cases. Judy rules on the evidence presented and the entity who

cheated is ļ¬ned or imprisoned. Thus, the penalty, if severe enough, may prevent

cheating and the need for Judy. However, there is a means to work things out

by another type of protocol that involves no third entity.

x Self-Enforcing Protocols

These are the most desirable protocols since they are designed to make cheat-

ing virtually impossible. We need neither Trent not Judy, since any cheating is

immediately detected by other entities participating in the protocol. Cheaters

gain no advantage by not following the protocol. Hence, the protocols are self-

enforcing.

As an illustration, suppose that Alice and Bob were married but got a di-

vorce, now live in diļ¬erent towns, and want to decide who gets the car by the

Ā© 2003 by CRC Press LLC

2.1. Cryptographic Protocols 37

ļ¬‚ip of a coin over the telephone. Given that they no longer trust each other and

have no trusted third party, such as Trent, they need to ensure that the protocol

is fair and not open to either of them cheating. They do this as follows.

s Coin Flipping by Telephone

There are numerous ācoin ļ¬‚ipping by telephoneā protocols, the ļ¬rst being

given by Blum in [30] (and we will re-visit the ācoin ļ¬‚ippingā notion several times

throughout the text). However, we present one here that is diļ¬erent from that

typically presented. The following uses what are called Blum integers, which

are natural numbers of the form n = pq where p ā” q ā” 3 (mod 4) are primes.

In the following, Bob is going to make a guess. If he is correct, he gets the car.

If not, Alice gets the car. Also, in each congruence modulo n, we assume that

the least positive residue is selected for the values discussed.

(1) Alice selects a Blum integer n = pq, and a random x ā N such that

gcd(x, n) = 1, then computes x0 ā” x2 (mod n) and x1 ā” x2 (mod n).

0

Then Alice reveals n and x1 to Bob.

(2) Bob guesses the parity of x and tells Alice his guess.

(3) Alice tells Bob what p, q, x, and x0 happen to be.

(4) Bob veriļ¬es that n is a Blum integer, then computes both x0 ā” x2 (mod n)

and x1 ā” x2 (mod n), and thereby is able to conļ¬rm that x is indeed what

0

Alice selected.

Analysis: Let Qn denote the set of all x ā (Z/nZ)ā— (the group of units

modulo n ā” see (C.12) in Appendix C on page 215), such that x is a quadratic

residue modulo n. Thus, the conditions in step (1) mean that both x0 ā Qn (the

condition: x0 ā” x2 (mod n)); and x1 ā Qn (the condition: x1 ā” x2 (mod n)).

0

Exercise 2.1 shows that of the four square roots x0 of x1 in Qn modulo n, exactly

one of them is also in Qn . This square root is often called the principal square

root of x0 modulo n. This guarantees the uniqueness of x. In fact, the function

f : Qn ā’ Qn , given by f (y) ā” y 2 (mod n) is a bijection with inverse,

f ā’1 (y) ā” y ((pā’1)(qā’1)+4)/8 (mod n).

If n is not a Blum integer, however, this uniqueness evaporates. In this case it

is possible for Alice to ļ¬nd an integer x2 such that x2 ā” x2 ā” x0 (mod n) with

2

x2 = x but x2 , x ā Qn . In this case, if the parity of x2 and x diļ¬er, then Alice

can cheat freely by sending x2 and x0 to Bob instead of x and x0 in step (3).

To see this, consider the following example.

Let n = 65 and x = 4. Then x0 ā” 16 ā” 42 ā” x2 ā” x2 ā” 612 (mod 65). Also,

2

both x = 4 and x = 61 are square roots of 16 = x0 modulo n = 65 and both are

easily checked to be in Q65 as well. In step (1), Alice sends (n, x1 ) = (65, 61)

to Bob. Suppose that Bob guesses (correctly) that x is even. Then Alice can

Ā© 2003 by CRC Press LLC

38 2. Protocols, Discrete Log, and Diļ¬e-Hellman

send x = 61 and x0 = 16 to Bob instead of x = 4 and x0 = 16 in step (3). Bob

checks that both 612 ā” 16 (mod 65) (verifying that x0 ā Qn ), and

x1 ā” 61 ā” 162 = x2 (mod 65)

0

(thereby verifying that that false x, namely, x2 = 61, is indeed a square root of

x0 = 16 modulo n). Since they hold, Bob has been cheated without being any

wiser. However, with Blum integers in place, this is a self-enforcing protocol

that both Alice and Bob can be sure is a fair determination of who gets the car.

This completes our discussion of protocols.

Exercises

2.1. Suppose that a ā N and a ā” z 2 (mod pq) where p ā” q ā” 3 (mod 4) are

primes. Prove that there are only four possible square roots of a modulo

pq, and they are given as follows. For x, y ā Z given by the Euclidean

Algorithm, such that xp + yq = 1 we have:

z = Ā±(xpa(q+1)/4 + yqa(p+1)/4 ), and z = Ā±(xpa(q+1)/4 ā’ yqa(p+1)/4 ).

2.2. Let n = pq = 101 Ā· 757 = 76457 in the Feige-Fiat-Shamir Protocol. Show

how Alice can prove knowledge of sA = 3 to Bob. Assume that a = 2, and

that in the ļ¬rst round m = 98 and c = 0, whereas in the second round

m = 747 and c = 1.

2.3. Given n = pq = 2087 Ā· 487 = 1016369, use the Feige-Fiat-Shamir Protocol

to show how Alice can prove knowledge of a secret sA = 111 to Bob.

Assume that a = 2 and that on the ļ¬rst round m = 21 and c = 0, whereas

on the second round m = 12 and c = 1.

2.4. Suppose that Alice and Bob each have computers that input bitstrings of

length m ā N and output bitstrings of length n ā N. Also, assume that

they send each other copies of the circuits of their respective computers.

The following coin tossing protocol is followed.

(1) Bob chooses a random bitstring R of length m, which he then runs

through the circuitry of both computers. The two outputs are added

modulo 2 and the result is sent to Alice.

(2) Alice guesses the parity of Bobā™s input (the number of 1ā™s in it) and

sends the guess to him.

(3) Bob sends R to Alice.

(4) Alice can verify that the modulo 2 addition of the outputs from

the two circuits is indeed what Bob sent earlier, and determine the

correctness of the guess.

What two properties must hold for the above coin ļ¬‚ipping algorithm to be

fair? (This problem is a precursor to the topic to be discussed in Section

3.1.)

Ā© 2003 by CRC Press LLC

2.2. The Discrete Log Problem 39

2.2 The Discrete Log Problem

The things I want to show are mechanical. Machines have less problems.

Andy Warhol (1927ā“1987) American Artist

The security of numerous algorithms, some of which we will study in Section

2.3, is predicated upon the diļ¬culty of solving a problem that is the topic of

this section. A general form of the problem may be stated as follows.

x Generalized Discrete Log Problem

Given a ļ¬nite cyclic group G of order n ā N, a generator Ī± of G, and an

element Ī² ā G, ļ¬nd that unique nonnegative integer e ā¤ nā’1 such that Ī±e = Ī².

A speciļ¬c instance of this occurs when G = Fā— , the multiplicative group of

p

nonzero elements in Fp = Z/pZ for p an odd prime. Given a generator Ī± (also

called a primitive root modulo p, recall) of Fā— and an element Ī² ā Fā— , ļ¬nd the

p p

unique nonnegative integer e ā¤ p ā’ 2 such that Ī±e ā” Ī² (mod p). This value e

is called the index of Ī² to the base Ī± modulo p in elementary number theory.

This methodology (see [163, Section 4.1, pp. 154ā“158], for instance, and see the

index-calculus algorithm on page 43) is strikingly similar to that of logarithms.

Thus, the problem of ļ¬nding a unique nonnegative integer e ā¤ p ā’ 2 such that

c ā” me (mod p), given integers m, c and a prime p, is called the

Discrete Log Problem (DLP):

e ā” logm (c) (mod p), (2.2)

often called simply discrete log. If p is āproperly chosenā, this is a very diļ¬cult

problem to solve. At the time of this writing, the consensus is that if p has more

than 308 decimal digits, and p ā’ 1 has at least one ālargeā prime factor, then

p is properly chosen (see the discussion at the bottom of page 45). Why we

insist upon p ā’ 1 having at least one large prime factor is due to the following

algorithm, which allows for eļ¬cient calculation of discrete logs when p ā’ 1 has

only small prime factors, an issue that will be discussed in more detail after

presentation. This ļ¬rst appeared in [185].

x Silver-Pohlig-Hellman Algorithm for Computing Discrete Logs

Let Ī± be a generator of Fā— and let Ī² ā Fā— , and assume that we have a

p p

factorization

r

a

pā’1= aj ā N,

pj j

j=1

where the pj are distinct primes. The technique for computing e = logĪ± Ī² is

a

to compute e modulo pj j for j = 1, 2, . . . , r, then apply the Chinese Remainder

a

Theorem. To compute e modulo pj j we need to determine e in its base pj

representation:

aj ā’1

(j) (j)

where 0 ā¤ bi ā¤ pj ā’ 1 for 0 ā¤ i ā¤ aj ā’ 1.

bi p i

e= j

i=0

Ā© 2003 by CRC Press LLC

40 2. Protocols, Discrete Log, and Diļ¬e-Hellman

(j)

To ļ¬nd these bi , we proceed as follows. First, set Ī² = Ī²0 .

(j)

(1) Compute b0 .

(j)

(pā’1)/p

ā” Ī±(pā’1)b0 /pj (mod p). Thus we compute

j

We have that Ī²0

Ī±(pā’1)k/pj modulo p for each k = 0, 1, . . . , pj ā’ 1 until we get that

(pā’1)/pj

Ī±(pā’1)k/pj ā” Ī²0 (mod p),

(j)

in which case this k must be b0 .

(j)

for i = 1, 2, . . . , aj ā’ 1 as follows. For each such i, recursively

(2) Compute bi

deļ¬ne (j)

iā’1

Ī²i = Ī²Ī±ā’ bk pk

, and xi = logĪ± Ī²i .

j

k=0

Then

aj ā’1

(j)

bk pk ,

xi = j

k=i

since

iā’1

(j)

iā’1

ā’ bk pk (j)

) = logĪ± Ī² ā’ bk p k =

logĪ± Ī²i = logĪ± (Ī²Ī± j

k=0

j

k=0

aj ā’1 aj ā’1

iā’1

(j) (j) (j)

ā’

bk pk bk p k b k pk .

=

j j j

k=0 k=0 k=i

By Exercise 2.5,

(pā’1)/pi+1 (j)

ā” Ī±(pā’1)bi /pj

j

Ī²i (mod p), (2.3)

so we compute Ī±(pā’1)k/pj modulo p for k ā„ 0 until (2.3) occurs in which

(j)

case k is bi .

We now illustrate the Pohlig-Hellman algorithm with a very small example

to get the ļ¬‚avour of the process without making the calculations onerous.

Example 2.4 Let p = 73. Then Ī± = 5 generates Fā— . Select Ī²0 = Ī² = 68. We

73

ā—

want to compute e = log5 (68) in F73 . We have p ā’ 1 = 72 = 23 Ā· 32 = pa1 pa2 .

12

All congruences in the balance of this example are assumed to be modulo 73.

For p1 = 2:

k 0 1

536 ā” 72

Ī±(pā’1)k/p1 1

2 = a1 ā’ 1

i 0 1

68 Ā· 5ā’1 ā” 72 68 Ā· 5ā’1 ā” 72

Ī²i 68

(pā’1)/pi+1

6836 ā” 72 7218 ā” 1 729 ā” 72

Ī²i 1

(1)

bi 1 0 1

Ā© 2003 by CRC Press LLC

2.2. The Discrete Log Problem 41

Thus, the base 2 representation of log5 (68) modulo 8 is:

a1 ā’1

(1)

bi pi = 1 Ā· 20 + 0 Ā· 21 + 1 Ā· 22 ā” 5 (mod 8). (2.5)

1

i=0

For p2 = 3:

k 0 1 2

524 ā” 8 524Ā·2 ā” 64

Ī±(pā’1)k/p2 1

1 = a2 ā’ 1

i 0

68 Ā· 5ā’1 ā” 72

Ī²i 68

(pā’1)/pi+1

6824 ā” 8 728 ā” 1

Ī²i 2

(2)

bi 1 0

Thus, the base 3 representation of log5 (68) modulo 9 is:

a2 ā’1

(2)

bi pi = 1 Ā· 30 + 0 Ā· 31 ā” 1 (mod 9). (2.6)

2

i=0

Solving (2.5)ā“(2.6) by the Chinese Remainder Theorem, we get that e =

log5 68 = 37 in Fā— . (See Exercises 2.6ā“2.23.) There are eļ¬cient methods for

73

implementing the Chinese Remainder Theorem (see [59], for instance).

The complexity of ļ¬nding e in (2.2) when p has n digits is virtually the

same as factoring an n-digit integer (see [178]). This tells us that computing

discrete logs is roughly as hard as factoring (algorithms for which we will study

in Chapter 5). To date, no tractable factorization algorithms are known, so

factoring is assumed to be intrinsically diļ¬cult. Hence, cryptosystems based

upon the computation of discrete logs are assumed to be intractable. However,

it should be stressed that nobody has established nontrivial lower bounds for

the complexity of integer factorization.

Remark 2.7 If n = p ā’ 1, then given a factorization of n, the running time of

the Silver-Pohlig-Hellman Discrete Log Algorithm is

ļ£« ļ£¶

r

ā

Oļ£ aj ln n + pj ļ£ø

j=1

group multiplications. This implies that the Pohlig-Hellman Algorithm is only

eļ¬cient if the prime divisors of pā’1 are small. This is the reason why we talked

about a proper choice of p in the beginning of this section for the intractability

of the discrete log problem. It should also be noted that the above algorithm

Ā© 2003 by CRC Press LLC

42 2. Protocols, Discrete Log, and Diļ¬e-Hellman

makes use of what is known as the baby-step giant-step algorithm for computing

discrete logs due to the late Dan Shanks, a pioneer in computational number

theory. Lastly, recent techniques developed by Dan Bernstein [24] can speed up

the above algorithm.

Remark 2.7 motivates us to look at the baby-step giant-step method, which

is a generic method in the sense that it can be used with any ļ¬nite group.

For simplicity of presentation, we state the algorithm for a cyclic group. The

original idea is attributed to Dan Shanks2.1 by Odlyzko [175] and Knuth [124].

x Baby-Step Giant-Step Algorithm for Computing Discrete Logs

Given a generator Ī± of a cyclic group G of order n, and Ī² ā G, the goal is

to compute the discrete logarithm x ā” logĪ± Ī² (mod n).

ā

(1) Compute s = n.

(2) Baby-Step: For j = 0, 1, . . . , s ā’ 1, compute (j, Ī±j Ī²). Then sort the list

by second component in ascending order.

(3) Giant-Step: For i = 1, 2, . . . , s compute (Ī±is , i) and sort by ļ¬rst compo-

nent in ascending order.

(4) Search and Compare: Search the lists in Steps (2)ā“(3) to see if there

is an Ī±j Ī² from Step (2) and an Ī±is from step (3) such that Ī±j Ī² = Ī±is . If

so, then compute x ā” is ā’ j (mod n), which is logĪ± Ī² (mod n).

Example 2.8 Let Ī± = 5, Ī² = 71, and n = 167. We want to determine

x ā” log5 (71) (mod 167).

ā

First, we calculate s = n = 12. The baby-step is the computation of

(j, 5j Ā· 71 (mod 167)) for j = 0, 1, . . . , 11 :

(0, 71), (1, 21), (2, 105), (3, 24), (4, 120), (5, 99), (6, 161), (7, 137), (8, 17),

(9, 85), (10, 91), (11, 121). Then we sort according to the second element:

j 8 1 3 0 9 10

5j Ā· 71 17 21 24 71 85 91

j 5 2 4 11 7 6

5j Ā· 71 99 105 120 121 137 161

2.1 Daniel Shanks (1917ā“1996) is responsible not only for this algorithm, but also for numerous

others such as his SQUFOF algorithm for factoring (see [196]). His book [204] is a classic in

number theory. He had not only a depth of intellect that contributed fundamental results,

but also a rapier wit and warm humanity. He died on September 9, 1996 from a heart attack.

Ā© 2003 by CRC Press LLC

2.2. The Discrete Log Problem 43

The giant-step is the computation of

(512i (mod 167), i) for i = 1, 2, . . . , 12 :

(152, 1), (58, 2), (132, 3), (24, 4), (141, 5), (56, 6), (162, 7), (75, 8), (44, 9),

(8, 10), (47, 11), (130, 12). Then we order according to the ļ¬rst component:

1512i 8 24 44 47 56 58

i 10 4 9 11 6 2

1512i 75 130 132 141 152 162

i 8 12 3 5 1 7

Then we search the two lists and ļ¬nd that

Ī±3 Ī² ā” 24 ā” Ī±4Ā·12 (mod 167),

so x = 4 Ā· 12 ā’ 3 = 45 and indeed:

log5 (71) ā” 45 (mod 167) since 545 ā” 71 (mod 167).

The baby-step giant-step method presented above was ļ¬rst used by Shanks

in August of 1968 to calculate the class number of anā imaginary quadratic ļ¬eld

(see [240]). The running time for the algorithm is O( n) group operations and

according to [156, Note 3.67(i), p. 109] is the ā

same as the Silver-Pohlig-Hellman

Algorithm if n is prime. Moreover, it uses O( n) memory, so this deterministic

algorithm has a runtime/memory trade-oļ¬. Shanksā™ method is a kind of square

root method, of which Pollard provided other kinds such as his rho-method (see

[163, pp. 127ā“130]). Such methods have also been used on elliptic curves (see

[227]ā“[228]).

We now look at (arguably) the most potent and eļ¬cacious of the methods

for computing discrete logs. In its general form, it bears a strong resemblance

to some of the most powerful factoring algorithms (such as the number ļ¬eld

sieve (see [165, Section 5.2, pp. 207ā“220]), which may be considered to be a

variant of the following method). Although the following has a more general

formulation for other cyclic groups, we restrict our attention to Fā— for the sake

p

of simplicity of presentation. The following is a subexponential time algorithm

(see Appendix B).

x The Index-Calculus Algorithm for Computing Discrete Logs

We solve Ī² ā” Ī±x (mod p) where p is a large prime and Ī± is a primitive root

modulo p.

Precomputation stage:

(1) Select a factor base2.2 (a set of āsmall primesā that will remain the primes

under consideration for the duration of the algorithm): B = {p1 , . . . , pB }

2.2 The term factor base was coined by John Brillhart (see Footnote 4.5 on page 83).

Ā© 2003 by CRC Press LLC

44 2. Protocols, Discrete Log, and Diļ¬e-Hellman

consisting of the ļ¬rst B primes. (Here the choice for B should be made

such that a āconsiderable numberā of the elements of Fā— can be expressed

p

as products of powers of elements of B.)

(2) Collect relations by choosing a random nonnegative integer k ā¤ p ā’ 2 and

compute the least positive residue of Ī±k modulo p, if possible, then its

k

B

canonical prime factorization, j=1 pj j for kj ā„ 0. When such relations

exist we may take logs and get

B

kā” kj logĪ± (pj ) (mod p ā’ 1). (2.9)

j=1

Continue to choose (at least) B such k so that we are successful in securing

B relations as in (2.9). Here we are trying to solve for logĪ± (pj ) for j =

1, 2, . . . , B.

Calculation of discrete logs stage:

(3) For each k in (2.9), determine the value of logĪ± (pj ) for 1 ā¤ j ā¤ B by

solving the B (modular) linear equations with unknowns logĪ± (pj ).

(4) Select a random nonnegative integer t ā¤ p ā’ 2 and compute Ī²Ī±t .

(5) If possible, factor Ī²Ī±t over B, namely, write

B

t

(tj ā„ 0).

t

pjj

Ī²Ī± = (2.10)

j=1

If it is not possible to get (2.10), then go to step (4). If (2.10) is successfully

obtained, then

B

logĪ± (Ī²) + t ā” tj logĪ± (pj ) (mod p ā’ 1),

j=1

from which we can calculate logĪ± (Ī²).

As usual, a small example will suļ¬ce to illustrate the algorithm.

Example 2.11 Let p = 3361, Ī± = 22, and B = {2, 3, 5, 7}. We wish to compute

log22 (4) in Fā—3361 using the index-calculus method. We choose randomly k =

48, 100, 186, 2986 and get

2248 ā” 25 Ā· 32 (mod 3361), 22100 ā” 26 Ā· 7 (mod 3361),

22186 ā” 29 Ā· 5 (mod 3361), 222986 ā” 23 Ā· 3 Ā· 52 (mod 3361).

Ā© 2003 by CRC Press LLC

2.2. The Discrete Log Problem 45

Thus we get the system of four congruences in four unknowns:

48 ā” 5 log22 (2) + 2 log22 (3) (mod 3360),

100 ā” 6 log22 (2) + log22 (7) (mod 3360),

186 ā” 9 log22 (2) + log22 (5) (mod 3360) and,

2986 ā” 3 log22 (2) + log22 (3) + 2 log22 (5) (mod 3360).

This completes the precomputation stage. Now we use this to compute:

log22 (2) = 1100; log22 (3) = 2314; log22 (5) = 366; and log22 (7) = 220.

Suppose that we now select t = 754 at random and compute,

Ī²Ī±t = 4 Ā· 22754 ā” 2 Ā· 32 Ā· 5 Ā· 7 (mod 3361).

Thus, we have,

log22 (4) + 754 ā” log22 (2) + 2 log22 (3) + log22 (5) + log22 (7) (mod 3360).

Hence, log22 (4) = 2200, and we check that indeed

222200 ā” 4 (mod 3361).

(See Exercise 2.24.)

The DLP will show up throughout the text. For instance, we will look

at discrete logs and key exchange when we discuss public-key cryptography in

Chapter 3. The DLP in subgroups of Fā— is assumed intractable and is used, for

p

instance, as the security of the American Government NIST Digital Signature

Algorithm (see Chapter 7). In Chapter 7, we will see that the ElGamal signature

scheme is based upon discrete log, and in Chapter 3 that the ElGamal encryption

is also based upon the DLP. In fact, in Chapter 5, when we discuss elliptic curves,

we will see that the DLP in elliptic curve groups appears to be several orders

of magnitude more diļ¬cult than the DLP in the multiplicative group of a ļ¬nite

ļ¬eld of similar size. The DLP plays an active role in numerous cryptographic

protocols. We begin in Section 2.3 to look at some of them.

It should be pointed out that in early 2001, Joux and Lercier [116] announced

that they had set a new record for computing discrete logs modulo a prime of

120 decimal digits in ten weeks on a single 525 MHz quadri-processor Digital

Alpha Server 8400 computer. Hence, today, for long-term security, one should

choose a prime modulus of 1024 bits (308 decimal digits) for long-term security.

Ā© 2003 by CRC Press LLC

46 2. Protocols, Discrete Log, and Diļ¬e-Hellman

Exercises

2.5. Given j ā {1, 2, . . . , r}, establish that for each i = 0, 1, . . . , aj ā’ 1,

(pā’1)/pi+1 (j)

ā” Ī±(pā’1)bi /pj

j

Ī²i (mod p),

in the Silver-Pohlig-Hellman Algorithm for computing discrete logs, de-

scribed on page 39.

In Exercises 2.6ā“2.23, assume Ī± generates Fā— for the given Ī± and prime p

p

in each case, and compute logĪ± Ī² for the given Ī² using the Silver-Pohlig-

Hellman Algorithm for computing discrete logs.)

2.6. Let p = 2083, Ī± = 2, and Ī² = 19.

2.7. Let p = 37, Ī± = 2, and Ī² = 19.

2.8. Let p = 1483, Ī± = 2, and Ī² = 21.

2.9. Let p = 1579, Ī± = 3, and Ī² = 31.

2.10. Let p = 1637, Ī± = 2, and Ī² = 5.

2.11. Let p = 1721, Ī± = 3, and Ī² = 7.

2.12. Let p = 1759, Ī± = 6, and Ī² = 13.

2.13. Let p = 1783, Ī± = 10, and Ī² = 3.

2.14. Let p = 1801, Ī± = 11, and Ī² = 2.

2.15. Let p = 1871, Ī± = 14, and Ī² = 5.

2.16. Let p = 2039, Ī± = 7, and Ī² = 15.

2.17. Let p = 2161, Ī± = 23, and Ī² = 3.

2.18. Let p = 2287, Ī± = 19, and Ī² = 10.

2.19. Let p = 2351, Ī± = 13, and Ī² = 2.

2.20. Let p = 2521, Ī± = 17, and Ī² = 2.

2.21. Let p = 2689, Ī± = 19, and Ī² = 7.

2.22. Let p = 2999, Ī± = 17, and Ī² = 7.

2.23. Let p = 3361, Ī± = 22, and Ī² = 3.

2.24. Go through Exercises 2.6ā“2.23 using the index-calculus method for com-

puting discrete logs.

ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”ā”

Genius is one per cent inspiration, ninety-nine per cent perspiration.

Thomas Alva Edison (1847ā“1931) American inventor

Ā© 2003 by CRC Press LLC

2.3. Exponentiation Ciphers and Diļ¬e-Hellman 47

2.3 Exponentiation Ciphers and Diļ¬e-Hellman

Nearly every man who develops an idea works it up to a point where it

looks impossible, and then gets discouraged. Thatā™s not the place to become

discouraged.

Thomas Alva Edison

As we shall see, modular exponentiation, c ā” me (mod n) is at the heart

of RSA and one of the most important operations in public-key cryptography.

We begin by looking at some ciphers that use modular exponentiation. The

ļ¬rst was introduced in 1978 in [185]. Encryption and decryption via the follow-

ing are examples of the ļ¬rst kind of exponentiation algorithm, ļ¬xed-exponent

exponentiation, where the exponent is ļ¬xed but the base may vary.

x Pohlig-Hellman2.3 Symmetric-Key Exponentiation Cipher

(a) A secret prime p is chosen and a secret enciphering key e ā N with e ā¤ pā’2.

(b) A secret deciphering key d is computed via ed ā” 1 (mod p ā’ 1).

(c) Encryption of plaintext message units m is accomplished via

c ā” me (mod p).

(d) Decryption is achieved via m ā” cd (mod p).

Since knowledge of e and p would allow a cryptanalyst to obtain d, then

both p and e must be kept secret. The security of this cipher is based on the

diļ¬culty of solving the discrete log problem discussed in Section 2.2, namely,

an adversary, without knowledge of e or d, would have to compute

e ā” logm (c) (mod p).

Example 2.12 We will choose p = 104729 which is unrealistically small, but

for pedagogical reasons we need to do this, as we will several times throughout

the text. Let e = 1011 and d = 41539, observing that ed ā” 1 (mod p ā’ 1), as

required. Thus if m = 76, we encipher via

c ā” m1011 ā” 26422 (mod 104729),

and we see that deciphering is given by

m ā” 2642241539 ā” 76 (mod 104729).

2.3 Martin E. Hellman (1945ā“) received his Ph.D. in electrical engineering from Stanford

University in 1969. After brief stints at IBM and MIT, he returned to Stanford in 1971 where

he remained until 1996 when he became Professor Emeritus. He is credited (along with Diļ¬e

and Merkle ā” see Footnote 2.4) for discovery of the notion of public-key cryptography. It

should be noted that (as we will discuss in Section 3.5) public-key cryptography was actually

known (in the classiļ¬ed sector in England) several years before Diļ¬e and Hellman published

their result.

Ā© 2003 by CRC Press LLC

48 2. Protocols, Discrete Log, and Diļ¬e-Hellman

In Section 2.1, we saw how Alice and Bob solved a problem via coin ļ¬‚ipping

over a phone. We now show how they can solve a problem via a coin ļ¬‚ipping

protocol involving exponentiation, sometimes called ļ¬‚ipping coins into a well.

x Coin Flipping by Exponentiation

Suppose that Alice and Bob want to make a decision based upon a random

coin ļ¬‚ip, but they are not in the same physical space. We now describe how

they can do this over a channel remotely. The following is the cryptographic

protocol for electronic coin ļ¬‚ipping using exponentiation modulo a prime p > 2.

(1) Alice and Bob agree upon a prime p such that the factorization of p ā’ 1 is

known.

(2) Alice selects two generators Ī±, Ī² ā Fā— and sends them to Bob.

p

(3) Bob randomly chooses an integer x, relatively prime to p ā’ 1, then he

computes one of y ā” Ī±x (mod p) or y ā” Ī² x (mod p), and sends y to Alice.

(4) Alice guesses whether y is a function of Ī± or Ī² and sends the guess to Bob.

(5) If Aliceā™s guess is correct, then the result of the coin ļ¬‚ip is deemed to be

heads, and if incorrect, it is tails. Bob sends the result of the coin ļ¬‚ip to

Alice.

In order for Bob to cheat on the coin toss, two integers x1 and x2 must be

known where Ī±x1 ā” Ī² x2 (mod p). To compute x2 given x1 , Bob must compute

logĪ± Ī² x2 (mod p), which is possible if Bob knows logĪ± Ī². However, Alice chooses

Ī± and Ī² in step 2. Hence, Bob is in the position of having to compute a

discrete log. (Thus, the coin ļ¬‚ipping protocol relies on the diļ¬culty of the

DLP.) Also, Bob could cheat by choosing an x such that gcd(x, p ā’ 1) > 1. That

can be avoided by the following veriļ¬cation step added on the end, called the

veriļ¬cation protocol.

(6) Bob reveals x to Alice. Then Alice computes Ī±x (mod p) and Ī² x (mod p)

to verify both the outcome of the coin toss, and that Bob has not cheated.

Step (6) ensures that Bob did not cheat at step (3) since Alice can then check

gcd(x, p ā’ 1).

Characteristics implicit in the above protocol are that neither Alice nor Bob

learns about the coin ļ¬‚ip at the same time. Also, at some point in the protocol,

one of them knows the result of the coin ļ¬‚ip, but cannot alter it. The reason

this type of coin ļ¬‚ipping protocol is called ļ¬‚ipping coins into a well is that it

is a metaphor for the following situation. Suppose that Bob is next to a well,

and that Alice is physically removed from this well. Bob throws a coin into the

well, and can see (but not reach) the coin at the bottom of it. Alice cannot see

the result until Bob allows Alice to come to the well to have a look.

The following is an example of the second type of exponentiation, ļ¬xed-base

exponentiation. Moreover, this was the ļ¬rst step in public-key cryptography, the

Ā© 2003 by CRC Press LLC

2.3. Exponentiation Ciphers and Diļ¬e-Hellman 49

main topic of this text. It was also the principal motivation for the intensive

interest in discrete logs over the past quarter century.

x The Diļ¬e-Hellman Key-Exchange Protocol

Suppose that Alice and Bob have not yet met nor exchanged keys, but

they want to establish a shared secret key k by exchanging messages over an

unsecured channel. First Alice and Bob agree on a large prime p and a generator

Ī± of Fā— (2 ā¤ Ī± ā¤ p ā’ 2). These need not be kept secret, so Alice and Bob can

p

agree over an unsecured channel. Then the protocol proceeds as follows.

(1) Alice chooses a random (large) x ā N and computes the least positive

residue X of Ī±x modulo p, then sends X to Bob (and keeps x secret).

(2) Bob chooses a random (large) y ā N and computes the least positive

residue Y of Ī±y modulo p, then sends Y to Alice (and keeps y secret).

(3) Alice computes the least positive residue k of Y x modulo p.

(Note that Y x ā” Ī±yx (mod p).)

(4) Bob computes the least positive residue k of X y modulo p.

(Note that X y ā” Ī±xy (mod p).)

In the Diļ¬e-Hellman protocol, k is the shared secret key independently

generated by both Alice and Bob. The key exchange is complete, since Alice

and Bob are in agreement on k. A cryptanalyst Eve listening to the channel

would know p , Ī±, X, and Y , but neither x nor y. Thus, Eve faces what is called

the

Diļ¬e-Hellman Problem (DHP):

ļ¬nd Ī±xy given Ī±, Ī±x and Ī±y (but not x or y).

If Eve can solve the DLP, then she can clearly solve the DHP. Whether the

converse is true or not is unknown. In other words, it is not known if it is possible

for a cryptanalyst to solve the DHP without solving the DLP. Nevertheless, the

consensus is that the two problems are equivalent. Thus, for practical purposes,

one may assume that the Diļ¬e-Hellman Key-Exchange Protocol is secure as

long as discrete log is intractable. (The equivalence of the two problems has

been proved for certain situations. See [39], [68], and [150]ā“[154].) Also, in

[206], Shmuely showed that if n = pq where p and q are odd primes, and the

DHP in (Z/nZ)ā— can be solved in polynomial time for a nontrivial magnitude of

all generators (primitive roots) Ī± ā (Z/nZ)ā— , then n can be factored in expected

polynomial time (see Appendix B).

Notice that the Diļ¬e-Hellman Protocol diļ¬ers from the Pohlig-Hellman Ci-

pher in that the latter requires that both p and e be kept secret since d could

be deduced from them, whereas in the former p and Ī± may be made public due

to the intractability of the DLP. The idea leading to the above protocol began

Ā© 2003 by CRC Press LLC

50 2. Protocols, Discrete Log, and Diļ¬e-Hellman

in the 1974ā“1975 academic year with Whitļ¬eld Diļ¬e2.4 and Martin Hellman

at Stanford University, along with Ralph Merkle at the University of California

at Berkeley. The Diļ¬e-Hellman idea, that the enciphering key could be made

public since it is computationally infeasible to obtain the deciphering key from

it, is at the heart of public-key cryptography, which we will begin to study in

depth in Chapter 3 with Diļ¬e-Hellman as the ādoor-openerā to the subject.

The Diļ¬e-Hellman protocol [74] in 1976 was the ļ¬rst practical key-exchange

technique to be published. It was a landmark in cryptographic development

since this was the ļ¬rst protocol with public-key properties including the idea

of a trapdoor one-way function (see Section 3.1), a partial solution to creating

public-key cryptosystems (see Section 3.2), and digital signatures (see Chapter

7). (In Chapter 3 we will see how the authors of RSA took the ideas in [74]

and created the ļ¬rst public-key cryptosystem.) We begin in the next chapter

to travel the road paved by the appearance of this paper and explore all the

ramiļ¬cations that it brought to the cryptographic arena.

We end this section by looking at an algorithm that uses modular exponen-

tiation to speed up calculations. This is an example of another (the last) kind

of exponentiation algorithm, basic exponentiation, which can be used with any

base m and exponent e.

Our task is to calculate the least positive residue of br modulo n. To do this

in a single exponentiation would, for large values of r, overļ¬‚ow the memory of

most computers. Even if we start with b and multiply by b, r ā’ 1 times reducing

modulo n at each step, the process is too slow. Happily, there is an eļ¬cient

process of squaring and reducing modulo n given in the following algorithm.

x The Repeated Squaring Method for Modular Exponentiation

We compute br modulo n for b, r, n ā N as follows. First write r in its binary

representation:

k

aj 2j .

r=

j=0

We wish to calculate c ā” br (mod n) in a stepwise fashion as follows.

Initial Step: Set b0 = b, and:

1 if a0 = 0,

c=

b if a0 = 1.

2.4 Whitļ¬eld Diļ¬e (1944ā“) received his B.Sc. in mathematics from MIT in 1965. Later he

worked on development of the mathematical symbolic manipulation package Mathlab, and

at Stanford University on proofs of correctness of computer programs. For his involvement,

along with Hellman and Merkle, in the discovery of the notion of public-key cryptography,

he was awarded a Doctorate in Technical Sciences (Honoris Causa) by the Swiss Federal

Institute of Technology in 1992. Prior to his current position as Distinguished Engineer at Sun

Microsystems, in Palo Alto, California, assumed in 1991, he was Manager of Secure Systems

Research for Northern Telecom. Since 1993, his primary focus has been on public policy

concerning cryptography, taking a position against limitations on the use of cryptography

by individuals and corporations, which included testifying before the House and the Senate.

He has received numerous awards including the 1997 Louis E. Levy Medal from the Franklin

Institute in Philadelphia.

Ā© 2003 by CRC Press LLC

2.3. Exponentiation Ciphers and Diļ¬e-Hellman 51

Perform the following step for each j = 1, 2, . . . , k:

j-th Step: Calculate the least nonnegative residue bj of b2 modulo n.

jā’1

If aj = 1, then replace c by c Ā· bj , and reduce modulo n. If aj = 0 leave c

unchanged. What is achieved at the j th step is the computation of

cj ā” brj (mod n),

where cj is the least nonnegative residue of brj modulo n, and

j

ai 2i .

rj =

i=0

Hence, at the k th step, we have calculated c ā” br (mod n).

Example 2.13 Suppose that we wish to calculate the least positive residue of

361 modulo 101. To do this in a single exponentiation would be an enormous

task, but can be simpliļ¬ed by using the repeated squaring method. Since

61 = 1 + 22 + 23 + 24 + 25 ,

then k = 5, aj = 1 for j = 0, 2, 3, 4, 5 and a1 = 0. Also, since a0 = 1, we set

c = 3 = b = b0 . The following are the j th steps for j = 1, 2, 3, 4, 5.

(1) 32 ā” 9 (mod 101), so b1 = 9, and since a1 = 0, then c = 3 remains.

(2) b2 ā” 92 (mod 101), so b2 = 81. Since a2 = 1, then

3 Ā· 81 ā” 243 ā” 41 (mod 101), so c becomes c = 41.

(3) b3 ā” 812 ā” 97 (mod 101), so b3 = 97. Since a3 = 1, then

c Ā· b3 ā” 41 Ā· 97 ā” 38 (mod 101), and c becomes c = 38.

(4) b4 ā” 972 ā” 16 (mod 101), so b4 = 16. Since a4 = 1, then

c Ā· b4 ā” 38 Ā· 16 ā” 2 (mod 101), making c = 2.

(5) b5 ā” 162 ā” 54 (mod 101), so b5 = 54. Also, since a5 = ak = 1, then

c Ā· b5 ā” 2 Ā· 54 ā” 7 (mod 101).

Hence, 361 ā” 7 (mod 101).

Example 2.13 clearly shows the power of the repeated squaring method which

we will have occasion to use throughout the text. In Chapter 3, we will begin

with a mention of one such application. For the reader interested in an ex-

tremely fast (but more complicated) exponentiation algorithm that uses only

multiplications, see Pippengerā™s developments in [180]ā“[182].

Ā© 2003 by CRC Press LLC

52 2. Protocols, Discrete Log, and Diļ¬e-Hellman

Exercises

In Exercises 2.25ā“2.30, ļ¬nd the least nonnegative residue modulo p for each

given exponent using the repeated squaring method (see page 50).

2.25. 551 modulo p = 97.

2.26. 749 modulo p = 103.

2.27. 971 modulo p = 113.

2.28. 1079 modulo p = 151.

2.29. 1122 modulo p = 167.

2.30. 1351 modulo p = 179.

In Exercises 2.31ā“2.34, decipher the cryptogram assuming that it was en-

crypted using the Pohlig-Hellman cipher with the given prime p and enciphering

key e. Determine the deciphering key d to get the numerical equivalents of the

plaintext, which will then be translated via Table 1.2 on page 3.

2.31. p = 167, e = 69 and cryptogram is 85, 50, 96, 96, 0, 27, 50.

2.32. p = 397, e = 95 and cryptogram is 344, 107, 128, 107, 198, 339, 107, 49.

2.33. p = 1187, e = 107 and cryptogram is 1084, 235, 904, 0, 18, 904.

2.34. p = 1481, e = 1201 and cryptogram is 1175, 185, 1032, 293, 263, 185, 167.

In Exercises 2.35ā“2.47, assume that the p, Ī±, x, and y are the parameters in

the Diļ¬e-Hellman protocol. Determine the key k generated by Alice and Bob in

each case.

2.35. p = 3361, Ī± = 22, x = 2999, y = 3299.

2.36. p = 3529, Ī± = 17, x = 3400, y = 3501.

2.37. p = 3631, Ī± = 15, x = 2001, y = 3001.

2.38. p = 3881, Ī± = 13, x = 3801, y = 2799.

2.39. p = 3889, Ī± = 11, x = 2000, y = 3811.

2.40. p = 4051, Ī± = 10, x = 2051, y = 3000.

2.41. p = 4129, Ī± = 13, x = 1998, y = 3900.

2.42. p = 4201, Ī± = 11, x = 4200, y = 2111.

2.43. p = 4339, Ī± = 10, x = 2911, y = 3911.

2.44. p = 4391, Ī± = 14, x = 3311, y = 4131.

2.45. p = 4441, Ī± = 21, x = 4011, y = 3191.

2.46. p = 4657, Ī± = 15, x = 4111, y = 2229.

2.47. p = 5039, Ī± = 11, x = 3133, y = 4313.

Ā© 2003 by CRC Press LLC