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-- As a special exception under Section 7 of GPL version 3, you are granted -- 19-- additional permissions described in the GCC Runtime Library Exception, -- 20-- version 3.1, as published by the Free Software Foundation. -- 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 32package 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 79end System.Exp_Mod; 80