Scribd
Upload
29 views

Premitive Roots_lecture3

Uploaded by

Ayush Verma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
29 views

Premitive Roots_lecture3

Uploaded by

Ayush Verma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

05-11-2024

Sketch of Lecture 25 Mon, 3/20/2023

Comments on primitive roots

Example 154. Determine all primitive roots modulo 11.


Solution. Since (11) = 10, the possible orders of residues modulo 11 are 1; 2; 5; 10. Residues with order 10 are
primitive roots. Our strategy is to find one primitive root and to use that to compute all primitive roots.
There is no good way of finding the first primitive root. We will just try the residues 2; 3; 5; ::: (why not 4?!)
We compute the order of 2 (mod 11):
Since 22 = 4 / 1 (mod 11), we find that 2 has order 10. Hence, 2 is a primitive root.
/ 1, 25 ¡1
10
All other invertible residues are of the form 2x. Recall that the order of 2x (mod 11) is gcd (10; x)
.
Hence, 2x is a primitive root if and only if gcd (10; x) = 1, which yields x = 1; 3; 7; 9.
In conclusion, the primitive roots modulo 11 are 21 = 2; 23 = 8; 27 7; 29 6.

Example 155. (extra) Determine all primitive roots modulo 22.


Solution. We proceed as in the previous example:

Since (22) = 10, the possible orders of residues modulo 22 are 1; 2; 5; 10.

We find one primitive root by trying residues 3; 5; ::: (2 is out because it is not invertible modulo 22)
Since 35 1 (mod 22), 3 is not a primitive root modulo 22.
Since 55 1 (mod 22), 5 is not a primitive root modulo 22.
Since 72 / 1 (mod 22), 7 is a primitive root modulo 22.
/ 1, 75 ¡1
10
7x (mod 22) has order gcd (10; x)
. We have gcd (10; x) = 1 for x = 1; 3; 7; 9.

Hence, the primitive roots modulo 22 are 71 = 7; 73 13; 77 17; 79 19.

Proceeding as in the previous example, we obtain the following result.

Theorem 156. (number of primitive roots) Suppose there is a primitive root modulo n. Then
there are ((n)) primitive roots modulo n.
Proof. Let x be a primitive root. It has order (n). All other invertible residues are of the form xa.
(n)
Recall that xa has order gcd ((n); a)
. This is (n) if and only if gcd ((n); a) = 1. There are ((n)) values
a among 1; 2; :::; (n), which are coprime to (n).
In conclusion, there are ((n)) primitive roots modulo n.

Comment. Recall that, for instance, there is no primitive root modulo 15. That's why we needed the assumption
that there should be a primitive root modulo n (which is the case if and only if n is of the form 1; 2; 4; pk ; 2pk
for some odd prime p).

In particular, since there are always primitive roots modulo primes, we have the following important
case:

There are ((p)) = (p ¡ 1) primitive roots modulo a prime p.

Example 157. (bonus challenge) For which prime p < 106 is the proportion of primitive roots
among invertible residues the smallest?
Send in a solution by next week for a bonus point!

Armin Straub 58
[email protected]
Back to RSA
(RSA encryption)

Bob chooses large random primes p; q .

Bob chooses e, and then computes d such that de 1 (mod (p ¡ 1)(q ¡ 1)).

Bob makes N = pq and e public. His (secret) private key is d.

Alice encrypts c = me (mod N ).

Bob decrypts m = c d (mod N ).


Does decryption always work? What Bob computes is cd (me)d = mde (mod N ). It follows from Euler's
theorem and de 1 (mod (N )) that mde m (mod (N )) for all invertible residues m. That this actually
works for all residues can be seen from the Chinese Remainder Theorem (see Theorem 158 below).
Is that really secure? Well, if implemented correctly (we will discuss potential issues), RSA has a good track
record of being secure. Next class, we will actually prove that finding the secret key d is as difficult as factoring
N (which is believed, but has not been proven, to be hard). On the other hand, it remains an important open
problem whether knowing d is actually necessary to decrypt a given message.
Comment. The (p ¡ 1)(q ¡ 1) in the generation of d can be replaced with lcm (p ¡ 1; q ¡ 1). This will be
illustrated in Example 162.

Theorem 158. Let N = pq and d; e be as in RSA. Then, for any m, m mde (mod N ).
Comment. Using Euler's theorem, this follows immediately for residues m which are invertible modulo N .
However, it then becomes tricky to argue what happens if m is a multiple of p or q.

Proof. By the CRT, we have m mde (mod N ) if and only if m mde (mod p) and m mde (mod q).
Since d e 1 (mod (p ¡ 1)(q ¡ 1)), we also have d e 1 (mod p ¡ 1). By little Fermat, it follows that
mde m (mod p) for all m
/ 0 (mod p). On the other hand, if m 0 (mod p), then this is obviously true.
Thus, m mde (mod p) for all m. Likewise, modulo q .

Example 159. Bob's public RSA key is N = 33, e = 3.


(a) Encrypt the message m = 4 and send it to Bob.
(b) Determine Bob's secret private key d.
(c) You intercept the message c = 31 from Alice to Bob. Decrypt it using the secret key.
Solution.

(a) The ciphertext is c = me (mod N ). Here, c 43 = 64 31 (mod 33). Hence, c = 31.

(b) N = 3 11, so that (N ) = 2 10 = 20.


To find d, we need to compute e ¡1 (mod 20). Since the numbers are so simple we see 3¡1 7 (mod20).
Hence, d = 7.

(c) We need to compute m = cd (mod N ), that is, m = 317 (¡2)7 4 (mod 33).
That is, m = 4 (as we already knew from the first part).

Example 160. For his public RSA key, Bob needs to select p; q and e. Which of these must be
chosen randomly?
Solution. The primes p and q must be chosen randomly. Anything that makes these primes more predictable,
makes it easier for an attacker to get her hands on them [in which case, the secret key d is trivial to compute].
On the other hand, e does not need to be chosen at random. In fact, knowing any pair e; d such that ed
1 (mod (p ¡ 1)(q ¡ 1)) would allow us to factor N = pq (and thus break RSA). We'll prove that later.

Armin Straub 59
[email protected]

You might also like