1 /* 2 * (C) Copyright Nick Thompson 2018. 3 * Use, modification and distribution are subject to the 4 * Boost Software License, Version 1.0. (See accompanying file 5 * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 */ 7 8 #include "multiprecision_config.hpp" 9 10 #ifndef DISABLE_MP_TESTS 11 #include <boost/integer/mod_inverse.hpp> 12 #include <boost/cstdint.hpp> 13 #include <boost/optional/optional.hpp> 14 #include <boost/core/lightweight_test.hpp> 15 #include <boost/multiprecision/cpp_int.hpp> 16 #include <boost/integer/common_factor.hpp> 17 18 using boost::multiprecision::int128_t; 19 using boost::multiprecision::int256_t; 20 using boost::integer::mod_inverse; 21 using boost::integer::gcd; 22 23 template<class Z> test_mod_inverse()24void test_mod_inverse() 25 { 26 //Z max_arg = std::numeric_limits<Z>::max(); 27 Z max_arg = 500; 28 for (Z modulus = 2; modulus < max_arg; ++modulus) 29 { 30 if (modulus % 1000 == 0) 31 { 32 std::cout << "Testing all inverses modulo " << modulus << std::endl; 33 } 34 for (Z a = 1; a < modulus; ++a) 35 { 36 Z gcdam = gcd(a, modulus); 37 Z inv_a = mod_inverse(a, modulus); 38 // Should fail if gcd(a, mod) != 1: 39 if (gcdam > 1) 40 { 41 BOOST_TEST(inv_a == 0); 42 } 43 else 44 { 45 BOOST_TEST(inv_a > 0); 46 // Cast to a bigger type so the multiplication won't overflow. 47 int256_t a_inv = inv_a; 48 int256_t big_a = a; 49 int256_t m = modulus; 50 int256_t outta_be_one = (a_inv*big_a) % m; 51 BOOST_TEST_EQ(outta_be_one, 1); 52 } 53 } 54 } 55 } 56 main()57int main() 58 { 59 test_mod_inverse<boost::int16_t>(); 60 test_mod_inverse<boost::int32_t>(); 61 test_mod_inverse<boost::int64_t>(); 62 test_mod_inverse<int128_t>(); 63 64 return boost::report_errors(); 65 } 66 #else main()67int main() 68 { 69 return 0; 70 } 71 #endif 72