Instructions:

1. Try to use your own calculations instead of readymades!
2. If you manage to do these without using a computer please contact Shakuntala Devi.

Number Theory and Cryptology

Assignment I

1 RSA

The following is an example RSA system. (We have used chunks of 4 digits to break up large numbers).

What	Number
Modulus						1120	3636	1351
	5716	6077	1438	9947	7366	2821	0498	6262
	4870	2237	7405	1359	1447	2052	5841	5977
Public Key							0015	8597
Secret						0029	9734	7246
	2576	1241	7972	6959	1999	9270	7786	7766
	5723	3432	0430	7514	6108	7174	6174	9337

The following was sent over the channel

Decrypt the (date) that is the message. Then add a date of your own in the same format; encrypt it and send it to me!

2 Trial Division

Find the first number larger than 2³² that is not divisible by the first 1000 primes. Is this number a prime?

3 Twin primes

The twin prime conjecture says that there are infinitely many pairs of primes (p, q) so that p - q = 2. Try to verify this conjecture by finding a pair (p, q) larger than 100000000001 ( = 10¹¹ + 1) which is likely to be a prime pair.