Re: Bignum modular types in Ada95

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

Brian Rogoff wrote:
> I know of a few high end
> CPUs which use a 128 bit wide bus to connect to external cache, but
> nothing which even comes close to having 1024 bit registers. I just don't
> think that's a desirable way to do 1024-bit wide arithmetic on a general
> purpose CPU for the next 5-10 years at least. I think 64-bit registers
> will be the norm for high end desktop machines and other non-embedded
> CPUs in the first decade of the 21st century.

The cryptosupport in the next generation of workstation processors
will not mean that the full internal bus will get 1024 bits wide!
I expect 64-bit there to become the standard within 5 years and it
will probably stay this way for a very long time.

The 1024-bit registers will be more like the floating-point registers
that we have already today: only few, only special operations,
and much larger than the bus width. It is also not necessary to
actually implement full 1024-bit registers to do 1024 bit operations:
If you have suitably designed 256-bit registers and arithmetic
logic, then you can easily fold 1024, 768, and 512 bit operations
efficiently into this hardware by just iterating a few times.

You can get today already microcontrollers for security applications
from Siemens, Phillips, SGS Thompson, Dallas Semiconductor,
Motorola, etc. that feature hardware support for efficient 768 or
1024 bit modular integer arithmetic (especially exponentiation).

I would suggest that System.Max_int be redefined to show the largest
integer word size that the processor can handle efficiently (usually
2**31-1 or 2**63-1) in case the compiler supports bignum integers
and does not actually have a fixed largest integer value. Does
this sound reasonable?

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/>