Bignum modular types in Ada95

Bignum modular types in Ada95

[Markus Kuhn]

One of the especially nice things about Ada seem to be the modular
types. Many of the calculations in asymmetric cryptography are done
over the integers modulo N, where N is a huge number (typically
1024 bits long or more).

I wonder how many Ada compilers support bignum arithmetic directly
without any special library calls, as in

  type Unsigned1024 is range 0..2**1024-1;
  Modulus, Public_Key: Unsigned1024;
  type Message is mod Modulus;
  Clear_Text, Cipher_Text: Message;

  Cipher_Text := Clear_Text ** Public_Key;

Considering that the next generation of server processors
will feature 1024-bit registers and hardware for fast modular
exponentiation, it is nice to know that Ada95 has already the
language constructs available today to use these forthcoming
capabilities comfortably. Neither C nor Java has. I wonder
however, whether existing Ada95 compilers for existing processors
do already support bignum modular arithmetic in a (certainly
slower) software emulation. If not, bignum arithmetic would not be
a portable feature and would therefore be of limited use once
the crypto-coprocessor with suitable hardware registers and
ALUs become available.

Which Ada95 compilers do support 1024-bit integers today and can
do an efficient modular exponentiation over them?

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

Re: Bignum modular types in Ada95

[Dmitriy Anisimkov]

Hello.

Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk>
> One of the especially nice things about Ada seem to be the modular
> types. Many of the calculations in asymmetric cryptography are done
> over the integers modulo N, where N is a huge number (typically
> 1024 bits long or more).

The GNAT, Aonix and Intermetrix compiler not support integer/modular
numbers more then 64 bit. But I have implemented the numbers which can
allocate more then 64bit, theoreticaly up to 2_000_000_000 bits. I have
implemented operations "+", "-", "*", "/", ">" ,"<", ">=", "<=", "=",
Shift. I plan to implement "and","or" shortly. I still not strongly test
this library and interesting to do this under the real application. I'm
ready to grant free help of using this library and to listen any
suggestions. I develop it under the GNAT and now porting it to the AONIX
ObjectADA for Windows. If you want to use this library, tell me, and I'm
send it to you.

Dmitriy Anisimkov. ts@quadrat.omsk.su

Re: Bignum modular types in Ada95

[Nick Roberts]

The message from this post for compiler writers is crystal clear!

-- 

Nick Roberts ================================================
Croydon, UK                                 =================
                                                   ==========
Proprietor, ThoughtWing Software                       ======
Independent Software Development Consultant              ====
Nick.Roberts@dial.pipex.com                               ===
Voicemail & Fax +44 181-405 1124                          ===

   I live not in myself, but I become
   Portion of that around me; and to me
   High mountains are a feeling, but the hum
   Of human cities torture.
                                     -- Byron [Childe Harold]


Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> wrote in article
<34CE568C.55D7E23D@cl.cam.ac.uk>...
> One of the especially nice things about Ada seem to be the modular
> types. Many of the calculations in asymmetric cryptography are done
> over the integers modulo N, where N is a huge number (typically
> 1024 bits long or more).
[...]
> Which Ada95 compilers do support 1024-bit integers today and can
> do an efficient modular exponentiation over them?

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

Re: Bignum modular types in Ada95

[Larry Kilgallen]

In article <01bd2b92$b639c1e0$64fc82c1@xhv46.dial.pipex.com>, "Nick Roberts" <Nick.Roberts@dial.pipex.com> writes:
> The message from this post for compiler writers is crystal clear!

Message being that a full implementation could result in two sales,
one to each of the major toolkit vendors who currently program in C
and distribute their toolkits in object code format ?

I would be quite happy if my crypto toolkit vendor switched to Ada.
While you are at it, please arrange for world peace and an end to
global warming.

Larry Kilgallen

> Nick Roberts ================================================
> Croydon, UK                                 =================
>                                                    ==========
> Proprietor, ThoughtWing Software                       ======
> Independent Software Development Consultant              ====
> Nick.Roberts@dial.pipex.com                               ===
> Voicemail & Fax +44 181-405 1124                          ===
> 
>    I live not in myself, but I become
>    Portion of that around me; and to me
>    High mountains are a feeling, but the hum
>    Of human cities torture.
>                                      -- Byron [Childe Harold]
> 
> 
> Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> wrote in article
> <34CE568C.55D7E23D@cl.cam.ac.uk>...
>> One of the especially nice things about Ada seem to be the modular
>> types. Many of the calculations in asymmetric cryptography are done
>> over the integers modulo N, where N is a huge number (typically
>> 1024 bits long or more).
> [...]
>> Which Ada95 compilers do support 1024-bit integers today and can
>> do an efficient modular exponentiation over them?
> 
>> Markus G. Kuhn, Security Group, Computer Lab, Cambridge University, UK
>> email: mkuhn at acm.org,  home page: <http://www.cl.cam.ac.uk/~mgk25/>
> 

Re: Bignum modular types in Ada95

[Nick Roberts]

Addendum

I have always assumed (perhaps wrongly!) that decimal types would be
implemented on many machines in BCD (packed ot not), in an arbitrary number
of multiple machine words (however many are required).  In these cases,
something like bignums are supported -- or easily supportable -- anyway.

On the other hand, one might argue that decimal types should be implemented
in the same way as fixed types, on the grounds that this implementation
will have been chosen for maximum performance (rather than flexibility, or
the requirements of the Information Systems special annex).

Perhaps a sensible compromise would be for compiler providers to adopt the
convention that fixed types are implemented to make the best out of the
underlying hardware, but decimal types are implemented for maximum
flexibility and consistency of operation?

Of course, that doesn't preclude the provision of built-in bignum
capability for fixed types: these would undoubtedly be most suitable for
the cryptographic calculations Markus was talking about.

[editor's note: slightly late night post after a whiskey :-]

-- 

Nick Roberts

Re: Bignum modular types in Ada95

[Robert Dewar]

Nick said

<<On the other hand, one might argue that decimal types should be implemented
in the same way as fixed types, on the grounds that this implementation
will have been chosen for maximum performance (rather than flexibility, or
the requirements of the Information Systems special annex).
>>

One would think the most reasonable approach is to let this depend
on Machine_Radix, that is why it is there!

Re: Bignum modular types in Ada95

[Nick Roberts]

But Robert, this doesn't answer the question of what the compiler does by
default.

-- 

== Nick Roberts ================================================
== Croydon, UK                       ===========================
==                                              ================
== Proprietor, ThoughtWing Software                   ==========
== Independent Software Development Consultant            ======
== Nick.Roberts@dial.pipex.com                              ====
== Voicemail & Fax +44 181-405 1124                          ===
==                                                            ==
==           I live not in myself, but I become               ==
===          Portion of that around me; and to me             ==
====         High mountains are a feeling, but the hum        ==
=======      Of human cities torture.
===========                             -- Byron [Childe Harold]


Robert Dewar <dewar@merv.cs.nyu.edu> wrote in article
<dewar.886366928@merv>...
> Nick said
> 
> <<On the other hand, one might argue that decimal types should be
implemented
> in the same way as fixed types, on the grounds that this implementation
> will have been chosen for maximum performance (rather than flexibility,
or
> the requirements of the Information Systems special annex).
> >>
> 
> One would think the most reasonable approach is to let this depend
> on Machine_Radix, that is why it is there!

Re: Bignum modular types in Ada95

[Robert Dewar]

Nick said

<<But Robert, this doesn't answer the question of what the compiler does by
default.
>>

Talking about the default representation of decimal fixed.



The answer is that decimal fixed is like COMPUTATIONAL in COBOL, the
semantics of arithmetic on this type and the set of values are well
specified, but the *representation* is implementation dependent.

Re: Bignum modular types in Ada95

[Markus Kuhn]

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

Re: Bignum modular types in Ada95

[Brian Rogoff]

On Wed, 28 Jan 1998, Markus Kuhn wrote:

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

Could you point me to the datasheet for this CPU? 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. Do you have some inside info 
on quantum dot devices you want to share :-)

-- Brian

Re: Bignum modular types in Ada95

[Markus Kuhn]

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

Re: Bignum modular types in Ada95

[Brian Rogoff]

On Thu, 29 Jan 1998, Markus Kuhn wrote:
> The cryptosupport in the next generation of workstation processors
> will not mean that the full internal bus will get 1024 bits wide!

OK, I misunderstood you then.

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

True even if you have 64 (or 32 or ...) bit registers of course.

> 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).

Could you point me to some datasheets for some of these parts? A part
number, or a URL for the Acrobat file would be helpful. I'm still not sure 
we're on the same page, so to speak. 

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

I'm not sure what this would mean. Scalar types are passed by value, and
there would seem to be a conflict. I agree with your general point
about the growing importance of cryptographic applications and the
nice match to Ada 95's modular types, but it seems that what you want 
(very big modular types) will be very hard to achieve.

-- Brian

Re: Bignum modular types in Ada95

[Robert Dewar]

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

I am not sure why you think GNAT customers might be especially interested
in such a capability, but so far we have seen zero demand from our customers
for such a feature, so there is no interest so far.

Re: Bignum modular types in Ada95

[Tarjei T. Jensen]

Robert Dewar wrote:
> 
> <<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!
> >>
> 
> I am not sure why you think GNAT customers might be especially interested
> in such a capability, but so far we have seen zero demand from our customers
> for such a feature, so there is no interest so far.

Some would be interested I guess if suitable libraries were available.
However the party would have to show enough interest to be willing to
finance the libraries as well. Not many of those I fear.

I assume that there would be some performance enhancement in having
arbitrary precision (e.g. up to 4kb) over doing it in 32bit chunks with
an emulation library. If such an increase would be worthwhile for Ada
advocacy purposes I don't know.

It would be useless to have this feature if all applications called
emulation libraries in C. Or if the Ada code was translated from C.

Greetings,

-- 
// Tarjei T. Jensen 
//    tarjei@online.no || voice +47 51 62 85 58
//   Support you local rescue centre: GET LOST!

Re: Bignum modular types in Ada95

[Robert Dewar]

Tarjei said

<<It would be useless to have this feature if all applications called
emulation libraries in C. Or if the Ada code was translated from C.
>>

Why? What possible concern is it to the user whether they call a library
written in C or written in Ada?

Re: Bignum modular types in Ada95

[Tarjei T. Jensen]

Robert Dewar wrote:
> 
> Tarjei said
> 
> <<It would be useless to have this feature if all applications called
> emulation libraries in C. Or if the Ada code was translated from C.
> >>
> 
> Why? What possible concern is it to the user whether they call a library
> written in C or written in Ada?

None whatsoever. I was trying to say that if more or less arbitrary
precision arithmetic were implemented native in Ada it would be a waste
of time if people did not use it.

One reason for not using such a facility even if it were faster than a
emulation library, would be that the descriptions of the cryptographic
algorithms I have seen to date assumes 32 bit C. Of course people less
mathematically challenged than me would have less of a problem.

If Knuth releases anything on these algorithms we will be treated with
an implementation in 32 bit assembly code. So much for computer
science....

Greetings,

-- 
// Tarjei T. Jensen 
//    tarjei@online.no || voice +47 51 62 85 58
//   Support you local rescue centre: GET LOST!

Re: Bignum modular types in Ada95

[Keith Thompson]

If an implementation wants to provide a "bignum" type (say, a 1024-bit
or infinite-precision signed or unsigned integer type), it can do so by
taking advantage of RM95-3.5.4(26) and creating nonstandard integer types.
The implementation may place arbitrary restrictions on the operations
it supports for such types.

Here's the paragraph:

	An implementation may provide nonstandard integer types,
	descendants of root_integer that are declared outside of
	the specification of package Standard, which need not have
	all the standard characteristics of a type defined by an
	integer_type_definition. For example, a nonstandard integer
	type might have an asymmetric base range or it might not be
	allowed as an array or loop index (a very long integer). Any type
	descended from a nonstandard integer type is also nonstandard. An
	implementation may place arbitrary restrictions on the use
	of such types; it is implementation defined whether operators
	that are predefined for ``any integer type'' are defined for a
	particular nonstandard integer type. In any case, such types are
	not permitted as explicit_generic_actual_parameters for formal
	scalar types -- see 12.5.2.

As far as I know, no implementation has taken advantage of this permission.

-- 
Keith Thompson (The_Other_Keith) kst@cts.com <*>
^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H^H
San Diego, California, USA
Trying to keep my daily caffeine intake between the RDA and the LD50.

Re: Bignum modular types in Ada95

[Markus Kuhn]

Robert A Duff wrote:
> >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.
> 
> Are you talking about special-purpose hardware?  I doubt if 1024-bit
> registers will exist in general-purpose computers any time soon.  (I
> reserve the right to redefine "soon" at will.)

No, I am talking about the standard off-the-shelf Pentium
successor in a few years, not about any exotic special hardware.
IPv6 and electronic commerce will make it necessary that normal
workstations can to thousands of 1024-bit modexp operations per
second for authentication protocols. This is commonly expected to
be the next major functional extention after MMX.

20-dollar smartcard microcontrollers have such 1024-bit registers/ALUs
already available today. It is just a matter of time until we
see them in workstation processors.

> Anyway, having the feature "built in" gives other advantages: literals,
> range checking, case_statements, etc.  None of that works with some
> library package (unfortunately).

Agree. Dear Ada compiler developers, please have a look again at
builtin bignum support!

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

Re: Bignum modular types in Ada95

[Nick Roberts]

Point taken, but I have another question.  Traditional bignums (e.g. in
LISP) are dynamically extensible: they can change size during run-time to
fit the actual value stored.  For some applications, this approach would
make sense, but for others it may not.  So what approach to take:
dynamically resizing, statically sized, or both?  And if both, how to
choose (depending on the range, by a representaion clause, by a pragma, or
something else)?

-- 

== Nick Roberts ================================================
== Croydon, UK                       ===========================
==                                              ================
== Proprietor, ThoughtWing Software                   ==========
== Independent Software Development Consultant            ======
== Nick.Roberts@dial.pipex.com                              ====
== Voicemail & Fax +44 181-405 1124                          ===
==                                                            ==
==           I live not in myself, but I become               ==
===          Portion of that around me; and to me             ==
====         High mountains are a feeling, but the hum        ==
=======      Of human cities torture.
===========                             -- Byron [Childe Harold]


Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> wrote in article
<34D04FFD.41C6@cl.cam.ac.uk>...
> Robert A Duff wrote:
> > >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.
> > 
> > Are you talking about special-purpose hardware?  I doubt if 1024-bit
> > registers will exist in general-purpose computers any time soon.  (I
> > reserve the right to redefine "soon" at will.)
> 
> No, I am talking about the standard off-the-shelf Pentium
> successor in a few years, not about any exotic special hardware.
> IPv6 and electronic commerce will make it necessary that normal
> workstations can to thousands of 1024-bit modexp operations per
> second for authentication protocols. This is commonly expected to
> be the next major functional extention after MMX.
> 
> 20-dollar smartcard microcontrollers have such 1024-bit registers/ALUs
> already available today. It is just a matter of time until we
> see them in workstation processors.
> 
> > Anyway, having the feature "built in" gives other advantages: literals,
> > range checking, case_statements, etc.  None of that works with some
> > library package (unfortunately).
> 
> Agree. Dear Ada compiler developers, please have a look again at
> builtin bignum support!

Re: Bignum modular types in Ada95

[Mats Weber]

> No.  Not really.  I guess there's one minor point: there's this thing
> called System.Max_Int, and it has to be some finite integer.  And some
> people write code that uses Max_Int to produce "the largest supported
> signed integer type", and, perhaps, expect that type to be reasonably
> efficient.  It's mainly that the Ada 9X project had no mandate to make
> any such wild-eyed changes.

And there is the fact that parameters of elementary types have to be passed by
copy, something you probably don't want for types with sizes around 1000 bits.

> Every Ada compiler includes a package for arbitrary-range integer
> arithmetic -- it's required, to do static expressions properly at
> compile time.  It's annoying (to me) that this implementation burden is
> required, but the user can't take advantage of it, portably, except in
> the case of static expressions.

I think it's reasonable the way it is (required in the compiler but not in the
runtime) because it's not needed for most applications, and the compiler can
have a quick and dirty, slow implementation that leaks memory without anyone caring.

The implementation, and even the spec of a bignum package is not that easy to
standardize, here are a few problems:

- Allow numbers of any size ? This requires tagged types and finalization,
which costs a lot in performance.

- Are the numbers _really_ big ? In this case, you will implement
multiplication and division using Fourier transforms, which is overkill for
medium size bignums.

- Only integers or reals as well ?

- ...

Re: Bignum modular types in Ada95

[Markus Kuhn]

Robert A Duff wrote:
> >- Are the numbers _really_ big ? In this case, you will implement
> >multiplication and division using Fourier transforms, which is overkill for
> >medium size bignums.
> 
> I don't care.  I'll be happy with an implementation that works.

Fair. Of course, compiler developers who strive for excellency would
be smart and would determine the 0..2^n over which FFT is faster
than simple multiplication and call an FFT routine for the types
where this is justified (say over 0..2**128 or so).

But I fully agree with you: Having it operational at all is
important first to ensure portability. Then you can worry about
efficiency.

If we have arbitrary length string operations, arbitrary
length integer operations shouldn't be that much additional
hazzle, and the popularity that arithmetic with huge numbers
has gained through the numerous asymmetric cryptoalgorithms
out there (RSA, Diffie-Hellman, ElGamal, DSS, all the new
elliptic curve stuff, etc.) surely justifies the investment.

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

Re: Bignum modular types in Ada95

[Mats Weber]

> If we have arbitrary length string operations, arbitrary
> length integer operations shouldn't be that much additional
> hazzle, and the popularity that arithmetic with huge numbers
> has gained through the numerous asymmetric cryptoalgorithms
> out there (RSA, Diffie-Hellman, ElGamal, DSS, all the new
> elliptic curve stuff, etc.) surely justifies the investment.

Yes, but for all such applications, efficiency is so important that it must be
part of the specification, and I think that if you get into coding such
applications, then you will be much better off if you have complete control
over your bignum algorithms.

Re: Bignum modular types in Ada95

[Markus Kuhn]

Mats Weber wrote:
> 
> > If we have arbitrary length string operations, arbitrary
> > length integer operations shouldn't be that much additional
> > hazzle, and the popularity that arithmetic with huge numbers
> > has gained through the numerous asymmetric cryptoalgorithms
> > out there (RSA, Diffie-Hellman, ElGamal, DSS, all the new
> > elliptic curve stuff, etc.) surely justifies the investment.
> 
> Yes, but for all such applications, efficiency is so important that it must be
> part of the specification, and I think that if you get into coding such
> applications, then you will be much better off if you have complete control
> over your bignum algorithms.

Not once there is hardware support available for such operations
and we still want to product strictly portable code.

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

Re: Bignum modular types in Ada95

[Nick Roberts]

Besides which the package implementation can always be used: it is not
denied by providing built-in bignum support!

-- 

== Nick Roberts ================================================
== Croydon, UK                       ===========================
==                                              ================
== Proprietor, ThoughtWing Software                   ==========
== Independent Software Development Consultant            ======
== Nick.Roberts@dial.pipex.com                              ====
== Voicemail & Fax +44 181-405 1124                          ===
==                                                            ==
==           I live not in myself, but I become               ==
===          Portion of that around me; and to me             ==
====         High mountains are a feeling, but the hum        ==
=======      Of human cities torture.
===========                             -- Byron [Childe Harold]


Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> wrote in article
<34D1ED17.D788435@cl.cam.ac.uk>...
> Mats Weber wrote:
> > 
> > > If we have arbitrary length string operations, arbitrary
> > > length integer operations shouldn't be that much additional
> > > hazzle, and the popularity that arithmetic with huge numbers
> > > has gained through the numerous asymmetric cryptoalgorithms
> > > out there (RSA, Diffie-Hellman, ElGamal, DSS, all the new
> > > elliptic curve stuff, etc.) surely justifies the investment.
> > 
> > Yes, but for all such applications, efficiency is so important that it
must be
> > part of the specification, and I think that if you get into coding such
> > applications, then you will be much better off if you have complete
control
> > over your bignum algorithms.
> 
> Not once there is hardware support available for such operations
> and we still want to product strictly portable code.

Re: Bignum modular types in Ada95

[Robert Dewar]

Markus says

<<If we have arbitrary length string operations, arbitrary
length integer operations shouldn't be that much additional
hazzle, and the popularity that arithmetic with huge numbers
has gained through the numerous asymmetric cryptoalgorithms
out there (RSA, Diffie-Hellman, ElGamal, DSS, all the new
elliptic curve stuff, etc.) surely justifies the investment.
>>

Investment in what? Putting this feature as a primitive feature into
the compiler, I think not. Making available suitable libraries? Sure,
and they have been around for a long long time.

Re: Bignum modular types in Ada95

[Mats Weber]

> True, but the fact remains that I can say "type T is range 1..10**10;"
> on some implementations and not others, and that's a portability
> problem.  The number "10**10" isn't all *that* big -- we're not talking
> about 1000 bits, here.

OK, but you portably say "type T is range 1 .. 10**9;" and that's good enough
for me (to be accurate, it's not formally potable, but it is portable to any
reasonable machine with a compiler that follows implementation advice).

I think it's a good thing that if you say "type T is range ...", then you will
get the machine's built-in arithmetic.

> I don't care.  I'll be happy with an implementation that works.  It
> should be efficient for small numbers, and I don't care if it's
> inefficient for big numbers, and _really_ inefficient for _really_ big
> numbers.

Are you talking about supporting
   type T is range ...
for bignums, or a package declaring a private bignum type and its operations ?

Re: Bignum modular types in Ada95

[Robert Dewar]

Mats said

  <<I think it's a good thing that if you say "type T is range ...", then
  you will get the machine's built-in arithmetic.>>

Note that no one ever guaranteed such a thing. It is certainly NOT true
for GNAT, which implements 64-bit integer arithmetic on all machines,
whether or not there is native 64-bit integer hardware.

Re: Bignum modular types in Ada95

[Robert Dewar]

Mats Weber says

<<I think it's a good thing that if you say "type T is range ...", then you will
>>

Note that no one ever guaranteed such a thing. It is certainly NOT true
for GNAT, which implements 64-bit integer arithmetic on all machines,
whether or not there is native 64-bit integer hardware.

Re: Bignum modular types in Ada95

[Nick Roberts]

I'm fairly sure that arbitrary-precision provision would be sensible for
both integer and fixed-point (possibly including decimal) types, but not
for floating-point types.

The reason for fixed-point support is that there will be many applications
requiring fixed-point types with huge ranges/accuracy (e.g.
astro-navigation (this is not a joke :-)) besides cryptography;
implementation is not an issue, since fixed-point types are (always?)
implemented as integer types anyway.

I suspect that no-one would want to use a floating-point type that couldn't
use the target machine's floating-point hardware.  Some RISC machines might
be able to do arbitrary-length floating point arithmetic (and maybe some
machines of the future), but I'm not sure that there would be a demand for
this functionality, in practice.  Would there?

-- 

== Nick Roberts ================================================
== Croydon, UK                       ===========================
==                                              ================
== Proprietor, ThoughtWing Software                   ==========
== Independent Software Development Consultant            ======
== Nick.Roberts@dial.pipex.com                              ====
== Voicemail & Fax +44 181-405 1124                          ===
==                                                            ==
==           I live not in myself, but I become               ==
===          Portion of that around me; and to me             ==
====         High mountains are a feeling, but the hum        ==
=======      Of human cities torture.
===========                             -- Byron [Childe Harold]


Robert A Duff <robertduff@world.std.com> wrote in article
<EnKEtu.KGp@world.std.com>...
> In article <34D082F9.ABEC0D3B@elca-matrix.ch>,
> Mats Weber  <Mats.Weber@elca-matrix.ch> wrote:
[snip]
> >- Only integers or reals as well ?
> 
> Reals?  No, just integers and rationals, which is exactly what is
> already supported at compile time (e.g. "X: constant :=
> 1_000_000_000_000/3_000_000_000_000;" has to be *exactly* one-third in
> current Ada compilers).  I'm not asking for an exact representation of
> the square root of 2 or pi or e!

Re: Bignum modular types in Ada95

[Robert Dewar]

Robert Duff said

<<True, but the fact remains that I can say "type T is range 1..10**10;"
on some implementations and not others, and that's a portability
problem.  The number "10**10" isn't all *that* big -- we're not talking
about 1000 bits, here.
>>

The standard could certainly have mandated a reasonable minimal range. There
were some such range requirements added to Ada 83, but they are so pathetic
that they are counter-productive, since they imply that it is perfectly
OK to produce a crippled compiler with minimal range capabilities (e.g.
Integer must be at least 16 bits -- wonderful!)

It certainly seems absurd to me if any general purpose Ada compiler does
not implement 64-bit integer arithmetic on all targets at this stage.

Re: Bignum modular types in Ada95

[Robert Dewar]

Bob said

<<No.  Not really.  I guess there's one minor point: there's this thing
called System.Max_Int, and it has to be some finite integer.  And some
people write code that uses Max_Int to produce "the largest supported
signed integer type", and, perhaps, expect that type to be reasonably
efficient.  It's mainly that the Ada 9X project had no mandate to make
any such wild-eyed changes.
>>


Surely you are allowed (but not required) to implement arbitrary precision
for the type Integer'Base?