LargeInteger Arithmetic
The computational demands of modern cipher systems center around
ordinary arithmetic of large integers. These days, that means several
hundred decimal digits. In order to try out some of these
cryptographic algorithms, we will need a facility that can do these
computations.
There is a lot of software out available that offers these
facilities. At the minimum, the package should include
Addition, subtraction and
multiplication of integers;
Quotient and remainder when one
integer is divided by another (ie., integer division and `mod');
Integer exponentiation and multiplicative inverses modulo an
integer (ie., a^b mod c, where a,b,c are integers)
In the above, "integer" means an arbitrarily large
integer. Let me stress that it will not be sufficient to use
the builtin arithmetic in a typical C compiler to do the assignments
in a typical cryptography course. Of course, it would be nice if the
platform you choose offers additional facilities like the ability to
format output and write little programs. But you can probably get by
without those.
I urge you, especially if you are taking the course by distance
education, to investigate one of these systems as soon as possible.
I'll try to think up a few "exercises" you can use to test
your system out. What follows is a brief discussion of some of the
packages that are out there. Much of this commentary was written in
December 1999, so it may be a bit out of date. If you don't already
know how to use one of these packages, I'd recommend that you try
Pari. It is free, fairly easy to use, and available precompiled for
most systems.
PariGP
The platform that I will use to demonstrate in class (although I
don't do a lot of demonstrations) is called PariGP. Pari is a
library of functions (written in C, I think). GP is a simple
characterbased interactive frontend for Pari that runs in a
terminal window. There is a Pari home
page with more information. PariGP has way more facilities than
we will ever use.
PariGP is available for UNIX, XP and the Macintosh. It can be
downloaded from the above URL. The download will come with a tutorial
and a user's guide. I recommend that you browse sections 1,2,4 of the
tutorial, and chapters 1 and 2 of the user's guide. While reading,
keep in mind that this system is primarily aimed at researchers in
number theory, so a lot of stuff that you won't understand creeps in
to the commentary.
Other Packages
Here are some other packages that I am aware of. I certainly don't
discourage you from trying one of these. If you find them superior to
Pari, by all means, tell me about it. Of course, if you already know
how to use one of these, it makes sense to use it instead of learning
pari.
"Big" Packages
 Maple

Big, fancy symbolic algebra package. Has everything you could
possibly want, including extensive documentation. No longer
available at ISU. Expensive to buy.

Mathematica

Similar to maple. If you already know it, it will do everything you
want. ISU has a site
license. Available in the Math Department lab (449 Carver).
Even more expensive than maple.

GAP4

Similar in flavor to Pari. But designed for group theory instead of
number theory. Better documentation, but bigger. Free. Available for
download from this site

SAGE

Sage is a free opensource
mathematics software system licensed under the GPL. It combines
the power of many existing opensource
packages into a common Pythonbased interface. Available from
http://www.sagemath.org/


Matlab

Matlab is a commercial programming environment specializing in the
manipulation of matrices. It has a fullfledged Clike language and
a particularly nice programmer's interface. However, in order to do
largeinteger arithmetic, you need the Symbolic Math toolbox. The
Iowa State
student license does not include the toolbox. It is possible
that the Engineering College offers the Symbolic Math toolbox, I'm
not sure.


"Little" Packages
 Gnu dc

This is the classical UNIX commandline desk calculator with some
largeinteger enhancements. Nothing fancy, but I think it will do
the job. It came installed with my recent version of RedHat Linux.
Free. Available from any gnu
mirror site. There is also gnu bc. I'm not sure
of the relationship to dc.

Aribas

Claims to be a desk calculator with arbitrary precision.
Documentation in German. Available from
ftp://ftp.mathematik.unimuenchen.de/pub/forster/aribas.

Calc

Another desk calculator. Looks promising, but I haven't tried it.
Let me know if it works. Available for all platforms from
http://www.numbertheory.org/calc/krm_calc.html.

For programmers
 gnu gmp

This is a Clanguage library for doing arbitraryprecision
arithmetic. Very extensive. The syntax is a pain. Installed on PV.
Free. Available from any gnu
mirror site. A copy came installed with my RedHat Linux. It
seems to compile nicely on any UNIX platform with gcc. It seems to
be possible to compile under Win9x, but there are pitfalls. Many of
my students have decided that ntl is easier to use.

ntl

A C++ language library for arbitraryprecision arithmetic. More
humane syntax than gmp. Installed on PV. Free. Available from Victor
Shoup's personal page. I believe he supplies a library
precompiled for Win 9x.

python, java.

Both of these languages have largenumber arithmetic builtin. If
you know one of them, it should be fine. If not, I think it is
overkill to learn it just for this course. I don't know how
efficient they are. (By the way: someone tried using perl
last year for the course, but it turned out to be hopelessly slow
for this.) Let me know if one of these works for you. They are both
free. I don't know much about availability. (But python, at least,
came with RedHat LInux.)

Finally, I include the software
sources for number theorists, which has a huge list of possible
options.
Back to cryptography class home page.