- A Mac or Linux computer with Python.

How large are p and q? Well, they can't both be larger than the square root of n, or they'd be larger than n when multiplied together.

Start Python in interactive mode. On a Mac or Linux box, you can do that by typing this command into a Terminal window:

Execute these commands:`python`

The square root prints out, as shown below.

import math n = 10142789312725007 print math.sqrt(n)

Execute this command:

Now more decimal places appear, as shown below.

print repr(math.sqrt(n))

A good way to do this is to calculate n mod c, where c is a candidate. If c is a factor of n, the result will be zero.

We can test the first 20 candidates with a for loop.

Execute these commands:

Press Enter twice after the last command to terminate the loop.

c = 100711413 for i in range(c, c-40, -2): print i, n%i

The third candidate is the winner, with a remainder of zero, as shown below.

Execute these commands:

The calculation worked, so the last value is zero, as shown below.

p = 100711409 q = n / p print p, q, n, p*q, n - p*q

The parameters print out, as shown below.

phin = (p-1) * (q-1) print p, q, n, phin

We know that e = 5 from the Problem Statement.(d * e) mod phin = 1

It's not obvious how to find d, but there's a simple way to do it in Python, using the "gmpy> library.

Open a **new Terminal window**, not the one
running Python, and execute this command to
download and install a few dependencies and gmpy:

brew install gmp mpfr mpc pip install gmpy

In the Terminal window running python, execute these commands.

We get the value of d, and, to verify it, we see that d*e %phin is indeed 1, as shown below.

e = 5 import gmpy d = gmpy.invert(e, phin) print d, e, d*e %phin

We can only send numbers. Let's convert that message to three bytes of ASCII and then interpret it as a 24-bit binary value.

Hi!

In the Terminal window running python, execute these commands.

We get the value of x, as shown below.

x1 = ord('H') x2 = ord('i') x3 = ord('!') x = x1*256*256 + x2*256 + x3 print x

Execute these commands:

The encrypted message appears, as shown below.

y = x ** e % n print y

Python crashes, as shown below. It cannot handle such large numbers. To compute such a number, we must use the pow() function.

xx = y ** d % n print xx

Execute these commands to restart python and restore all the values we calculated previously:

Your screen should look like the image below. Let's try that decryption again with the pow() function. Execute these commands:

python n = 10142789312725007 p = 100711409 q = 100711423 phin = (p-1) * (q-1) e = 5 import gmpy d = gmpy.invert(e, phin) x1 = ord('H') x2 = ord('i') x3 = ord('!') x = x1*256*256 + x2*256 + x3 y = x ** e % n

Now it works, showing our original message in numerical form.

xx = pow(y, d, n) print xx

Now it works, showing the original message in readable form, as shown below.

xx1 = xx / (256*256) xx2 = (xx - 256*256*xx1) / 256 xx3 = xx - 256*256*xx1 - 256*xx2 msg = chr(xx1) + chr(xx2) + chr(xx3) print xx1, xx2, xx3, msg

OBEY!

*Hint 2: The encrypted message is 16 digits long and ends in 81.*

Use the form
below to put your name on the
**WINNERS PAGE**.

Meghan sends this message to Cueball. Decrypt it.(111036975342601848755221, 13)

Use the form below to put your name on the80564890594461648564443

Meghan sends this message to Rob. Decrypt it.(1234592592962967901296297037045679133590224789902207663928489902170626521926687, 5557)

272495530567010327943798078794037733865151017104532777645776936985235709526002

Use the form
below to put your name on the
**WINNERS PAGE**.

Prime Numbers Generator and Checker

Arbitrary precision of square roots

Posted 3-31-16 by Sam Bowne

Winners pages added 8-6-16