1 // Copyright (c) Microsoft Corporation. All rights reserved. 2 // Licensed under the MIT license. 3 4 #include "seal/memorymanager.h" 5 #include "seal/modulus.h" 6 #include "seal/util/uintarithsmallmod.h" 7 #include "seal/util/uintcore.h" 8 #include "gtest/gtest.h" 9 10 using namespace seal::util; 11 using namespace seal; 12 using namespace std; 13 14 namespace sealtest 15 { 16 namespace util 17 { TEST(UIntArithSmallMod,IncrementUIntMod)18 TEST(UIntArithSmallMod, IncrementUIntMod) 19 { 20 Modulus mod(2); 21 ASSERT_EQ(1ULL, increment_uint_mod(0, mod)); 22 ASSERT_EQ(0ULL, increment_uint_mod(1ULL, mod)); 23 24 mod = 0x10000; 25 ASSERT_EQ(1ULL, increment_uint_mod(0, mod)); 26 ASSERT_EQ(2ULL, increment_uint_mod(1ULL, mod)); 27 ASSERT_EQ(0ULL, increment_uint_mod(0xFFFFULL, mod)); 28 29 mod = 2305843009211596801ULL; 30 ASSERT_EQ(1ULL, increment_uint_mod(0, mod)); 31 ASSERT_EQ(0ULL, increment_uint_mod(2305843009211596800ULL, mod)); 32 ASSERT_EQ(1ULL, increment_uint_mod(0, mod)); 33 } 34 TEST(UIntArithSmallMod,DecrementUIntMod)35 TEST(UIntArithSmallMod, DecrementUIntMod) 36 { 37 Modulus mod(2); 38 ASSERT_EQ(0ULL, decrement_uint_mod(1, mod)); 39 ASSERT_EQ(1ULL, decrement_uint_mod(0ULL, mod)); 40 41 mod = 0x10000; 42 ASSERT_EQ(0ULL, decrement_uint_mod(1, mod)); 43 ASSERT_EQ(1ULL, decrement_uint_mod(2ULL, mod)); 44 ASSERT_EQ(0xFFFFULL, decrement_uint_mod(0ULL, mod)); 45 46 mod = 2305843009211596801ULL; 47 ASSERT_EQ(0ULL, decrement_uint_mod(1, mod)); 48 ASSERT_EQ(2305843009211596800ULL, decrement_uint_mod(0ULL, mod)); 49 ASSERT_EQ(0ULL, decrement_uint_mod(1, mod)); 50 } 51 TEST(UIntArithSmallMod,NegateUIntMod)52 TEST(UIntArithSmallMod, NegateUIntMod) 53 { 54 Modulus mod(2); 55 ASSERT_EQ(0ULL, negate_uint_mod(0, mod)); 56 ASSERT_EQ(1ULL, negate_uint_mod(1, mod)); 57 58 mod = 0xFFFFULL; 59 ASSERT_EQ(0ULL, negate_uint_mod(0, mod)); 60 ASSERT_EQ(0xFFFEULL, negate_uint_mod(1, mod)); 61 ASSERT_EQ(0x1ULL, negate_uint_mod(0xFFFEULL, mod)); 62 63 mod = 0x10000ULL; 64 ASSERT_EQ(0ULL, negate_uint_mod(0, mod)); 65 ASSERT_EQ(0xFFFFULL, negate_uint_mod(1, mod)); 66 ASSERT_EQ(0x1ULL, negate_uint_mod(0xFFFFULL, mod)); 67 68 mod = 2305843009211596801ULL; 69 ASSERT_EQ(0ULL, negate_uint_mod(0, mod)); 70 ASSERT_EQ(2305843009211596800ULL, negate_uint_mod(1, mod)); 71 } 72 TEST(UIntArithSmallMod,Div2UIntMod)73 TEST(UIntArithSmallMod, Div2UIntMod) 74 { 75 Modulus mod(3); 76 ASSERT_EQ(0ULL, div2_uint_mod(0ULL, mod)); 77 ASSERT_EQ(2ULL, div2_uint_mod(1ULL, mod)); 78 79 mod = 17; 80 ASSERT_EQ(11ULL, div2_uint_mod(5ULL, mod)); 81 ASSERT_EQ(4ULL, div2_uint_mod(8ULL, mod)); 82 83 mod = 0xFFFFFFFFFFFFFFFULL; 84 ASSERT_EQ(0x800000000000000ULL, div2_uint_mod(1ULL, mod)); 85 ASSERT_EQ(0x800000000000001ULL, div2_uint_mod(3ULL, mod)); 86 } 87 TEST(UIntArithSmallMod,AddUIntMod)88 TEST(UIntArithSmallMod, AddUIntMod) 89 { 90 Modulus mod(2); 91 ASSERT_EQ(0ULL, add_uint_mod(0, 0, mod)); 92 ASSERT_EQ(1ULL, add_uint_mod(0, 1, mod)); 93 ASSERT_EQ(1ULL, add_uint_mod(1, 0, mod)); 94 ASSERT_EQ(0ULL, add_uint_mod(1, 1, mod)); 95 96 mod = 10; 97 ASSERT_EQ(0ULL, add_uint_mod(0, 0, mod)); 98 ASSERT_EQ(1ULL, add_uint_mod(0, 1, mod)); 99 ASSERT_EQ(1ULL, add_uint_mod(1, 0, mod)); 100 ASSERT_EQ(2ULL, add_uint_mod(1, 1, mod)); 101 ASSERT_EQ(4ULL, add_uint_mod(7, 7, mod)); 102 ASSERT_EQ(3ULL, add_uint_mod(6, 7, mod)); 103 104 mod = 2305843009211596801ULL; 105 ASSERT_EQ(0ULL, add_uint_mod(0, 0, mod)); 106 ASSERT_EQ(1ULL, add_uint_mod(0, 1, mod)); 107 ASSERT_EQ(1ULL, add_uint_mod(1, 0, mod)); 108 ASSERT_EQ(2ULL, add_uint_mod(1, 1, mod)); 109 ASSERT_EQ(0ULL, add_uint_mod(1152921504605798400ULL, 1152921504605798401ULL, mod)); 110 ASSERT_EQ(1ULL, add_uint_mod(1152921504605798401ULL, 1152921504605798401ULL, mod)); 111 ASSERT_EQ(2305843009211596799ULL, add_uint_mod(2305843009211596800ULL, 2305843009211596800ULL, mod)); 112 } 113 TEST(UIntArithSmallMod,SubUIntMod)114 TEST(UIntArithSmallMod, SubUIntMod) 115 { 116 Modulus mod(2); 117 ASSERT_EQ(0ULL, sub_uint_mod(0, 0, mod)); 118 ASSERT_EQ(1ULL, sub_uint_mod(0, 1, mod)); 119 ASSERT_EQ(1ULL, sub_uint_mod(1, 0, mod)); 120 ASSERT_EQ(0ULL, sub_uint_mod(1, 1, mod)); 121 122 mod = 10; 123 ASSERT_EQ(0ULL, sub_uint_mod(0, 0, mod)); 124 ASSERT_EQ(9ULL, sub_uint_mod(0, 1, mod)); 125 ASSERT_EQ(1ULL, sub_uint_mod(1, 0, mod)); 126 ASSERT_EQ(0ULL, sub_uint_mod(1, 1, mod)); 127 ASSERT_EQ(0ULL, sub_uint_mod(7, 7, mod)); 128 ASSERT_EQ(9ULL, sub_uint_mod(6, 7, mod)); 129 ASSERT_EQ(1ULL, sub_uint_mod(7, 6, mod)); 130 131 mod = 2305843009211596801ULL; 132 ASSERT_EQ(0ULL, sub_uint_mod(0, 0, mod)); 133 ASSERT_EQ(2305843009211596800ULL, sub_uint_mod(0, 1, mod)); 134 ASSERT_EQ(1ULL, sub_uint_mod(1, 0, mod)); 135 ASSERT_EQ(0ULL, sub_uint_mod(1, 1, mod)); 136 ASSERT_EQ(2305843009211596800ULL, sub_uint_mod(1152921504605798400ULL, 1152921504605798401ULL, mod)); 137 ASSERT_EQ(1ULL, sub_uint_mod(1152921504605798401ULL, 1152921504605798400ULL, mod)); 138 ASSERT_EQ(0ULL, sub_uint_mod(1152921504605798401ULL, 1152921504605798401ULL, mod)); 139 ASSERT_EQ(0ULL, sub_uint_mod(2305843009211596800ULL, 2305843009211596800ULL, mod)); 140 } 141 TEST(UIntArithSmallMod,BarrettReduce128)142 TEST(UIntArithSmallMod, BarrettReduce128) 143 { 144 uint64_t input[2]; 145 146 Modulus mod(2); 147 input[0] = 0; 148 input[1] = 0; 149 ASSERT_EQ(0ULL, barrett_reduce_128(input, mod)); 150 input[0] = 1; 151 input[1] = 0; 152 ASSERT_EQ(1ULL, barrett_reduce_128(input, mod)); 153 input[0] = 0xFFFFFFFFFFFFFFFFULL; 154 input[1] = 0xFFFFFFFFFFFFFFFFULL; 155 ASSERT_EQ(1ULL, barrett_reduce_128(input, mod)); 156 157 mod = 3; 158 input[0] = 0; 159 input[1] = 0; 160 ASSERT_EQ(0ULL, barrett_reduce_128(input, mod)); 161 input[0] = 1; 162 input[1] = 0; 163 ASSERT_EQ(1ULL, barrett_reduce_128(input, mod)); 164 input[0] = 123; 165 input[1] = 456; 166 ASSERT_EQ(0ULL, barrett_reduce_128(input, mod)); 167 input[0] = 0xFFFFFFFFFFFFFFFFULL; 168 input[1] = 0xFFFFFFFFFFFFFFFFULL; 169 ASSERT_EQ(0ULL, barrett_reduce_128(input, mod)); 170 171 mod = 13131313131313ULL; 172 input[0] = 0; 173 input[1] = 0; 174 ASSERT_EQ(0ULL, barrett_reduce_128(input, mod)); 175 input[0] = 1; 176 input[1] = 0; 177 ASSERT_EQ(1ULL, barrett_reduce_128(input, mod)); 178 input[0] = 123; 179 input[1] = 456; 180 ASSERT_EQ(8722750765283ULL, barrett_reduce_128(input, mod)); 181 input[0] = 24242424242424; 182 input[1] = 79797979797979; 183 ASSERT_EQ(1010101010101ULL, barrett_reduce_128(input, mod)); 184 } 185 TEST(UIntArithSmallMod,MultiplyUIntMod)186 TEST(UIntArithSmallMod, MultiplyUIntMod) 187 { 188 Modulus mod(2); 189 ASSERT_EQ(0ULL, multiply_uint_mod(0, 0, mod)); 190 ASSERT_EQ(0ULL, multiply_uint_mod(0, 1, mod)); 191 ASSERT_EQ(0ULL, multiply_uint_mod(1, 0, mod)); 192 ASSERT_EQ(1ULL, multiply_uint_mod(1, 1, mod)); 193 194 mod = 10; 195 ASSERT_EQ(0ULL, multiply_uint_mod(0, 0, mod)); 196 ASSERT_EQ(0ULL, multiply_uint_mod(0, 1, mod)); 197 ASSERT_EQ(0ULL, multiply_uint_mod(1, 0, mod)); 198 ASSERT_EQ(1ULL, multiply_uint_mod(1, 1, mod)); 199 ASSERT_EQ(9ULL, multiply_uint_mod(7, 7, mod)); 200 ASSERT_EQ(2ULL, multiply_uint_mod(6, 7, mod)); 201 ASSERT_EQ(2ULL, multiply_uint_mod(7, 6, mod)); 202 203 mod = 2305843009211596801ULL; 204 ASSERT_EQ(0ULL, multiply_uint_mod(0, 0, mod)); 205 ASSERT_EQ(0ULL, multiply_uint_mod(0, 1, mod)); 206 ASSERT_EQ(0ULL, multiply_uint_mod(1, 0, mod)); 207 ASSERT_EQ(1ULL, multiply_uint_mod(1, 1, mod)); 208 ASSERT_EQ(576460752302899200ULL, multiply_uint_mod(1152921504605798400ULL, 1152921504605798401ULL, mod)); 209 ASSERT_EQ(576460752302899200ULL, multiply_uint_mod(1152921504605798401ULL, 1152921504605798400ULL, mod)); 210 ASSERT_EQ(1729382256908697601ULL, multiply_uint_mod(1152921504605798401ULL, 1152921504605798401ULL, mod)); 211 ASSERT_EQ(1ULL, multiply_uint_mod(2305843009211596800ULL, 2305843009211596800ULL, mod)); 212 } 213 TEST(UIntArithSmallMod,MultiplyAddMod)214 TEST(UIntArithSmallMod, MultiplyAddMod) 215 { 216 Modulus mod(7); 217 ASSERT_EQ(0ULL, multiply_add_uint_mod(0, 0, 0, mod)); 218 ASSERT_EQ(0ULL, multiply_add_uint_mod(1, 0, 0, mod)); 219 ASSERT_EQ(0ULL, multiply_add_uint_mod(0, 1, 0, mod)); 220 ASSERT_EQ(1ULL, multiply_add_uint_mod(0, 0, 1, mod)); 221 ASSERT_EQ(3ULL, multiply_add_uint_mod(3, 4, 5, mod)); 222 223 mod = 0x1FFFFFFFFFFFFFFFULL; 224 ASSERT_EQ(0ULL, multiply_add_uint_mod(0, 0, 0, mod)); 225 ASSERT_EQ(0ULL, multiply_add_uint_mod(1, 0, 0, mod)); 226 ASSERT_EQ(0ULL, multiply_add_uint_mod(0, 1, 0, mod)); 227 ASSERT_EQ(1ULL, multiply_add_uint_mod(0, 0, 1, mod)); 228 ASSERT_EQ(0ULL, multiply_add_uint_mod(mod.value() - 1, mod.value() - 1, mod.value() - 1, mod)); 229 } 230 TEST(UIntArithSmallMod,ModuloUIntMod)231 TEST(UIntArithSmallMod, ModuloUIntMod) 232 { 233 MemoryPool &pool = *global_variables::global_memory_pool; 234 auto value(allocate_uint(4, pool)); 235 236 Modulus mod(2); 237 value[0] = 0; 238 value[1] = 0; 239 value[2] = 0; 240 modulo_uint_inplace(value.get(), 3, mod); 241 ASSERT_EQ(0ULL, value[0]); 242 ASSERT_EQ(0ULL, value[1]); 243 ASSERT_EQ(0ULL, value[2]); 244 245 value[0] = 1; 246 value[1] = 0; 247 value[2] = 0; 248 modulo_uint_inplace(value.get(), 3, mod); 249 ASSERT_EQ(1ULL, value[0]); 250 ASSERT_EQ(0ULL, value[1]); 251 ASSERT_EQ(0ULL, value[2]); 252 253 value[0] = 2; 254 value[1] = 0; 255 value[2] = 0; 256 modulo_uint_inplace(value.get(), 3, mod); 257 ASSERT_EQ(0ULL, value[0]); 258 ASSERT_EQ(0ULL, value[1]); 259 ASSERT_EQ(0ULL, value[2]); 260 261 value[0] = 3; 262 value[1] = 0; 263 value[2] = 0; 264 modulo_uint_inplace(value.get(), 3, mod); 265 ASSERT_EQ(1ULL, value[0]); 266 ASSERT_EQ(0ULL, value[1]); 267 ASSERT_EQ(0ULL, value[2]); 268 269 mod = 0xFFFF; 270 value[0] = 9585656442714717620ul; 271 value[1] = 1817697005049051848; 272 value[2] = 0; 273 modulo_uint_inplace(value.get(), 3, mod); 274 ASSERT_EQ(65143ULL, value[0]); 275 ASSERT_EQ(0ULL, value[1]); 276 ASSERT_EQ(0ULL, value[2]); 277 278 mod = 0x1000; 279 value[0] = 9585656442714717620ul; 280 value[1] = 1817697005049051848; 281 value[2] = 0; 282 modulo_uint_inplace(value.get(), 3, mod); 283 ASSERT_EQ(0xDB4ULL, value[0]); 284 ASSERT_EQ(0ULL, value[1]); 285 ASSERT_EQ(0ULL, value[2]); 286 287 mod = 0xFFFFFFFFC001ULL; 288 value[0] = 9585656442714717620ul; 289 value[1] = 1817697005049051848; 290 value[2] = 14447416709120365380ul; 291 value[3] = 67450014862939159; 292 modulo_uint_inplace(value.get(), 4, mod); 293 ASSERT_EQ(124510066632001ULL, value[0]); 294 ASSERT_EQ(0ULL, value[1]); 295 ASSERT_EQ(0ULL, value[2]); 296 ASSERT_EQ(0ULL, value[3]); 297 } 298 TEST(UIntArithSmallMod,TryInvertUIntMod)299 TEST(UIntArithSmallMod, TryInvertUIntMod) 300 { 301 uint64_t result; 302 Modulus mod(5); 303 ASSERT_FALSE(try_invert_uint_mod(0, mod, result)); 304 ASSERT_TRUE(try_invert_uint_mod(1, mod, result)); 305 ASSERT_EQ(1ULL, result); 306 ASSERT_TRUE(try_invert_uint_mod(2, mod, result)); 307 ASSERT_EQ(3ULL, result); 308 ASSERT_TRUE(try_invert_uint_mod(3, mod, result)); 309 ASSERT_EQ(2ULL, result); 310 ASSERT_TRUE(try_invert_uint_mod(4, mod, result)); 311 ASSERT_EQ(4ULL, result); 312 313 mod = 6; 314 ASSERT_FALSE(try_invert_uint_mod(2, mod, result)); 315 ASSERT_FALSE(try_invert_uint_mod(3, mod, result)); 316 ASSERT_TRUE(try_invert_uint_mod(5, mod, result)); 317 ASSERT_EQ(5ULL, result); 318 319 mod = 1351315121; 320 ASSERT_TRUE(try_invert_uint_mod(331975426, mod, result)); 321 ASSERT_EQ(1052541512ULL, result); 322 } 323 TEST(UIntArithSmallMod,ExponentiateUIntMod)324 TEST(UIntArithSmallMod, ExponentiateUIntMod) 325 { 326 Modulus mod(5); 327 ASSERT_EQ(1ULL, exponentiate_uint_mod(1, 0, mod)); 328 ASSERT_EQ(1ULL, exponentiate_uint_mod(1, 0xFFFFFFFFFFFFFFFFULL, mod)); 329 ASSERT_EQ(3ULL, exponentiate_uint_mod(2, 0xFFFFFFFFFFFFFFFFULL, mod)); 330 331 mod = 0x1000000000000000ULL; 332 ASSERT_EQ(0ULL, exponentiate_uint_mod(2, 60, mod)); 333 ASSERT_EQ(0x800000000000000ULL, exponentiate_uint_mod(2, 59, mod)); 334 335 mod = 131313131313; 336 ASSERT_EQ(39418477653ULL, exponentiate_uint_mod(2424242424, 16, mod)); 337 } 338 TEST(UIntArithSmallMod,DotProductMod)339 TEST(UIntArithSmallMod, DotProductMod) 340 { 341 Modulus mod(5); 342 uint64_t arr1[64], arr2[64]; 343 for (size_t i = 0; i < 64; i++) 344 { 345 arr1[i] = 2; 346 arr2[i] = 3; 347 } 348 349 ASSERT_EQ(0, dot_product_mod(arr1, arr2, 0, mod)); 350 ASSERT_EQ(1, dot_product_mod(arr1, arr2, 1, mod)); 351 ASSERT_EQ(2, dot_product_mod(arr1, arr2, 2, mod)); 352 ASSERT_EQ(15 % mod.value(), dot_product_mod(arr1, arr2, 15, mod)); 353 ASSERT_EQ(16 % mod.value(), dot_product_mod(arr1, arr2, 16, mod)); 354 ASSERT_EQ(17 % mod.value(), dot_product_mod(arr1, arr2, 17, mod)); 355 ASSERT_EQ(32 % mod.value(), dot_product_mod(arr1, arr2, 32, mod)); 356 ASSERT_EQ(64 % mod.value(), dot_product_mod(arr1, arr2, 64, mod)); 357 358 mod = get_prime(1024, SEAL_MOD_BIT_COUNT_MAX); 359 for (size_t i = 0; i < 64; i++) 360 { 361 arr1[i] = mod.value() - 1; 362 arr2[i] = mod.value() - 1; 363 } 364 365 ASSERT_EQ(0, dot_product_mod(arr1, arr2, 0, mod)); 366 ASSERT_EQ(1, dot_product_mod(arr1, arr2, 1, mod)); 367 ASSERT_EQ(2, dot_product_mod(arr1, arr2, 2, mod)); 368 ASSERT_EQ(15, dot_product_mod(arr1, arr2, 15, mod)); 369 ASSERT_EQ(16, dot_product_mod(arr1, arr2, 16, mod)); 370 ASSERT_EQ(17, dot_product_mod(arr1, arr2, 17, mod)); 371 ASSERT_EQ(32, dot_product_mod(arr1, arr2, 32, mod)); 372 ASSERT_EQ(64, dot_product_mod(arr1, arr2, 64, mod)); 373 } 374 TEST(UIntArithSmallMod,MultiplyUIntModOperand)375 TEST(UIntArithSmallMod, MultiplyUIntModOperand) 376 { 377 Modulus mod(3); 378 MultiplyUIntModOperand y; 379 y.set(1, mod); 380 ASSERT_EQ(1ULL, y.operand); 381 ASSERT_EQ(6148914691236517205ULL, y.quotient); 382 y.set(2, mod); 383 y.set_quotient(mod); 384 ASSERT_EQ(2ULL, y.operand); 385 ASSERT_EQ(12297829382473034410ULL, y.quotient); 386 387 mod = 2147483647ULL; 388 y.set(1, mod); 389 ASSERT_EQ(1ULL, y.operand); 390 ASSERT_EQ(8589934596ULL, y.quotient); 391 y.set(2147483646ULL, mod); 392 y.set_quotient(mod); 393 ASSERT_EQ(2147483646ULL, y.operand); 394 ASSERT_EQ(18446744065119617019ULL, y.quotient); 395 396 mod = 2305843009211596801ULL; 397 y.set(1, mod); 398 ASSERT_EQ(1ULL, y.operand); 399 ASSERT_EQ(8ULL, y.quotient); 400 y.set(2305843009211596800ULL, mod); 401 y.set_quotient(mod); 402 ASSERT_EQ(2305843009211596800ULL, y.operand); 403 ASSERT_EQ(18446744073709551607ULL, y.quotient); 404 } 405 TEST(UIntArithSmallMod,MultiplyUIntMod2)406 TEST(UIntArithSmallMod, MultiplyUIntMod2) 407 { 408 Modulus mod(2); 409 MultiplyUIntModOperand y; 410 y.set(0, mod); 411 ASSERT_EQ(0ULL, multiply_uint_mod(0, y, mod)); 412 ASSERT_EQ(0ULL, multiply_uint_mod(1, y, mod)); 413 y.set(1, mod); 414 ASSERT_EQ(0ULL, multiply_uint_mod(0, y, mod)); 415 ASSERT_EQ(1ULL, multiply_uint_mod(1, y, mod)); 416 417 mod = 10; 418 y.set(0, mod); 419 ASSERT_EQ(0ULL, multiply_uint_mod(0, y, mod)); 420 ASSERT_EQ(0ULL, multiply_uint_mod(1, y, mod)); 421 y.set(1, mod); 422 ASSERT_EQ(0ULL, multiply_uint_mod(0, y, mod)); 423 ASSERT_EQ(1ULL, multiply_uint_mod(1, y, mod)); 424 y.set(6, mod); 425 ASSERT_EQ(2ULL, multiply_uint_mod(7, y, mod)); 426 y.set(7, mod); 427 ASSERT_EQ(9ULL, multiply_uint_mod(7, y, mod)); 428 ASSERT_EQ(2ULL, multiply_uint_mod(6, y, mod)); 429 430 mod = 2305843009211596801ULL; 431 y.set(0, mod); 432 ASSERT_EQ(0ULL, multiply_uint_mod(0, y, mod)); 433 ASSERT_EQ(0ULL, multiply_uint_mod(1, y, mod)); 434 y.set(1, mod); 435 ASSERT_EQ(0ULL, multiply_uint_mod(0, y, mod)); 436 ASSERT_EQ(1ULL, multiply_uint_mod(1, y, mod)); 437 y.set(1152921504605798400ULL, mod); 438 ASSERT_EQ(576460752302899200ULL, multiply_uint_mod(1152921504605798401ULL, y, mod)); 439 y.set(1152921504605798401ULL, mod); 440 ASSERT_EQ(576460752302899200ULL, multiply_uint_mod(1152921504605798400ULL, y, mod)); 441 ASSERT_EQ(1729382256908697601ULL, multiply_uint_mod(1152921504605798401ULL, y, mod)); 442 y.set(2305843009211596800ULL, mod); 443 ASSERT_EQ(1ULL, multiply_uint_mod(2305843009211596800ULL, y, mod)); 444 } 445 TEST(UIntArithSmallMod,MultiplyUIntModLazy)446 TEST(UIntArithSmallMod, MultiplyUIntModLazy) 447 { 448 Modulus mod(2); 449 MultiplyUIntModOperand y; 450 y.set(0, mod); 451 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(0, y, mod)); 452 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(1, y, mod)); 453 y.set(1, mod); 454 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(0, y, mod)); 455 ASSERT_EQ(1ULL, multiply_uint_mod_lazy(1, y, mod)); 456 457 mod = 10; 458 y.set(0, mod); 459 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(0, y, mod)); 460 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(1, y, mod)); 461 y.set(1, mod); 462 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(0, y, mod)); 463 ASSERT_EQ(1ULL, multiply_uint_mod_lazy(1, y, mod)); 464 y.set(6, mod); 465 ASSERT_EQ(2ULL, multiply_uint_mod_lazy(7, y, mod)); 466 y.set(7, mod); 467 ASSERT_EQ(9ULL, multiply_uint_mod_lazy(7, y, mod)); 468 ASSERT_EQ(2ULL, multiply_uint_mod_lazy(6, y, mod)); 469 470 mod = 2305843009211596801ULL; 471 y.set(0, mod); 472 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(0, y, mod)); 473 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(1, y, mod)); 474 y.set(1, mod); 475 ASSERT_EQ(0ULL, multiply_uint_mod_lazy(0, y, mod)); 476 ASSERT_EQ(1ULL, multiply_uint_mod_lazy(1, y, mod)); 477 y.set(1152921504605798400ULL, mod); 478 ASSERT_EQ(576460752302899200ULL, multiply_uint_mod_lazy(1152921504605798401ULL, y, mod)); 479 y.set(1152921504605798401ULL, mod); 480 ASSERT_EQ(576460752302899200ULL, multiply_uint_mod_lazy(1152921504605798400ULL, y, mod)); 481 ASSERT_EQ(1729382256908697601ULL, multiply_uint_mod_lazy(1152921504605798401ULL, y, mod)); 482 y.set(2305843009211596800ULL, mod); 483 ASSERT_EQ(2305843009211596802ULL, multiply_uint_mod_lazy(2305843009211596800ULL, y, mod)); 484 } 485 TEST(UIntArithSmallMod,MultiplyAddMod2)486 TEST(UIntArithSmallMod, MultiplyAddMod2) 487 { 488 Modulus mod(7); 489 MultiplyUIntModOperand y; 490 y.set(0, mod); 491 ASSERT_EQ(0ULL, multiply_add_uint_mod(0, y, 0, mod)); 492 ASSERT_EQ(0ULL, multiply_add_uint_mod(1, y, 0, mod)); 493 ASSERT_EQ(1ULL, multiply_add_uint_mod(0, 0, 1, mod)); 494 y.set(1, mod); 495 ASSERT_EQ(0ULL, multiply_add_uint_mod(0, y, 0, mod)); 496 y.set(4, mod); 497 ASSERT_EQ(3ULL, multiply_add_uint_mod(3, y, 5, mod)); 498 499 mod = 0x1FFFFFFFFFFFFFFFULL; 500 y.set(0, mod); 501 ASSERT_EQ(0ULL, multiply_add_uint_mod(0, y, 0, mod)); 502 ASSERT_EQ(0ULL, multiply_add_uint_mod(1, y, 0, mod)); 503 ASSERT_EQ(1ULL, multiply_add_uint_mod(0, y, 1, mod)); 504 y.set(1, mod); 505 ASSERT_EQ(0ULL, multiply_add_uint_mod(0, y, 0, mod)); 506 y.set(mod.value() - 1, mod); 507 ASSERT_EQ(0ULL, multiply_add_uint_mod(mod.value() - 1, y, mod.value() - 1, mod)); 508 } 509 } // namespace util 510 } // namespace sealtest 511