A) Because Is a Primitive Root for , (Mod P

2.3

(a) Because is a primitive root for , (mod p)

x = a and x = b so we have: (mod p), without lose generality assume that ab, we have:

(mod p) (1)

(mod p) ( because: 1 (mod p)

So, with q, r ; 0 r p – 1, (a-b) = q(p – 1) + r (*)

 (mod p) (2)

By Euler’s Theorem, (mod p) (3)

From (1), (2), (3) 1 (mod p), with r < p – 1 => r = 0. (4)

From (*) & (4) → (a – b) = q(p – 1), it means (a – b) (mod p – 1)

→ (mod p – 1)

(b) Set:

logg(h1.h2) (mod p)

b1 logg(h1) (mod p)

b2 logg(h2) (mod p)

b b1 + b2

h = h1.h2

We have to proof:

a b1 + b2 b (mod p – 1)

As we set above, we have that: h (mod p),

= = h1.h2 = h => h (mod p)

It means: and

Suppose that x = a & x = b are both solutions to the congruence

As part (a) we have a b (mod p – 1). So that:

logg(h1.h2) = logg(h1) + logg(h2) for all h1, h2 *p

a logg(hn) (mod p)

b logg(h) (mod p)

We have to proof: a b (mod p – 1)

As we set above, we have:

hn (mod p)

h (mod p)

 (mod p)

Suppose that x = a & x = b.n are both solutions to the congruence h (mod p)

As part (a) we have: a b (mod p – 1). So that

logg(hn) = n.logg(h) for all h1, h2 *p & n

2.4

(a)

-> x=7

-> ( prime 23)

(b)

-> x=10

-> (prime 47)

for the prime p= 941)

2.5 We have :

Because g is primitive root, so square root is

So, a has a square root modulo p if and only if its discrete logarithm modulo p is

even.

2.6. .

p = 1373 is a prime, and g = 2 is a primitive root mod p. Alice picks her

expopnent a and computes A ≡ ≡ 974 (mod 1373). Bob wants to use b = 871 to send Alice B ≡ (mod 1373), and to obtain the secretly commonly shared key .

Thus Bob will send Alice B ≡ 805 (mod 1373). Their commonly shared secret key is ≡ . ≡ 397

(mod 1373).
2.7

Because, when Eva has fouldalgorithm that solves the Diffie–Hellman problem, so she can compute gab ≡ Ab ≡ Ba(mod p). She can find b with (ga )b≡ Ba(mod p) . So she can used it tosolve the Diffie–Hellman decision problem.

I think Diffie–Hellman decision problem is hard , because with big prime, We have difficulty for compute Ax (mod p) ….

2.8

(a) A ≡ ≡ ≡ 177 (mod 1373).

(b) Here k = 877. From public domain, A ≡ 177 (mod 1373). Therefore,

C1 =(mod p) =719

C2=

Hence c1 ≡ 719 and c2 ≡ 618 (mod 1373).

(d) Eve ﬁrst solves the discrete math log problem≡ 893 (mod 1373) to get b = 219

(mod 1373) =893

Then decode the cipher text as follows.

c1 = 693

c2 =793

x = (mod p) = 431

> m = c2*mod p = 365 mod 1373
Thus m ≡ 365 (mod 1373).

2.9I don’t know. I’m sorry

2.10Big number!!! I can’t compute..:3 .I’m sorry.

1.26

Let {p1, p2, …,pr} be a set of prime numbers, and let N = p1p2…pr + 1.

Prove that N is divisible by some prime not in the original set.

We have N = p1*p2…*pr + 1 => N is not divisible by p1, p2, ..pr (1)
N is a natural number, according to the fundamental theorem of arithmetic, every natural number > 1 can be written one way only achievement primes

N = A1k1*A2k2…Ankn with A1, A2, …Ak is prime numbers (A1, A2, … Ak p1, p2, …., pr) (2)

From (1) and (2) => N is divisible by some prime not in the original

Use this fact to deduce that there must be infinitely many prime numbers.

Call set P = {p1, p2, …, pr} is the set of prime numbers known and set

N = p1*p2… *pn + 1

According to the above, N is divisible by a prime number not belonging to the original.

Then there exists a set of primes not known primes, so primes is infinite.

1.27

Without using the fact that every integer has a unique factorization into primes.

Prove that if gcd(a, b) = 1 and if a | bc, then a | c

One Way:

Gcd(a, b) = 1 => ax + by = 1  c.ax + c.by = c
a | (c.ax + c.by) => a | c

Two Way:

We have a | bc => b*c = k*a (with a Z) (1)
And gcd(a, b) = 1 => is not a divisor of b (2)

From (1) and (2) => is a divisor of c or a | c

1.28

Compute the following ordpvalues:

The fundamental theorem of arithmetic (Theorem 1.21) says that in the factorization of a positive integer a into primes, each prime p appears to a particular power. We denote this power by ordp(a) and call it the order (or exponent) of p in a. ( For convenience, we set orpp(1) = 0 for all primes)

Ord2 (2816): We have 2816 = 11 * 28 Then Ord2 (2816) = 8
Ord7 (2222574487): We have 2222574487 = 75 * 132241 Then Ord7 (2222574487) = 5
ordp(46357) for each of p = 3, 5, 7 or 11. We have 46357 = 7 * 53 * 53

Then:

ord3(46357) = 0

ord5(46357) = 3

ord7(46357) = 1

ord11(46357) = 0

1.29

Let p be a prime number. Prove that ordphas the following properties.

a)Ordp(ab) = ordp(a) + ordp(b)

Set a = p1X1* p2X2* …*pXp =ordp(a) = Xp

Set b = p1Y1* p2Y2* …*pYp =ordp(b) = Yp

a * b = p1X1* p2X2* …*pXp * p1Y1* p2Y2* …*pYp

a * b = p1X1* p2X2* …* p1Y1* p2Y2 * p(Xp + Yp)

ordp(a * b) = Xp + Yp = ordp(a) + ordp(b)

b)Ordp(a + b) >= min{ ordp(a) , ordp(b)}

Set a = p1X1* p2X2* …*pXp =ordp(a) = Xp

Set b = p1Y1* p2Y2* …*pYp =ordp(b) = Yp

Give XpYp => min{ordp(a) , ordp(b)} = Xp (1)

a + b = (p1X1* p2X2* …*pXp) + (p1Y1* p2Y2* …*pYp)

a + b = (p1X1* p2X2* …*pXp) + (p1Y1* p2Y2* …*pXp + Kp)

withXp + Kp = Yp

a + b = pXp[(p1X1* p2X2* …*) + (p1Y1* p2Y2* …*pKp)]

ordp(a + b) = Xp + a small amount may be >= 0 (2)

From (1) and (2) => Ordp(a + b) >= min{ ordp(a) , ordp(b)}

c)If ordp(a) ordp(b), then Ordp(a + b) = min{ ordp(a) , ordp(b) }

Set a = p1X1* p2X2* …*pXp =ordp(a) = Xp

Set b = p1Y1* p2Y2* …*pYp =ordp(b) = Yp

Give XpYp => min{ordp(a) , ordp(b)} = Xp (1)

a + b = (p1X1* p2X2* …*pXp) + (p1Y1* p2Y2* …*pYp)

a + b = (p1X1* p2X2* …*pXp) + (p1Y1* p2Y2* …*pXp + Kp)

withXp + Kp = Yp

a + b = pXp[(p1X1* p2X2* …*) + (p1Y1* p2Y2* …*pKp)]

withordp(a) ordp(b) then

[(p1X1* p2X2* …*) + (p1Y1* p2Y2* …*pKp)] = k1X1*k2X2*…*kpXp

With k1, k2,…,kp p1, p2, … p (Application The Fundamental Theorem Of Arithmetic)

Ordp(a + b) = Xp (2)

From (1) and (2) => Ordp(a + b) = min{ ordp(a) , ordp(b)} = Xp

1.30

For each of the following primes p and numbers a, compute a-1 mod p in two way.

Use the extended Euclidean algorithm
Use the fast power algorithm and Fermat’s little theorem.

a)P = 47 and a = 11

Use the extended Euclidean algorithm

P / a / q / r / Y0 / Y1 / y
47 / 11 / 4 / 3 / 0 / 1 / -4
11 / 3 / 3 / 2 / 1 / -4 / 13
3 / 2 / 1 / 1 / -4 / 13 / -17
2 / 1 / 2 / 0

-17 + 47 = 30 => a’ = 30

Use the fast power algorithm and Fermat’s little theorem

According to Remark 1.27. We have a-1 = ap – 2 (mod p)

11-1 = 1145 = 30 (mod 47)

a’ = 30

b)P = 587 and a = 345

Use the extended Euclidean algorithm

P / a / q / r / Y0 / Y1 / y
587 / 345 / 1 / 242 / 0 / 1 / -1
345 / 242 / 1 / 103 / 1 / -1 / 2
242 / 103 / 2 / 36 / -1 / 2 / -5
103 / 36 / 3 / 31 / 2 / -5 / 12
36 / 31 / 1 / 5 / -5 / 12 / -17
31 / 5 / 6 / 1 / 12 / -17 / 114
5 / 1 / 5 / 0

a’ = 114

Use the fast power algorithm and Fermat’s little theorem

According to Remark 1.27. We have a-1 = ap – 2 (mod p)

345-1 = 345585 = 114 (mod 587)

a’ = 114

c)P = 104801 and a = 78467

Use the extended Euclidean algorithm

P / a / q / r / Y0 / Y1 / y
104801 / 78467 / 1 / 26334 / 0 / 1 / -1
78467 / 26334 / 2 / 25799 / 1 / -1 / 3
26334 / 25799 / 1 / 535 / -1 / 3 / -4
25799 / 535 / 48 / 119 / 3 / -4 / 195
535 / 119 / 4 / 59 / -4 / 195 / -784
119 / 59 / 2 / 1 / 195 / -784 / 1763
59 / 1 / 59 / 0

a’ = 1763

Use the fast power algorithm and Fermat’s little theorem

According to Remark 1.27. We have a-1 = ap – 2 (mod p)

=> 78467-1 = 78467104799 = 1763 ( mod 104801)

=> a’ = 1763

1.31

By Fermat’s Theorem, we have bq = a((p-1)/q)^q = 1 (mod p). So the order of b divides the prime q, But q has very few divisors: if b 1, then b has order q.
A are a such that a((p-1)/q = 1 (mod p). These are the a whose order diveides (p-1)/q.

It is convenient now to use a primitive root g of p for the rest of the argument. Let a = gk (mod p)/ Then (gk)ˆ((p-1)/q) = 1 (mod p) if and only if (p-1) divides k(p-1)/q, that is, if and only if k is a multiply of g. There are (p-1)/q such multiples of q in the interval 0 to p -1. Hus the required fraction is ((p-1)/q)/(p-1), that is, 1/q.

1.32

For which of the following primes is 2 a primitive root modulo p?

P = 7: 20 = 1, 21 = 2, 22 = 4, 23 = 1, 24 = 2…Then: 2 is not primitive root modulo 7

P = 13: 20 = 1, 21 = 2, 22 = 4, 23 = 8, 24 = 3, 25 = 6, 26 = 12, 27 = 11, 28 = 9, 29= 5, 210=10, 211=7. Then 2 a primitive root modulo 13

P = 19: 20 = 1, 21 = 2, 22 = 4, 23 = 8, 24=16, 25=13, 26=7, 27 =14, 28 = 9, 29 = 18, 210 = 17, 211 = 15, 212= 11, 213= 3, 214=6, 215=12, 216=5, 217= 10. Then 2 is a primitive root module 19
P = 23: 20 = 1, 21 = 2, 22 = 4, 23 = 8, 24 = 16, 25 = 9, 26 = 18, 27 = 13, 28 = 3, 29 = 6, 210 = 12, 211 = 1, 212 = 2…Then 2 is not a primitive root modulo 23.

For which of the following primes is 3 a primitive root modulo p?

P= 5: 30 = 1, 31 = 3, 32 = 4, 33 = 2. Then 3 is a primitive root modulo 5.
P = 7: 30 = 1, 31 = 3, 32 = 2, 33 = 6, 34 = 4, 35 = 5. Then 3 is a primitive root modulo 7.
P = 11: 30 = 1, 31 = 3, 32 = 9, 33 = 5, 34 = 4, 35 = 1, 36 = 3…. Then 3 is not a primitive root modulo 11.
P = 17: 30 = 1, 31 = 3, 32 = 9, 33 = 10, 34 = 13, 35 = 5, 36 = 15, 37 = 11, 38 = 16, 39 = 14, 310 = 8, 311 = 7, 312 = 4, 313 = 12, 314 = 2, 315 = 6. Then 3 is a primitive root modulo 17.

Find a primitive root for each of the following primes.

P = 23: after compute: 3 a primitive root modulo 23
P = 29: after compute: 2 a primitive root modulo 29.
P = 41: after compute: 2 a primitive root modulo 41
P = 43: after compute: 2 a primitive root modulo 43

Find all primitive root modulo 11.

{2, 6, 7, 8} is a list of a primitive root modulo 11.

And (10) = 4.

1.33

If gq 1 (mod p) then the order of g does not divide q. But the order every unit mod p divides (p) = p – 1 = 2q. So g’s order divides 2q but not q.

Bài1.36 :

-Compute :

p = 3 => 2(p-1)/2(mod p) = -1.
p = 5 => 2(p-1)/2(mod p) = -1.
p = 7 => 2(p-1)/2(mod p) = 1.
p = 11 => 2(p-1)/2(mod p) = -1.
p = 13 => 2(p-1)/2(mod p) = -1.
p = 17 => 2(p-1)/2(mod p) = 1.
p = 19 => 2(p-1)/2(mod p) = -1.

-Using Fermat's little theorem, 2p = 2 (mod p)
2p-1 = 1 (mod p)
So (2(p-1)/2)2 = 1 (mod p)
Therefore 2(p-1)/2 = ± 1 (mod p).

Bài1.35 :

It suffices to show if b mod p. Since p |/ b, then a ≠ 0 ( mod p ). Therefore p |/ a and thus gcd (a,p) = 1.

Since a2 ≡ b (mod p), it follow that (–a )2 ≡ a2 ≡ b ( mod p ) and so –a must also be a square root of b ( mod p). We need to explain that a ≠ –a (mod p) . If we had \ 2 a ≡ –a ( mod p) then 2a ≡ 0 (mod p), so p | 2a. Since gcd(a.p) = 1 and p | 2a, then p |2 , which is contrary to p being prime. Hence, a ≠ a(mod p) and so b has at least two square roots.

We need to show that b cannot have more than 1 square roots. Suppose that for some c € Zp , c ≠ ±a(mod p) but c2 = b(mod p). Then we have a2 ≡ b ≡ c2 (mod p), or equipvalently, (a – c) (a + c) ≡ a2 – c2 ≡ b(mod p). This mean p | (a – c) (a + c). If p | (a – c) then c ≡ a(mod p) ; if p |(a + c) then c ≡ –a(mod p) . Either way will lead to a contradition to the assumptions that c ≠ ±a(mod p) . Thus, b must have two square roots, if it has a least one.

1.40

B / a / d / d / a / y / , / D / a / d / .
66 / 97 / 100 / 32 / 100 / 97 / 121 / 44 / 32 / 68 / 97 / 100 / 46
1000010 / 1100001 / 1100100 / 0100000 / 1100100 / 1100001 / 1111001 / 0101100 / 0100000 / 1000100 / 1100001 / 1100100 / 0101110

1.41

a) p = 541, k = (34, 71)

ek(m) = k1.m + k2 (mod p) = 34.204 + 71 (mod 541) = 7007 (mod 541) = 515

dk(c) = k1’.(c – k2) (mod p) = 366.(431 – 71) (mod 541) = 131760 (mod 541) = 297

b) Given some pairs of plaintexts and their corresponding cinphertext, (m1, c1), (m2, c2), …, (mn, cn), and p is public knowledge. We can use the encryption and decryption that are defined by

ek(m) = k1.m + k2 (mod p)anddk(c) = k1’.(c – k2) (mod p)

to find two integer k(k1, k2) that is private key. So that why the affine cipher is vulnerable. We might need at least two pairs of plaintext/ciphertext to recover the private key.

d) If p is not public knowledge, the affine cipher still vulnerable to a chosen plaintext attack. We might need at least 3 pairs to recover the private key.

1.42

i) Encrypt m: c = k1.m + k2 (mod 7) =

b) The Hill cipher is vulnerable to a know-plaintext attack because it is completely linear. An opponent who intercept n2 plaintext/ciphertext character pairs can set up a linear system which can be easily solves.

c) The alphabet has a zero element. In some case, the zero element is “A”. The numerical value of any letter α + A = α, just as any number added to 0 equals itself. The alphaber is closed under modulo addition. The addition operator “+” is defined as modulo addition for use within this alphabet such that for the numerical values of two letters α and β by the size of the alphabet. The alphabet is closed under modulo scalar multiplication. Scalar multiplication is defined for use within this alphabet such that for all numerical values of two letters α and β, αβ = γ where γ is the remainder of the product of α and β divided by the size of the alphabet.

1.43

a) No. ek(m) = (k – m)k (mod N)

b) Yes. dk(m) = k-1.m (mod N)

c) No. ek(m) = k + m (mod N)

1.44

a) 3429

b) 1001001111011101

c) 100100001100010001000100

d) 11001010 xor 10011010 = 01010000

8734 = 10001000011110

5177 = 01010000111001

8734 xor 5177 = 11011000100111 = 13863

1.45

a) ~591 days.

b) B = 66.

1.46

We have ek(m) = k xor m = c

Thus c xor m = k xor m xor m = k

So if we know the cipher text and message, we can find the private key k.

We have:

e = 1001010001010111

m = 0010010000101100

So k = m xor c = 1011000001111011

1.47

a) We have and d = 6

So α = 316624

Ciphertext c = 328973 + 316624 (mod 106) = 645597 (mod 106) = 645597

b) We have and d = 8

So m = c – α (mod 108) = 78183903 – 79583152 (mod 108) = -1399249 (mod 108) = -1399249

1.48

C1=12849217045006222

C2=6485880443666222

k is a large prime (key need to find)

m is a message(intergers)

We have:

C1=km1

C2=km2

X=gcd(c1,c2)=gcd(k·m1,k·m2)=k·gcd(m1,m2)= 174385766

X equals k itself or a small multiple of k.

Y=X/2=87192883

Test Y, we see Y is a prime =>k=87192883

Bài3.1 :

We solve the congruence :x19 ≡ 36 (mod 97), where the modulus p = 97 is prime.