# CS/MATH111 ASSIGNMENT 2

CS/MATH111 ASSIGNMENT 2

due Tuesday, April 29 (8AM)

0.1in Individual assignment: Problems 1 and 2.

0.1in

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.

ANSWER: If $$x$$=$$0$$ (mod $$3$$),then for $$x$$ to be prime $$x$$ must be $$3$$. If $$x$$=$$1$$(mod$$3$$), then $$x$$ has to be $$4$$.The this shows that the next $$x$$ will be prime relative to $$3$$.We can then assume $$x$$=$$2$$m+$$1$$, and $$y$$=$$2$$n+$$1$$ , since odd numbers can be represented as $$2$$n+$$1$$ and $$2$$m+$$1$$ where m and n are integers.

So the equation will be:

$$2$$n+$$1$$=($$2$$m+$$1$$)($$2$$m+$$1$$)+$$2$$

$$2$$n+$$1$$=($$4$$m)($$4$$m)+$$4$$m+$$1$$+$$2$$

$$2$$n+$$1$$=($$4$$m)($$4$$m)+$$4$$m+$$3$$

When solving for this the right hand side will be even since and odd plus and odd results in and even integer.The right hand side will be divisible by $$2$$ when m does not equal $$1$$ showing that $$x$$ and $$y$$ be both prime only when $$x$$=$$3$$, When x does not equal 3 the right side will be even and divisible by 2 while the left side will be odd.

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 “break" RSA to decrypt his message.

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.

ANSWER: Since n=$$77$$, and it had to be composed of prime numbers p and q. p=$$11$$ and q=$$7$$. We know that e times x will give us $$1$$ times the mod of ((p-$$1$$)(q-$$1$$)). Next we compute s, and t such that: $$13$$s+$$60$$t=$$1$$ Using Euclidean Algorithm we find s=$$37$$ and t=-$$8$$. That gives us d since d=s, so d=37. Since we know n=p*q, we have n=$$77$$. I used a program to figure decode the numbers. I just set up the equation: (encrypted number)^s(mod n) THE ASWER TO THE MESSAGE: Get your facts first, then you can distort them as you please. by Mark Twain.

0.1in

#### Submission.

To submit the homework, you need to upload the pdf file into ilearn by 8AM on Tuesday, April 29, and turn-in a paper copy in class.