Large-Integer 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

In the above, "integer" means an arbitrarily large integer. Let me stress that it will not be sufficient to use the built-in 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.

Pari-GP

The platform that I will use to demonstrate in class (although I don't do a lot of demonstrations) is called Pari-GP. Pari is a library of functions (written in C, I think). GP is a simple character-based interactive front-end for Pari that runs in a terminal window. There is a Pari home page with more information. Pari-GP has way more facilities than we will ever use.

Pari-GP 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 open-source mathematics software system licensed under the GPL. It combines the power of many existing open-source packages into a common Python-based interface. Available from http://www.sagemath.org/

Matlab
Matlab is a commercial programming environment specializing in the manipulation of matrices. It has a full-fledged C-like language and a particularly nice programmer's interface. However, in order to do large-integer 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 command-line desk calculator with some large-integer 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.uni-muenchen.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 C-language library for doing arbitrary-precision 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 arbitrary-precision arithmetic. More humane syntax than gmp. Installed on PV. Free. Available from Victor Shoup's personal page. I believe he supplies a library pre-compiled for Win 9x.
python, java.
Both of these languages have large-number arithmetic built-in. 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.