Ada Conformity Assessment Authority      Home Conformity Assessment   Test Suite ARGAda Standard
Overview of Ada 2022
Jeff Cousins
Contents   Index   Search   Previous   Next 

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;
   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:
with Ada.Numerics.Big_Numbers.Big_Integers;
use  Ada.Numerics.Big_Numbers.Big_Integers;
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;
   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.

Contents   Index   Search   Previous   Next 
© 2021, 2022 Jeff Cousins