diff options
author | Wei-Ning Huang <w@byzantine-lab.io> | 2019-06-12 17:31:08 +0800 |
---|---|---|
committer | Wei-Ning Huang <w@byzantine-lab.io> | 2019-09-17 16:57:29 +0800 |
commit | ac088de6322fc16ebe75c2e5554be73754bf1fe2 (patch) | |
tree | 086b7827d46a4d07b834cd94be73beaabb77b734 /vendor/github.com/byzantine-lab/mcl/test/mont_fp_test.cpp | |
parent | 67d565f3f0e398e99bef96827f729e3e4b0edf31 (diff) | |
download | go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.gz go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.bz2 go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.lz go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.xz go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.tar.zst go-tangerine-ac088de6322fc16ebe75c2e5554be73754bf1fe2.zip |
Rebrand as tangerine-network/go-tangerine
Diffstat (limited to 'vendor/github.com/byzantine-lab/mcl/test/mont_fp_test.cpp')
-rw-r--r-- | vendor/github.com/byzantine-lab/mcl/test/mont_fp_test.cpp | 332 |
1 files changed, 332 insertions, 0 deletions
diff --git a/vendor/github.com/byzantine-lab/mcl/test/mont_fp_test.cpp b/vendor/github.com/byzantine-lab/mcl/test/mont_fp_test.cpp new file mode 100644 index 000000000..e41e77a53 --- /dev/null +++ b/vendor/github.com/byzantine-lab/mcl/test/mont_fp_test.cpp @@ -0,0 +1,332 @@ +#define PUT(x) std::cout << #x "=" << (x) << std::endl +#include <cybozu/test.hpp> +#include <cybozu/benchmark.hpp> +#include <cybozu/xorshift.hpp> +#include <time.h> + +#if 0 +#include <mcl/bls12_381.hpp> +using namespace mcl::bls12; +typedef Fr Zn; +#else +#include <mcl/fp.hpp> +struct ZnTag; +typedef mcl::FpT<ZnTag> Zn; +typedef mcl::FpT<> Fp; +#endif + +struct Montgomery { + typedef mcl::fp::Unit Unit; + mpz_class p_; + mpz_class R_; // (1 << (pn_ * 64)) % p + mpz_class RR_; // (R * R) % p + Unit rp_; // rp * p = -1 mod M = 1 << 64 + size_t pn_; + Montgomery() {} + explicit Montgomery(const mpz_class& p) + { + p_ = p; + rp_ = mcl::fp::getMontgomeryCoeff(mcl::gmp::getUnit(p, 0)); + pn_ = mcl::gmp::getUnitSize(p); + R_ = 1; + R_ = (R_ << (pn_ * 64)) % p_; + RR_ = (R_ * R_) % p_; + } + + void toMont(mpz_class& x) const { mul(x, x, RR_); } + void fromMont(mpz_class& x) const { mul(x, x, 1); } + + void mul(mpz_class& z, const mpz_class& x, const mpz_class& y) const + { +#if 0 + const size_t ySize = mcl::gmp::getUnitSize(y); + mpz_class c = x * mcl::gmp::getUnit(y, 0); + Unit q = mcl::gmp::getUnit(c, 0) * rp_; + c += p_ * q; + c >>= sizeof(Unit) * 8; + for (size_t i = 1; i < pn_; i++) { + if (i < ySize) { + c += x * mcl::gmp::getUnit(y, i); + } + Unit q = mcl::gmp::getUnit(c, 0) * rp_; + c += p_ * q; + c >>= sizeof(Unit) * 8; + } + if (c >= p_) { + c -= p_; + } + z = c; +#else + z = x * y; + for (size_t i = 0; i < pn_; i++) { + Unit q = mcl::gmp::getUnit(z, 0) * rp_; +#ifdef MCL_USE_VINT + z += p_ * q; +#else + mpz_class t; + mcl::gmp::set(t, q); + z += p_ * t; +#endif + z >>= sizeof(Unit) * 8; + } + if (z >= p_) { + z -= p_; + } +#endif + } + void mod(mpz_class& z, const mpz_class& xy) const + { + z = xy; + for (size_t i = 0; i < pn_; i++) { +//printf("i=%zd\n", i); +//std::cout << "z=" << std::hex << z << std::endl; + Unit q = mcl::gmp::getUnit(z, 0) * rp_; +//std::cout << "q=" << q << std::endl; + mpz_class t; + mcl::gmp::set(t, q); + z += p_ * t; + z >>= sizeof(Unit) * 8; +//std::cout << "z=" << std::hex << z << std::endl; + } + if (z >= p_) { + z -= p_; + } +//std::cout << "z=" << std::hex << z << std::endl; + } +}; + +template<class T> +mpz_class getMpz(const T& x) +{ + std::string str = x.getStr(); + mpz_class t; + mcl::gmp::setStr(t, str); + return t; +} + +template<class T> +std::string getStr(const T& x) +{ + std::ostringstream os; + os << x; + return os.str(); +} + +template<class T, class U> +T castTo(const U& x) +{ + T t; + t.setStr(getStr(x)); + return t; +} + +template<class T> +void putRaw(const T& x) +{ + const uint64_t *p = x.getInnerValue(); + for (size_t i = 0, n = T::BlockSize; i < n; i++) { + printf("%016llx", p[n - 1 - i]); + } + printf("\n"); +} + +template<size_t N> +void put(const uint64_t (&x)[N]) +{ + for (size_t i = 0; i < N; i++) { + printf("%016llx", x[N - 1 - i]); + } + printf("\n"); +} + +struct Test { + typedef mcl::FpT<> Fp; + void run(const char *p) + { + Fp::init(p); + Fp x("-123456789"); + Fp y("-0x7ffffffff"); + CYBOZU_BENCH("add", operator+, x, x); + CYBOZU_BENCH("sub", operator-, x, y); + CYBOZU_BENCH("mul", operator*, x, x); + CYBOZU_BENCH("sqr", Fp::sqr, x, x); + CYBOZU_BENCH("div", y += x; operator/, x, y); + } +}; + +void customTest(const char *pStr, const char *xStr, const char *yStr) +{ +#if 0 + { + pStr = "0xfffffffffffffffffffffffffffffffffffffffeffffee37", + Fp::init(pStr); + static uint64_t x[3] = { 1, 0, 0 }; + uint64_t z[3]; +std::cout<<std::hex; + Fp::inv(*(Fp*)z, *(const Fp*)x); +put(z); + exit(1); + } +#endif +#if 0 + std::cout << std::hex; + uint64_t x[9] = { 0xff7fffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0x1ff }; + uint64_t y[9] = { 0xff7fffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0x1ff }; + uint64_t z1[9], z2[9]; + Fp::init(pStr); + Fp::fg_.mul_(z2, x, y); + put(z2); + { + puts("C"); + mpz_class p(pStr); + Montgomery mont(p); + mpz_class xx, yy; + mcl::gmp::setArray(xx, x, CYBOZU_NUM_OF_ARRAY(x)); + mcl::gmp::setArray(yy, y, CYBOZU_NUM_OF_ARRAY(y)); + mpz_class z; + mont.mul(z, xx, yy); + std::cout << std::hex << z << std::endl; + } + exit(1); +#else + std::string rOrg, rC, rAsm; + Zn::init(pStr); + Zn s(xStr), t(yStr); + s *= t; + rOrg = getStr(s); + { + puts("C"); + mpz_class p(pStr); + Montgomery mont(p); + mpz_class x(xStr), y(yStr); + mont.toMont(x); + mont.toMont(y); + mpz_class z; + mont.mul(z, x, y); + mont.fromMont(z); + rC = getStr(z); + } + + puts("asm"); + Fp::init(pStr); + Fp x(xStr), y(yStr); + x *= y; + rAsm = getStr(x); + CYBOZU_TEST_EQUAL(rOrg, rC); + CYBOZU_TEST_EQUAL(rOrg, rAsm); +#endif +} + +#if MCL_MAX_BIT_SIZE >= 521 +CYBOZU_TEST_AUTO(customTest) +{ + const struct { + const char *p; + const char *x; + const char *y; + } tbl[] = { + { + "0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", +// "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff", +// "0xfffffffffffffffffffffffffffffffffffffffeffffee37", + "0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe", + "0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + }, + }; + for (size_t i = 0; i < CYBOZU_NUM_OF_ARRAY(tbl); i++) { + customTest(tbl[i].p, tbl[i].x, tbl[i].y); + } +} +#endif + +CYBOZU_TEST_AUTO(test) +{ + Test test; + const char *tbl[] = { +#if 1 + // N = 2 + "0x0000000000000001000000000000000d", + "0x7fffffffffffffffffffffffffffffff", + "0x8000000000000000000000000000001d", + "0xffffffffffffffffffffffffffffff61", + + // N = 3 + "0x000000000000000100000000000000000000000000000033", // min prime + "0x00000000fffffffffffffffffffffffffffffffeffffac73", + "0x0000000100000000000000000001b8fa16dfab9aca16b6b3", + "0x000000010000000000000000000000000000000000000007", + "0x30000000000000000000000000000000000000000000002b", + "0x70000000000000000000000000000000000000000000001f", + "0x800000000000000000000000000000000000000000000005", + "0xfffffffffffffffffffffffffffffffffffffffeffffee37", + "0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d", + "0xffffffffffffffffffffffffffffffffffffffffffffff13", // max prime + + // N = 4 + "0x0000000000000001000000000000000000000000000000000000000000000085", // min prime + "0x2523648240000001ba344d80000000086121000000000013a700000000000013", + "0x7523648240000001ba344d80000000086121000000000013a700000000000017", + "0x800000000000000000000000000000000000000000000000000000000000005f", + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff43", // max prime +#endif + +#if MCL_MAX_BIT_SIZE >= 384 + // N = 6 + "0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab", + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff", +#endif + +#if MCL_MAX_BIT_SIZE >= 521 + // N = 9 + "0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", +#endif + }; + for (size_t i = 0; i < CYBOZU_NUM_OF_ARRAY(tbl); i++) { + printf("prime=%s\n", tbl[i]); +#if 0 + mpz_class p(tbl[i]); + initPairing(mcl::BLS12_381); +#if 1 + cybozu::XorShift rg; + for (int i = 0; i < 1000; i++) { + Fp x, y, z; + FpDbl xy; + x.setByCSPRNG(rg); + y.setByCSPRNG(rg); + FpDbl::mulPre(xy, x, y); + FpDbl::mod(z, xy); + if (z != x * y) { + puts("ERR"); + std::cout << std::hex; + PUT(x); + PUT(y); + PUT(z); + PUT(x * y); + exit(1); + } + } +#else + Montgomery mont(p); + mpz_class x("19517141aafb2ffc39517141aafb2ffc39517141aafb2ffc39517141aafb2ffc39517141aafb2ffc39517141aafb2ffc", 16); + mpz_class y("139517141aafb2ffc39517141aafb2ffc39517141aafb2ffc39517141aafb2ffc39517141aafb2ffc39517141aafb2ff", 16); + std::cout << std::hex; + PUT(x); + PUT(y); + mpz_class z; + mont.mul(z, x, y); + PUT(z); + Fp x1, y1, z1; + puts("aaa"); + memcpy(&x1, mcl::gmp::getUnit(x), sizeof(x1)); + memcpy(&y1, mcl::gmp::getUnit(y), sizeof(y1)); + z1.clear(); + x1.dump(); + y1.dump(); + Fp::mul(z1, x1, y1); + z1.dump(); +#endif + exit(1); +#endif + test.run(tbl[i]); + } +} |