PALISADE Lattice Crypto Library  1.11.9
A lattice crypto library for software engineers by software engineers.
ubintdyn.h
1 // @file ubintdyn.h This file contains the main class for unsigned big
2 // integers: ubint. Big integers are represented as arrays of machine native
3 // unsigned integers. The native integer type is supplied as a template
4 // parameter. Currently implementation based on uint32_t and uint64_t is
5 // supported. a native double the base integer size is also needed.
6 // @author TPOC: contact@palisade-crypto.org
7 //
8 // @copyright Copyright (c) 2019, New Jersey Institute of Technology (NJIT)
9 // All rights reserved.
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are met:
12 // 1. Redistributions of source code must retain the above copyright notice,
13 // this list of conditions and the following disclaimer.
14 // 2. Redistributions in binary form must reproduce the above copyright notice,
15 // this list of conditions and the following disclaimer in the documentation
16 // and/or other materials provided with the distribution. THIS SOFTWARE IS
17 // PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
18 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
19 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
20 // EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
21 // INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
26 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 #ifndef LBCRYPTO_MATH_BIGINTDYN_UBINTDYN_H
29 #define LBCRYPTO_MATH_BIGINTDYN_UBINTDYN_H
30 
31 #define NO_BARRETT // currently barrett is slower than mod
32 
33 #include <fstream>
34 #include <functional>
35 #include <iostream>
36 #include <limits>
37 #include <memory>
38 #include <string>
39 #include <type_traits>
40 #include <typeinfo>
41 #include <vector>
42 #include "math/nbtheory.h"
43 #include "utils/inttypes.h"
44 #include "utils/memory.h"
45 #include "utils/serializable.h"
46 
47 #ifdef UBINT_64
48 
49 #undef int128_t
50 #define int128_t our_int128_t
51 #undef uint128_t
52 #define uint128_t our_uint128_t
53 
54 typedef __int128 int128_t;
55 typedef unsigned __int128 uint128_t;
56 
57 #define UINT128_MAX ((uint128_t)-1)
58 
59 #endif // UBINT_64
60 
65 namespace bigintdyn {
66 
80 template <usint N>
81 struct Log2 {
82  static const usint value = 1 + Log2<N / 2>::value;
83 };
84 
90 template <>
91 struct Log2<2> {
92  static const usint value = 1;
93 };
94 
101 template <typename Dtype>
103  static const bool value = false;
104 };
105 
111 template <>
112 struct DataTypeChecker<uint8_t> {
113  static const bool value = true;
114 };
115 
121 template <>
122 struct DataTypeChecker<uint16_t> {
123  static const bool value = true;
124 };
125 
131 template <>
132 struct DataTypeChecker<uint32_t> {
133  static const bool value = true;
134 };
135 
141 template <>
142 struct DataTypeChecker<uint64_t> {
143  static const bool value = true;
144 };
145 
146 #ifdef UBINT_64
147 
152 template <>
153 struct DataTypeChecker<uint128_t> {
154  static const bool value = true;
155 };
156 #endif
157 
164 template <typename utype>
166  typedef void T;
167 };
168 
173 template <>
174 struct DoubleDataType<uint8_t> {
175  typedef uint16_t T;
176 };
177 
182 template <>
183 struct DoubleDataType<uint16_t> {
184  typedef uint32_t T;
185 };
186 
191 template <>
192 struct DoubleDataType<uint32_t> {
193  typedef uint64_t T;
194 };
195 
196 #ifdef UBINT_64
197 
201 template <>
202 struct DoubleDataType<uint64_t> {
203  typedef uint128_t T;
204 };
205 #endif
206 
213 template <typename utype>
215  typedef void T;
216 };
217 
222 template <>
223 struct SignedDataType<uint8_t> {
224  typedef int8_t T;
225 };
226 
231 template <>
232 struct SignedDataType<uint16_t> {
233  typedef int16_t T;
234 };
235 
240 template <>
241 struct SignedDataType<uint32_t> {
242  typedef int32_t T;
243 };
244 
249 template <>
250 struct SignedDataType<uint64_t> {
251  typedef int64_t T;
252 };
253 
260 template <typename utype>
262  typedef void T;
263 };
264 
269 template <>
270 struct SignedDoubleDataType<uint8_t> {
271  typedef int16_t T;
272 };
273 
278 template <>
279 struct SignedDoubleDataType<uint16_t> {
280  typedef int32_t T;
281 };
282 
287 template <>
288 struct SignedDoubleDataType<uint32_t> {
289  typedef int64_t T;
290 };
291 
292 #ifdef UBINT_64
293 
297 template <>
298 struct SignedDoubleDataType<uint64_t> {
299  typedef int128_t T;
300 };
301 #endif
302 
303 const double LOG2_10 =
304  3.32192809;
305 
307 // Definition starts here
309 template <typename limb_t>
310 class ubint : public lbcrypto::BigIntegerInterface<ubint<limb_t>> {
311  public:
312  // CONSTRUCTORS
313 
317  ubint();
318 
324  ubint(const ubint &val);
325 
331  ubint(ubint &&val);
332 
338  explicit ubint(const std::string &strval);
339 
345  ubint(const uint64_t val);
346 #if defined(HAVE_INT128)
347  ubint(unsigned __int128 val);
348 #endif
349 
355  ubint(int val) : ubint(uint64_t(val)) {}
356  ubint(uint32_t val) : ubint(uint64_t(val)) {}
357  ubint(long val) : ubint(uint64_t(val)) {}
358  ubint(long long val) : ubint(uint64_t(val)) {}
359 
365  template <typename T>
366  ubint(const bigintnat::NativeIntegerT<T> &val) : ubint(val.ConvertToInt()) {}
367 
373  ubint(double val)
374  __attribute__((deprecated("Cannot construct from a double")));
375 
379  ~ubint();
380 
381  // ASSIGNMENT OPERATORS
382 
389  const ubint &operator=(const ubint &val);
390 
391  // TODO move assignment operator?
392 
399  const ubint &operator=(const std::string strval) {
400  *this = ubint(strval);
401  return *this;
402  }
403 
410  const ubint &operator=(const uint64_t val) {
411  *this = ubint(val);
412  return *this;
413  }
414 
422  *this = ubint(val);
423  return *this;
424  }
425 
426  // ACCESSORS
427 
433  void SetValue(const std::string &strval);
434 
440  void SetValue(const ubint &val);
441 
445  inline void SetIdentity() { *this = 1; }
446 
447  // ARITHMETIC OPERATIONS
448 
455  ubint Add(const ubint &b) const;
456 
463  const ubint &AddEq(const ubint &b);
464 
471  ubint Sub(const ubint &b) const;
472 
479  const ubint &SubEq(const ubint &b);
480 
481  // this is a negation operator which really doesn't make sense for an unsinged
482  ubint operator-() const { return ubint(0).Sub(*this); }
483 
490  ubint Mul(const ubint &b) const;
491 
498  const ubint &MulEq(const ubint &b);
499 
506  ubint DividedBy(const ubint &b) const;
507 
514  const ubint &DividedByEq(const ubint &b);
515 
522  ubint Exp(usint p) const;
523 
530  const ubint &ExpEq(usint p);
531 
540  ubint MultiplyAndRound(const ubint &p, const ubint &q) const;
541 
550  const ubint &MultiplyAndRoundEq(const ubint &p, const ubint &q);
551 
559  ubint DivideAndRound(const ubint &q) const;
560 
568  const ubint &DivideAndRoundEq(const ubint &q);
569 
570  // MODULAR ARITHMETIC OPERATIONS
571 
578  ubint Mod(const ubint &modulus) const;
579 
586  const ubint &ModEq(const ubint &modulus);
587 
593  ubint ComputeMu() const;
594 
604  ubint Mod(const ubint &modulus, const ubint &mu) const;
605 
615  const ubint &ModEq(const ubint &modulus, const ubint &mu);
616 
624  ubint ModAdd(const ubint &b, const ubint &modulus) const;
625 
633  const ubint &ModAddEq(const ubint &b, const ubint &modulus);
634 
642  ubint ModAddFast(const ubint &b, const ubint &modulus) const;
643 
651  const ubint &ModAddFastEq(const ubint &b, const ubint &modulus);
652 
661  ubint ModAdd(const ubint &b, const ubint &modulus, const ubint &mu) const;
662 
671  const ubint &ModAddEq(const ubint &b, const ubint &modulus, const ubint &mu);
672 
680  ubint ModSub(const ubint &b, const ubint &modulus) const;
681 
689  const ubint &ModSubEq(const ubint &b, const ubint &modulus);
690 
698  ubint ModSubFast(const ubint &b, const ubint &modulus) const;
699 
707  const ubint &ModSubFastEq(const ubint &b, const ubint &modulus);
708 
717  ubint ModSub(const ubint &b, const ubint &modulus, const ubint &mu) const;
718 
727  const ubint &ModSubEq(const ubint &b, const ubint &modulus, const ubint &mu);
728 
736  ubint ModMul(const ubint &b, const ubint &modulus) const;
737 
745  const ubint &ModMulEq(const ubint &b, const ubint &modulus);
746 
755  ubint ModMul(const ubint &b, const ubint &modulus, const ubint &mu) const;
756 
765  const ubint &ModMulEq(const ubint &b, const ubint &modulus, const ubint &mu);
766 
774  ubint ModMulFast(const ubint &b, const ubint &modulus) const;
775 
784  const ubint &ModMulFastEq(const ubint &b, const ubint &modulus);
785 
794  ubint ModMulFast(const ubint &b, const ubint &modulus, const ubint &mu) const;
795 
805  const ubint &ModMulFastEq(const ubint &b, const ubint &modulus,
806  const ubint &mu);
807 
808  ubint ModMulFastConst(const ubint &b, const ubint &modulus,
809  const ubint &bInv) const {
810  PALISADE_THROW(lbcrypto::not_implemented_error,
811  "ModMulFastConst is not implemented for backend 4");
812  }
813 
814  const ubint &ModMulFastConstEq(const ubint &b, const ubint &modulus,
815  const ubint &bInv) {
816  PALISADE_THROW(lbcrypto::not_implemented_error,
817  "ModMulFastConstEq is not implemented for backend 4");
818  }
819 
827  ubint ModExp(const ubint &b, const ubint &modulus) const;
828 
837  const ubint &ModExpEq(const ubint &b, const ubint &modulus);
838 
845  ubint ModInverse(const ubint &modulus) const;
846 
853  const ubint &ModInverseEq(const ubint &modulus);
854 
855  // SHIFT OPERATIONS
856 
863  ubint LShift(usshort shift) const;
864 
871  const ubint &LShiftEq(usshort shift);
872 
879  ubint RShift(usshort shift) const;
880 
887  const ubint &RShiftEq(usshort shift);
888 
889  // COMPARE
890 
898  int Compare(const ubint &a) const;
899 
900  // CONVERTERS
901 
906  template <typename T = bigintnat::BasicInteger>
907  T ConvertToInt() const {
908  T result = 0;
909  if (m_value.size() == 0) {
910  PALISADE_THROW(lbcrypto::not_available_error,
911  "ConvertToInt() on uninitialized bint");
912  }
913  if (sizeof(limb_t) >= sizeof(T)) {
914  result = m_value[0];
915  result = (T)m_value[0];
916  } else {
917  // Case where limb_t is less bits than uint64_t
918  uint32_t msbTest = sizeof(T) * 8;
919  if (msbTest > m_MSB) {
920  msbTest = m_MSB;
921  }
922  usint ceilInt = ceilIntByUInt(msbTest);
923  // copy the values by shift and add
924  for (usint i = 0; i < ceilInt; i++) {
925  T tmp = this->m_value[i];
926  tmp <<= (m_limbBitLength * i);
927  result += tmp;
928  }
929  }
930  return result;
931  }
932 
941  float ConvertToFloat() const;
942 
952  double ConvertToDouble() const;
953 
963  long double ConvertToLongDouble() const;
964 
971  static ubint UsintToUbint(usint m);
972 
980  static ubint FromBinaryString(const std::string &bitString);
981 
982  // OTHER FUNCTIONS
983 
989  usint GetMSB() const;
990 
996  usint GetNumberOfLimbs() const;
997 
1004  bool isPowerOfTwo(const ubint &m_numToCheck);
1005 
1013  usint GetLengthForBase(usint base) const { return GetMSB(); }
1014 
1029  usint GetDigitAtIndexForBase(usint index, usint base) const;
1030 
1034  const std::string GetState() const;
1035 
1041  inline ubint MulIntegerByLimb(limb_t b) const; // todo rename to ubint
1042 
1049  uschar GetBitAtIndex(usint index) const;
1050 
1055  static ubint Allocator() { return 0; }
1056 
1057  // STRINGS & STREAMS
1058 
1065  const std::string ToString() const;
1066 
1067  public:
1068 #ifdef UBINT_32
1069  static const std::string IntegerTypeName() { return "UBDYNINT_32"; }
1070 #endif
1071 #ifdef UBINT_64
1072  static const std::string IntegerTypeName() { return "UBDYNINT_64"; }
1073 #endif
1074 
1080  std::string GetInternalRepresentation() const {
1081  std::string ret("");
1082  for (size_t i = 0; i < m_value.size(); i++) {
1083  ret += std::to_string(m_value[i]);
1084  if (i < (m_value.size() - 1)) {
1085  ret += " ";
1086  }
1087  }
1088  return ret;
1089  }
1090 
1100  friend std::ostream &operator<<(std::ostream &os, const ubint &ptr_obj) {
1101  // todo: get rid of m_numDigitInPrintval and make dynamic
1102 
1103  // initiate to object to be printed
1104  // todo smartpointer
1105  uschar *print_VALUE = new uschar[ptr_obj.m_numDigitInPrintval]();
1106  // starts the conversion from base r to decimal value
1107  for (usint i = ptr_obj.m_MSB; i > 0; i--) {
1108  ubint::double_bitVal(print_VALUE);
1109  // adds the bit value to the print_VALUE (print_VALUE *= 2)
1110  ubint::add_bitVal(print_VALUE, ptr_obj.GetBitAtIndex(i));
1111  }
1112 
1113  // find the first occurence of non-zero value in print_VALUE
1114  bool print = false;
1115  for (usint counter = 0; counter < ptr_obj.m_numDigitInPrintval; counter++) {
1116  if (print_VALUE[counter] != 0) {
1117  print = true;
1118  }
1119  if (print) {
1120  os << static_cast<int>(print_VALUE[counter]);
1121  }
1122  }
1123  // Print 0 value
1124  if (!print) {
1125  os << 0;
1126  }
1127  delete[] print_VALUE;
1128  return os;
1129  }
1130 
1134  void PrintIntegerConstants();
1135 
1136  // SERIALIZATION
1137 
1138  template <class Archive>
1139  void save(Archive &ar, std::uint32_t const version) const {
1140  ar(::cereal::make_nvp("v", m_value));
1141  ar(::cereal::make_nvp("m", m_MSB));
1142  ar(::cereal::make_nvp("s", m_state));
1143  }
1144 
1145  template <class Archive>
1146  void load(Archive &ar, std::uint32_t const version) {
1147  if (version > SerializedVersion()) {
1148  PALISADE_THROW(lbcrypto::deserialize_error,
1149  "serialized object version " + std::to_string(version) +
1150  " is from a later version of the library");
1151  }
1152  ar(::cereal::make_nvp("v", m_value));
1153  ar(::cereal::make_nvp("m", m_MSB));
1154  ar(::cereal::make_nvp("s", m_state));
1155  }
1156 
1157  std::string SerializedObjectName() const { return "DYNInteger"; }
1158 
1159  static uint32_t SerializedVersion() { return 1; }
1160 
1161  protected:
1168  void AssignVal(const std::string &v);
1169 
1173  void SetMSB();
1174 
1179  void SetMSB(usint guessIdxChar);
1180 
1181  private:
1189  void NormalizeLimbs(void);
1190 
1197  void SetIntAtIndex(usint idx, limb_t value);
1198 
1204  int divqr_vect(ubint &q, ubint &r, const ubint &u, const ubint &v) const;
1205 
1206  int divr_vect(ubint &r, const ubint &u, const ubint &v) const;
1207 
1208  int divq_vect(ubint &q, const ubint &u, const ubint &v) const;
1209 
1210  private:
1211  // vector storing the native integers. stored little endian
1212  vector<limb_t> m_value;
1213 
1214  private:
1215  // variable that stores the MOST SIGNIFICANT BIT position in the
1216  uint32_t m_MSB;
1217 
1218  // variable to store the bitlength of the limb data type.
1219  static const usint m_limbBitLength;
1220 
1221  // variable to store the maximum value of the limb data type.
1222  static const limb_t m_MaxLimb;
1223 
1224  // variable to store the log(base 2) of the number of bits in the limb data
1225  // type.
1226  static const usint m_log2LimbBitLength;
1227 
1228  // variable to store the size of the data array.
1229  static const usint m_nSize;
1230 
1231  // The maximum number of digits in biginteger. It is used by the cout(ostream)
1232  // function for printing the bignumber. Todo remove this limitation
1233  static const usint m_numDigitInPrintval =
1234  1500; // todo get rid of m_numDigitInPrintval
1235 
1243  static usint ceilIntByUInt(
1244  const limb_t Number); // todo rename to MSB2NLimbs()
1245 
1246  // currently unused array
1247  static const ubint *m_modChain;
1248 
1249  private:
1256  inline static usint GetMSBlimb_t(limb_t x) { return lbcrypto::GetMSB64(x); }
1257 
1258  // Dlimb_t is the data type that has twice as many bits in the limb data type.
1259  typedef typename DoubleDataType<limb_t>::T Dlimb_t;
1260 
1261  // Slimb_t is the data type that as many bits in the limb data type but is
1262  // signed.
1263  typedef typename SignedDataType<limb_t>::T Slimb_t;
1264 
1265  // Slimb_t is the data type that as many bits in the limb data type but is
1266  // signed.
1267  typedef typename SignedDoubleDataType<limb_t>::T Sdlimb_t;
1268 
1269  // enum definition to represent the state of the ubint.
1270  enum State { INITIALIZED, GARBAGE };
1271 
1277  inline static usint GetMSBDlimb_t(Dlimb_t x) { return lbcrypto::GetMSB64(x); }
1278 
1279  // enum to store the state of the
1280  State m_state;
1281 
1287  static limb_t UintInBinaryToDecimal(uschar *a);
1288 
1293  static void double_bitVal(uschar *a);
1294 
1300  static void add_bitVal(uschar *a, uschar b);
1301 };
1302 
1303 #if 0
1304 // stream helper function for vector of objects
1305 template <typename limb_t>
1306 inline std::ostream &operator<<(std::ostream &os,
1307  const std::vector<limb_t> &v) {
1308  os << "[";
1309  for (const auto &itr : v) {
1310  os << " " << itr;
1311  }
1312  os << " ]";
1313  return os;
1314 }
1315 #endif
1316 } // namespace bigintdyn
1317 
1318 #endif // LBCRYPTO_MATH_BIGINTDYN_UBINTDYN_H
Struct to determine a datatype that is the signed version of utype. sets T as of type void for defaul...
Definition: ubintdyn.h:214
Struct to find log value of N. Needed in the preprocessing step of ubint to determine bitwidth...
Definition: ubintdyn.h:81
Struct to determine a datatype that is twice as big(bitwise) as utype. sets T as of type void for def...
Definition: ubintdyn.h:165
uschar GetBitAtIndex(usint index) const
Definition: ubintdyn.cpp:2350
Definition: ubintdyn.h:310
static ubint Allocator()
Definition: ubintdyn.h:1055
usint GetLengthForBase(usint base) const
Definition: ubintdyn.h:1013
Definition: exception.h:119
Definition: exception.h:147
ubint Sub(const ubint &b) const
Definition: ubintdyn.cpp:302
const ubint & operator=(const bigintnat::NativeInteger &val)
Definition: ubintdyn.h:421
Struct for validating if Dtype is amongst {uint8_t, uint16_t, uint32_t, uint64_t, uint128_t}...
Definition: ubintdyn.h:102
std::string GetInternalRepresentation() const
Definition: ubintdyn.h:1080
const double LOG2_10
A pre-computed constant of Log base 2 of 10.
Definition: ubintdyn.h:303
Definition: backend.h:187
friend std::ostream & operator<<(std::ostream &os, const ubint &ptr_obj)
Definition: ubintdyn.h:1100
ubint(int val)
Definition: ubintdyn.h:355
Struct to determine a signed datatype that is twice as big(bitwise) as utype. sets T as of type void ...
Definition: ubintdyn.h:261
const ubint & operator=(const std::string strval)
Definition: ubintdyn.h:399
usint GetMSB64(uint64_t x)
Definition: nbtheory.h:219
ubint(const bigintnat::NativeIntegerT< T > &val)
Definition: ubintdyn.h:366
Definition: interface.h:33
T ConvertToInt() const
Definition: ubintdyn.h:907
Main class for big integers represented as an array of native (primitive) unsigned integers...
Definition: backend.h:60
Definition: exception.h:126
const ubint & operator=(const uint64_t val)
Definition: ubintdyn.h:410
void SetIdentity()
Definition: ubintdyn.h:445