1 ------------------------------------------------------------------------------
3 -- GNAT RUNTIME COMPONENTS --
5 -- S Y S T E M . E X P _ M O D --
10 -- Copyright (C) 1992,1993,1994,1995 Free Software Foundation, Inc. --
12 -- GNAT is free software; you can redistribute it and/or modify it under --
13 -- terms of the GNU General Public License as published by the Free Soft- --
14 -- ware Foundation; either version 2, or (at your option) any later ver- --
15 -- sion. GNAT is distributed in the hope that it will be useful, but WITH- --
16 -- OUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY --
17 -- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License --
18 -- for more details. You should have received a copy of the GNU General --
19 -- Public License distributed with GNAT; see file COPYING. If not, write --
20 -- to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, --
21 -- MA 02111-1307, USA. --
23 -- As a special exception, if other files instantiate generics from this --
24 -- unit, or you link this unit with other files to produce an executable, --
25 -- this unit does not by itself cause the resulting executable to be --
26 -- covered by the GNU General Public License. This exception does not --
27 -- however invalidate any other reasons why the executable file might be --
28 -- covered by the GNU Public License. --
30 -- GNAT was originally developed by the GNAT team at New York University. --
31 -- It is now maintained by Ada Core Technologies Inc (http://www.gnat.com). --
33 ------------------------------------------------------------------------------
35 package body System.Exp_Mod is
47 Result : Integer := 1;
48 Factor : Integer := Left;
49 Exp : Natural := Right;
51 function Mult (X, Y : Integer) return Integer;
53 -- Modular multiplication. Note that we can't take advantage of the
54 -- compiler's circuit, because the modulus is not known statically.
56 function Mult (X, Y : Integer) return Integer is
59 (Long_Long_Integer (X) * Long_Long_Integer (Y)
60 mod Long_Long_Integer (Modulus));
63 -- Start of processing for Exp_Modular
66 -- We use the standard logarithmic approach, Exp gets shifted right
67 -- testing successive low order bits and Factor is the value of the
68 -- base raised to the next power of 2.
70 -- Note: it is not worth special casing the cases of base values -1,0,+1
71 -- since the expander does this when the base is a literal, and other
72 -- cases will be extremely rare.
76 if Exp rem 2 /= 0 then
77 Result := Mult (Result, Factor);
82 Factor := Mult (Factor, Factor);