diff options
| author | MITSUNARI Shigeo <herumi@nifty.com> | 2017-03-15 09:41:25 +0800 |
|---|---|---|
| committer | MITSUNARI Shigeo <herumi@nifty.com> | 2017-03-15 09:41:25 +0800 |
| commit | 2c1111966216aeefd73f6b5d2cf70a33dd335fb5 (patch) | |
| tree | e668b34fedebdbdd7fc171761274c18ca96dbb8b /include | |
| parent | 50a0ed560f3e10db55c8e52ebd335586f76473a6 (diff) | |
| download | tangerine-mcl-2c1111966216aeefd73f6b5d2cf70a33dd335fb5.tar.gz tangerine-mcl-2c1111966216aeefd73f6b5d2cf70a33dd335fb5.tar.zst tangerine-mcl-2c1111966216aeefd73f6b5d2cf70a33dd335fb5.zip | |
add getQuadraticNonResidue
Diffstat (limited to 'include')
| -rw-r--r-- | include/mcl/gmp_util.hpp | 14 |
1 files changed, 9 insertions, 5 deletions
diff --git a/include/mcl/gmp_util.hpp b/include/mcl/gmp_util.hpp index 61aef5f..a056db3 100644 --- a/include/mcl/gmp_util.hpp +++ b/include/mcl/gmp_util.hpp @@ -289,6 +289,14 @@ struct gmp { } } while (!(isPrime(z))); } + static inline mpz_class getQuadraticNonResidue(const mpz_class& p) + { + mpz_class g = 2; + while (gmp::legendre(g, p) > 0) { + g++; + } + return g; + } }; /* @@ -320,11 +328,7 @@ public: if (p <= 2) throw cybozu::Exception("SquareRoot:bad p") << p; isPrime = gmp::isPrime(p); if (!isPrime) return; // don't throw until get() is called - // g is quadratic nonresidue - g = 2; - while (gmp::legendre(g, p) > 0) { - g++; - } + g = gmp::getQuadraticNonResidue(p); // p - 1 = 2^r q, q is odd r = 0; q = p - 1; |