- 84C9976AA492F507F8F21C8BBEB3B7DC671F8AA45C9479808DFFDA6B62FD23A1891F08740937D5D61B8D5FAD9DA7AD9E890AAA79059C0A1EE69096D877A93577
+ 321CC7F54066CA6F0C7BE85A195A028919076A6775510F99B5C9802F093CB08042770E08E8579376A7558CEB4BA1A0F0F43D437847FD2A89CA30EC8BC48C6177
ffa/libffa/fz_modex.adb
(2 . 7)(2 . 7)
878 ------------------------------------------------------------------------------
879 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
880 -- --
881 -- (C) 2017 Stanislav Datskovskiy ( www.loper-os.org ) --
882 -- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org ) --
883 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html --
884 -- --
885 -- You do not have, nor can you ever acquire the right to use, copy or --
(17 . 17)(17 . 18)
887 ------------------------------------------------------------------------------
888 ------------------------------------------------------------------------------
889
890 with Words; use Words;
891 with W_Shifts; use W_Shifts;
892 with FZ_Basic; use FZ_Basic;
893 with FZ_Pred; use FZ_Pred;
894 with FZ_Shift; use FZ_Shift;
895 with FZ_Mul; use FZ_Mul;
896 with FZ_Sqr; use FZ_Sqr;
897 with FZ_Divis; use FZ_Divis;
898 with FZ_Barr; use FZ_Barr;
899
900
901 package body FZ_ModEx is
902
903 -- Modular Multiply: Product := X*Y mod Modulus
904 -- (Conventional) Modular Multiply: Product := X*Y mod Modulus
905 procedure FZ_Mod_Mul(X : in FZ;
906 Y : in FZ;
907 Modulus : in FZ;
(54 . 7)(55 . 7)
909 end FZ_Mod_Mul;
910
911
912 -- Modular Squaring: Product := X*X mod Modulus
913 -- (Conventional) Modular Squaring: Product := X*X mod Modulus
914 procedure FZ_Mod_Sqr(X : in FZ;
915 Modulus : in FZ;
916 Product : out FZ) is
(80 . 44)(81 . 68)
918 end FZ_Mod_Sqr;
919
920
921 -- Modular Exponent: Result := Base^Exponent mod Modulus
922 -- (Barrettronic) Modular Exponent: Result := Base^Exponent mod Modulus
923 procedure FZ_Mod_Exp(Base : in FZ;
924 Exponent : in FZ;
925 Modulus : in FZ;
926 Result : out FZ) is
927
928 -- Working register for the squaring; initially is copy of Base
929 B : FZ(Base'Range) := Base;
930 -- Double-width scratch buffer for the modular operations
931 D : FZ(1 .. Base'Length * 2);
932
933 -- Copy of Exponent, for cycling through its bits
934 E : FZ(Exponent'Range) := Exponent;
935 -- Working register for the squaring; initially is copy of Base
936 B : FZ(Base'Range) := Base;
937
938 -- Register for the Mux operation
939 T : FZ(Result'Range);
940 T : FZ(Result'Range);
941
942 -- Buffer register for the Result
943 R : FZ(Result'Range);
944 R : FZ(Result'Range);
945
946 -- Space for Barrettoid
947 Bar : Barretoid(ZXMLength => Modulus'Length + 1,
948 BarretoidLength => 2 * B'Length);
949
950 begin
951
952 -- First, pre-compute the Barretoid for the given Modulus:
953 FZ_Make_Barrettoid(Modulus => Modulus, Result => Bar);
954
955 -- Result := 1
956 WBool_To_FZ(1, R);
957
958 -- For each bit of R width:
959 for i in 1 .. FZ_Bitness(R) loop
960
961 -- T := Result * B mod Modulus
962 FZ_Mod_Mul(X => R, Y => B, Modulus => Modulus, Product => T);
963
964 -- Sel is the current low bit of E;
965 -- When Sel=0 -> Result := Result;
966 -- When Sel=1 -> Result := T
967 FZ_Mux(X => R, Y => T, Result => R, Sel => FZ_OddP(E));
968 -- For each Word of the Exponent:
969 for i in Exponent'Range loop
970
971 -- Advance to the next bit of E
972 FZ_ShiftRight(E, E, 1);
973 declare
974
975 -- The current Word of the Exponent
976 Wi : Word := Exponent(i);
977
978 begin
979
980 -- For each bit of Wi:
981 for j in 1 .. Bitness loop
982
983 -- T := Result * B mod Modulus
984 FZ_Multiply_Unbuffered(X => R, Y => B, XY => D);
985 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => T);
986
987 -- Sel is the current bit of Exponent;
988 -- When Sel=0 -> Result := Result;
989 -- When Sel=1 -> Result := T
990 FZ_Mux(X => R, Y => T, Result => R, Sel => Wi and 1);
991
992 -- Advance to the next bit of Wi (i.e. next bit of Exponent)
993 Wi := Shift_Right(Wi, 1);
994
995 -- B := B^2 mod Modulus
996 FZ_Square_Unbuffered(X => B, XX => D);
997 FZ_Barrett_Reduce(X => D, Bar => Bar, XReduced => B);
998
999 end loop;
1000
1001 -- B := B^2 mod Modulus
1002 FZ_Mod_Sqr(X => B, Modulus => Modulus, Product => B);
1003 end;
1004
1005 end loop;
1006