authorea.com/6558

CS111 Homework Assignment 2

**Problem 1:** Let \(x\) be a positive integer and \(y = x^2+2\). Can \(x\) and \(y\) be both prime? The answer is yes, since for \(x=3\) we get \(y=11\), and both numbers are prime. Prove that this is the only value of \(x\) for which both \(x\) and \(y\) are prime.

*Hint:* Consider cases, depending on the remainder of \(x\) modulo \(3\).

**Solution 1:**

If \(x\neq3\), then \(x=1\) or \(x=2\) in \(x\) modulo \(3\).

\(x=1\) and \(x=2\) would be prime under the equation \(x^2 = 1\) (mod \(3\))

However, with the equation \(x^2+2\), both \(x=1\) and \(x=2\) result in 0 \(x^2+2=0\)(mod \(3\))

This means that \(3\) evenly divides into \(x^2+2\) for \(x=1\) and \(x=2\), meaning that \(y\) is not prime for both of these terms.

Additionally, \(y\neq3\) because the equation is only true for \(x=1\) and \(1\) is not a prime number.

Therefore, since for \(x=1\) and \(x=2\), \(y\) is divisible by \(3\) and \(y\neq3\), the only case where both \(x\) and \(y\) can be prime is \(x=3\)

**Problem 2:** Alice’s RSA public key is \(P = (e,n) = (13,77)\). Bob sends Alice the message by encoding it as follows. First he assigns numbers to characters: blank is 2, comma is 3, period is 4, then A is 5, B is 6, ..., Y is 29, and Z is 30. Then he uses RSA to encode each number separately.

Bob’s encoded message is:

```
11 58 52 30 57 61
60 22 30 10 26 35
52 23 30 10 41 22
23 52 38 30 52 12
58 46 30 57 61 60
30 35 26 46 30 50
41 23 52 61 22 52
30 52 12 58 73 30
26 23 30 57 61 60
30 69 37 58 26 23
58 53
```

Decode Bob’s message. Notice that you don’t have Bob’s secret key, so you need to “

For the solution, you need to provide the following:

Describe step by step how you arrived at the solution:

Show how you determined \(p\), \(q\), \(\phi(n)\), and \(d\);

Show the computation for the first number in the message.

Give Bob’s message in plaintext. (The message is a quote. Who said it?)

If you wrote a program, attach your code to the hard copy. If you solved it by hand, attach your scratch paper with calculations.

**Solution 2:**

Since \(n\) is a product of \(p\) and \(q\), which are both prime numbers, we compute the prime factorization of \(n=77=7*11\).

So, \(p=7\) and \(q=11\)

To compute \(\phi(n)\), we use the formula \(\phi(n)=(p-1)(q-1)\)

\(\phi(n)=(7-1)(11-1)\)

\(\phi(n)=60\)

Now, we must compute \(d\) using the formula: \(d=e^{-1} (mod\: \phi(n))\)

\(d=13^{-1} (mod\: 60)\)

Using linear combinations, we get:

\(13(37)=1+60(8) (mod\: 60)\)

\(13*37=1 (mod\: 60)\)

\(37=13^{-1} (mod\: 60)\)

\(d=37\)

To compute \(m\) from \(c\), we use \(m=c^d (mod\: n)\).

Computing the first letter, \(11^{37} (mod\: 77)\)

\(11*11^{36} (mod\: 77)\)

\(11*121^{18} (mod\: 77)\)

\(11*(44^2)^{9} (mod\: 77)\)

\(11*11^9 (mod\: 77)\)

\(11*11*11^8 (mod\: 77)\)

\(11*11*121^4 (mod\: 77)\)

\(11*11*(44^2)^2 (mod\: 77)\)

\(11*11*11^2 (mod\: 77)\)

\(11*11*44 (mod\: 77)\)

\(121*44 (mod\: 77)\)

\(44*44 (mod\: 77)\)

\(=11 (mod\: 77)\)

The first letter is \(11\) or G.

Using the the program whose source code is attached to the back of this document, the decrypted message is:

“GET YOUR FACTS FIRST, THEN YOU CAN DISTORT THEM AS YOU PLEASE.” - Mark Twain

## Share on Social Media