Ada Conformity Assessment Authority Home Conformity Assessment Test Suite ARG Ada Standard

Jeff Cousins

# 7.11 Big Numbers

Predefined Big numbers support (AI12-0208) defines a package Ada.Numerics.Big_Numbers, with child packages Big_Integers and Big_Reals, to support arbitrary precision arithmetic (see RM A.5.6 and A.5.7). Types Big_Integer and Big_Real, and the usual comparison and arithmetic operators, are provided in their respective child packages.
Changes to Big_Integer and Big_Real (AI12-0366) then updates AI12-0208 in the light of implementation experience.
Now for an example, using the RSA algorithm. Value v can be encrypted using:
c = ve mod n
and decrypted using:
v = cd mod n
Both encryption and decryption require a value to be raised to a power (which is often but not always a prime number) and then take the remainder when divided by n which is the product of two (typically large) primes. The fine details of how to choose e and d need not bother us. Executing:
function Power_Mod (M, Exp, N : Integer) return Integer is
((M ** Exp) mod N);
would soon overflow for all but the smallest of values. The risk of overflow can be reduced by taking the remainder for intermediate results, as in the following simple algorithm:
function Power_Mod (M, Exp, N : Integer) return Integer is
Result : Integer := 1;
begin
for Count in 1 .. Exp loop
Result := (@ * M) mod N;
end loop;
return Result;
end Power_Mod;
This avoids overflow (and performs at least as well as more sophisticated algorithms) for the sort of values typically used in textbook examples. But real world encryption may use values hundreds of digits long, so Integer should be replaced by Big_Integer. An example using Big_Integer in a more sophisticated algorithm is:
function Power_Mod (M, Exp, N : Big_Integer) return Big_Integer is
Result    : Big_Integer := 1;
Temp_Exp    : Big_Integer := Exp;
Mult    : Big_Integer := M mod N;
begin
while Temp_Exp > 1 loop
if Temp_Exp mod 2 /= 0 then
Result := (@ * Mult) mod N;
end if;
Mult := @ ** 2 mod N;
Temp_Exp := @ / 2;
end loop;
Result := (@ * Mult) mod N;
return Result;
end Power_Mod;
In order to make Big Numbers easier to use, User-defined numeric literals (AI12-0249) allows the user to define numeric literals to be used with a (non-numeric) type, using aspects Integer_Literal and Real_Literal to identify a function that will do the interpretation (see RM 4.2.1). For example:
type Big_Integer is private
with Integer_Literal => Big_Integer_Value;
function Big_Integer_Value (S : String) return Big_Integer;
...
Y : Big_Integer := -3;
This is equivalent to:
Y : Big_Integer := - Big_Integer_Value ("3");
Named Numbers and User-Defined Numeric Literals (AI12-0394) extends this to allow named numbers to be used with user-defined numeric literals.
User-defined string literals (AI12-0295) allows the user to define string literals to be used with a non-string type, using aspect String_Literal to identify a function that will do the interpretation. For example:
type Varying_String is private
with String_Literal => To_Varying_String;
function To_Varying_String (Source : Wide_Wide_String)
return Varying_String;
...
X : constant Varying_String := "This is a test";
This is equivalent to:
X : constant Varying_String :=
To_Varying_String (Wide_Wide_String'("This is a test"));
Various issues with user-defined literals (AI12-0325) and Various issues with user-defined literals (part 2) (AI12-0342) sort out some of the details of both user-defined numeric literals and user-defined string literals.