Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Problem 1.
In class, we investigated quadratic residues modulo a prime. In this problem, we will take
it up a notch by investigating cubic residues modulo primes.
We begin by fixing a prime p > 3. Furthermore, let a be an integer such that p 6 | a.
We say that a is a cubic residue mod p if there exists b such that a ≡ b
3
(mod p).
1. Show that the product of two cubic residues mod p is again a cubic residue.
2. For a and b not divisible by p, is it necessarily the case that at least one of: a, b, ab
is a cubic residue mod p?
3. Fix a primitive root g ∈ F
∗
p
. Determine for what values of k, the element g
k
is a cubic
residue mod p.
Hint. Your answer should depend on what p is mod 3.
Problem 2.
Most of the cryptosystems implemented in practice add an element of randomization in
order to prevent certain attacks. In this problem, we will explore one way of adding
randomization to the RSA cryptosystem.
Our set of messages M = {0, 1}
30 consists of bit strings of length 30. Alice’s public key
is the usual RSA public key (N, e). To encrypt a message m, Bob chooses a random bit
string r of length 30 and computes
c = n(m)
e
(mod N)
where n(m) is the number whose binary representation is given by the bit string r||(r⊕m).
Here, || denotes concatenation of strings and ⊕ is a binary operation defined on individual
bits as:
b ⊕ b
0 =
(
1 if b = b
0
0 otherwise.
You task is to implement the decryption function that given the RSA private key finds the
original message m.