Re: Bignum modular types in Ada95

[Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk>]

It seems that GNAT, Aonix, and Intermetrix do not support any
arithmetic that does not fit into 64-bit registers at the moment,
therefore Ada lines such as

  type Unsigned1024 is range 0..2**1024-1;

cannot be compiled. :-(

Suggestion:

Would any of the major compiler designers (especially the
GNAT team) be interested in add such bignum support to their
compiler? I think, this would be a very nice distinguishing
feature over the competition and over C/C++/Java compilers!

A question for the language lawyers:

Was the idea of having "range 0..2**1024-1" integer variables
even considered when Ada95 was drafted or are there any detail
problems in the language that would be an obstacle in such an
extention of a compiler?

It would also be nice to have some test code for bignum arithmetic
in the Ada95 validation test suite that can be used to check
quickly whether an Ada95 compiler handles >>64-bit arithmetic
correctly (both integer and modular).

Optimized assembler code for bignum arithmetic is already freely
available in the GNU MultiPrecision library on

  ftp://nic.funet.fi/pub/gnu/gnu/gmp-2.0.2.tar.gz

but this still would have to be integrated with the gcc backend.

Handling 1024-bit integer arithmetic in the Ada compiler and not in
some library package has the advantage that the compiler will later
be able to do much better optimization (e.g. automatic register
allocation), once we get CPUs with 1024-bit integer registers and
ALUs, which I expect to happen in the next three years. This way,
if we could already write now portable bignum code, all this code
could just be recompiled to be much more efficient without any
changes to the source on the next generation processors with
a Crypto-ALU.

Markus

-- 
Markus G. Kuhn, Security Group, Computer Lab, Cambridge University, UK
email: mkuhn at acm.org,  home page: <http://www.cl.cam.ac.uk/~mgk25/>