Overview of Ada 2022
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:
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;
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.
© 2021, 2022 Jeff Cousins
