The AKS Primality Test
Project is due on November 14 @
11.59pm. Email your file to yueping @
cs.tamu.edu.
Documentation and
submission guidelines [ps][pdf]
Important
Update:
- CSG failed to install the gmp library.
- Please assume that a local copy of the gmp library is installed
above your directory
(i.e., your automake file should generate
-I../ and -L../ options).
You can use aks_LDFLAGS and INCLUDES in your automake file to set such options.
- We will use a no-nonsense approach to the include/library path problem:
You can adjust your automake file when you demonstrate your program to the TA.
- Please include a --slow switch which will disable your optimizations in steps 1 and 2, so that we are able to test step 3.
- You can use EXTRA_DIST in your automake file to include documentation such as doc.dvi when you make the distribution with make dist.
- You need only deliver the result of test1 until the deadline.
Demonstrate your program to Yueping Zhang on Friday.
Task
Your task is to write an efficient implementation of the AKS primality
test in C or C++.
The name of your executable should be aks. The usage of your program should be as follows:
aks [--verbose] integerA integerB
In other words, you give two integers A and B with B ≥ A ≥ 2
as input. The program will test all integers in the range from A to B
and will determine whether they are prime or not. For example,
aks 2 5 should produce the output
2 is prime
3 is prime
4 is composite
5 is prime
Note that the output should be exactly in this form, namely a number
followed by one space, followed by the string `is prime' or by the
string `is composite'.
If aks is called with the option --verbose then the
output should be of the form
2 step 1, 2 is prime
2 step 1, 2 is prime
4 step 1 is composite
The steps denote the event that you enter
step 1 (is n is a prime power?),
step 2 (has n small factors?),
step 3 (the polynomial congruence test).
Packaging
Your program should come in a package of the form gzipped tar file called
YourFirstname_Lastname.tgz
Expanding this tar ball should create a directory YourFirstname_Lastname,
which contains all source files, documentation, copyright notice, etc.
In other words, all the information that we need to grade your project.
After entering your directory, we should be able to create the executables
by typing ./configure followed by make.
The information on the GNU build system given below will help you to
create this convenient packaging. If you have never used
automake and autoconf before, then you will see that
this is simple and fun.
Before you hand in any of your programs, make sure that they compile on the
UNIX system of the department, as well as on a Windows/cygwin combination.
Requirements (partial list)
- Your implementation should use the GNU C compiler
gcc or the GNU C++ compiler g++.
- You are allowed to use the GNU GMP
library, which implements a multipresicision integer arithmetic.
- Avoid machine specific performance improvements
(in particular, do not use any assembly language parts).
- Do not use other libraries
(of course with the exception of the C/C++ standard libraries).
- Follow precisely all instructions given below (frequently check back for updates).
Aggie code of honor
You are required to document all sources of information that you have
used in the course of producing your project. DO NOT DOWNLOAD AND
MODIFY PROGRAMS FROM THE WEB OR ANY OTHER SOURCE. Write the program
code completely on your own. You are allowed to use the GNU GMP
library, which will simplify your task enormously.
Documentation
- Description of the AKS Primality Test
- Packaging
- GMP
- GMP home page
- Installing GMP is usually simply done by ./configure and make
- On a SPARC v9 64 bit architecture (such as interactive), installation is done by typing
./configure gcc_64_ldflags="-Wc,-m64" followed by make
- Programming in general
- GNU coding standards
- Keep it always simple and clear.
- If you are confident, try to make it fast.