|
|
|
Projects
- Important dates:
- October 30: project proposals due. You must discuss your choice of project with the instructor before this day.
- Decemebr 4: projects due
- No extensions will be granted
You may work on a project by yourself or in a small group.
SUGGESTED PROJECTS
- A fast (polynomial-time) algorithm for factorising numbers into primes is unknown.
However, recently Agrawal, Kayal, and Saxena discovered a way to determine if the number is prime
in polynomial time. Read either the
original paper or its summary elsewhere, write up a short description of the algorithm, and implement it.
- A positive number n is perfect if it equals the sum of all of its divisors less
than n. E.g., 6=1+2+3 or 28=1+2+4+7+14.
A Mersenne prime is a prime number of the form M(k)=2k-1. If M(k)
is prime, then k is necessarily prime (see exercise 1.3.6).
- Prove that if M(k) is a prime number, then n=2k-1M(k) is perfect.
(Hint: compute the sum of all divisors of n.)
- Try to prove the converse of the previous statement for even perfect numbers.
- Write a program that finds even perfect numbers (use the connection with Mersenne primes).
- In Exercise 1.3.8 you were asked to prove that there are infinitely many primes of the
form 4k+3. For this project you will have to find a proof that there are infinitely many primes
of the form 4k+1.
Also, write a program that compares the number of primes of the form 4k+1 and the number of primes of the form 4k+3
for a range of values of k. Can you make any conjectures about the relationship between these numbers?
- In certain situations, the RSA code is vulnerable. For example, if the exponent is small
and the message is short, the message can be deciphered quickly. Discover how this can be done
and write a program implementing this code-breaking.
Alternatively, you may discuss the mathematics of other real-life vulnerabilities of the RSA code. More
information can be found on
the RSA Labs website.
- There are public key cryptography algorithms other than RSA. One of them is the ElGamal algorithm.
Give a brief description of ElGamal, explain the mathematics behind it, and implement it.
- We define a group as a set with a particular operation. However, a group can
be also defined as a collection of strings of letters (and the group operation is
just putting two words together). This approach to groups is called "Combinatorial groups
theory." Learn as much of it as you can and write a report. In particular, you
will have to explain why the two definitions of a group are equivalent.
- A group G is simple if its only normal subgroups are the trivial subgroup
and G itself. Simple finite groups are the "building blocks" out of which other finite groups
may be constructed. The classification of simple groups is nearing completion:
some proofs need to be ironed out, but it is believed that all such groups
are known. Learn what these groups are and write a short (4 or 5 typed pages) report.
- Discuss Vigenere and Hill ciphers (encryption, decryption). Write a program that
can perform encryption, decryption using such methods. Discuss vulnerability via
statistics of blocks in the encrypted test. Write a program that does cryptanalysis
for such cyphers based on statistics of blocks (for small sizes of blocks).
- Write a short (4 or 5 typed pages) paper on the mathematical contributions of a
number theorist or an algebraist. Note: This is not a biography — you will have to describe
mathematical results, their proofs, etc.
- Write a short (4 or 5 typed pages) historical report on material discussed in the
course. You will need to describe mathematical results, outline proofs, etc.
|
|
|
