File : s-expmod.adb
1 ------------------------------------------------------------------------------
2 -- --
3 -- GNAT RUN-TIME COMPONENTS --
4 -- --
5 -- S Y S T E M . E X P _ M O D --
6 -- --
7 -- B o d y --
8 -- --
9 -- Copyright (C) 1992-2014, Free Software Foundation, Inc. --
10 -- --
11 -- GNAT is free software; you can redistribute it and/or modify it under --
12 -- terms of the GNU General Public License as published by the Free Soft- --
13 -- ware Foundation; either version 3, or (at your option) any later ver- --
14 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
15 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
16 -- or FITNESS FOR A PARTICULAR PURPOSE. --
17 -- --
18 -- --
19 -- --
20 -- --
21 -- --
22 -- You should have received a copy of the GNU General Public License and --
23 -- a copy of the GCC Runtime Library Exception along with this program; --
24 -- see the files COPYING3 and COPYING.RUNTIME respectively. If not, see --
25 -- <http://www.gnu.org/licenses/>. --
26 -- --
27 -- GNAT was originally developed by the GNAT team at New York University. --
28 -- Extensive contributions were provided by Ada Core Technologies Inc. --
29 -- --
30 ------------------------------------------------------------------------------
31
32 package body System.Exp_Mod is
33 use System.Unsigned_Types;
34
35 -----------------
36 -- Exp_Modular --
37 -----------------
38
39 function Exp_Modular
40 (Left : Unsigned;
41 Modulus : Unsigned;
42 Right : Natural) return Unsigned
43 is
44 Result : Unsigned := 1;
45 Factor : Unsigned := Left;
46 Exp : Natural := Right;
47
48 function Mult (X, Y : Unsigned) return Unsigned is
49 (Unsigned (Long_Long_Unsigned (X) * Long_Long_Unsigned (Y)
50 mod Long_Long_Unsigned (Modulus)));
51 -- Modular multiplication. Note that we can't take advantage of the
52 -- compiler's circuit, because the modulus is not known statically.
53
54 begin
55 -- We use the standard logarithmic approach, Exp gets shifted right
56 -- testing successive low order bits and Factor is the value of the
57 -- base raised to the next power of 2.
58
59 -- Note: it is not worth special casing the cases of base values -1,0,+1
60 -- since the expander does this when the base is a literal, and other
61 -- cases will be extremely rare.
62
63 if Exp /= 0 then
64 loop
65 if Exp rem 2 /= 0 then
66 Result := Mult (Result, Factor);
67 end if;
68
69 Exp := Exp / 2;
70 exit when Exp = 0;
71 Factor := Mult (Factor, Factor);
72 end loop;
73 end if;
74
75 return Result;
76
77 end Exp_Modular;
78
79 end System.Exp_Mod;