diff options
| author | MITSUNARI Shigeo <herumi@nifty.com> | 2019-02-20 08:51:34 +0800 |
|---|---|---|
| committer | MITSUNARI Shigeo <herumi@nifty.com> | 2019-02-20 08:51:34 +0800 |
| commit | 08148dcf605117f495545cdf3ce29afb1e9c963e (patch) | |
| tree | 16078825901bf033bda072e3df4090bd755786d5 | |
| parent | d6229da5aaf6ed0e9154c918e731c4a09b629177 (diff) | |
| download | tangerine-mcl-08148dcf605117f495545cdf3ce29afb1e9c963e.tar.gz tangerine-mcl-08148dcf605117f495545cdf3ce29afb1e9c963e.tar.zst tangerine-mcl-08148dcf605117f495545cdf3ce29afb1e9c963e.zip | |
LagrangeInterpolation sets out = yVec[0] if k = 1
| -rw-r--r-- | include/mcl/bn.h | 1 | ||||
| -rw-r--r-- | include/mcl/lagrange.hpp | 13 | ||||
| -rw-r--r-- | readme.md | 1 | ||||
| -rw-r--r-- | test/bench.hpp | 2 |
4 files changed, 13 insertions, 4 deletions
diff --git a/include/mcl/bn.h b/include/mcl/bn.h index 6499280..0044d9d 100644 --- a/include/mcl/bn.h +++ b/include/mcl/bn.h @@ -379,6 +379,7 @@ MCLBN_DLL_API void mclBn_precomputedMillerLoop2mixed(mclBnGT *f, const mclBnG1 * Lagrange interpolation recover out = y(0) by { (xVec[i], yVec[i]) } return 0 if success else -1 + @note *out = yVec[0] if k = 1 @note k >= 2, xVec[i] != 0, xVec[i] != xVec[j] for i != j */ MCLBN_DLL_API int mclBn_FrLagrangeInterpolation(mclBnFr *out, const mclBnFr *xVec, const mclBnFr *yVec, mclSize k); diff --git a/include/mcl/lagrange.hpp b/include/mcl/lagrange.hpp index 7c02188..feca80d 100644 --- a/include/mcl/lagrange.hpp +++ b/include/mcl/lagrange.hpp @@ -15,14 +15,19 @@ namespace mcl { template<class G, class F> void LagrangeInterpolation(bool *pb, G& out, const F *S, const G *vec, size_t k) { + if (k == 0) { + *pb = false; + return; + } + if (k == 1) { + out = vec[0]; + *pb = true; + return; + } /* delta_{i,S}(0) = prod_{j != i} S[j] / (S[j] - S[i]) = a / b where a = prod S[j], b = S[i] * prod_{j != i} (S[j] - S[i]) */ - if (k < 2) { - *pb = false; - return; - } F a = S[0]; for (size_t i = 1; i < k; i++) { a *= S[i]; @@ -443,6 +443,7 @@ Y. Sakemi, Y. Nogami, K. Okeya, Y. Morikawa, CANS 2008. # History
+* 2019/Feb/20 LagrangeInterpolation sets out = yVec[0] if k = 1
* 2019/Jan/31 add mclBnFp_mapToG1, mclBnFp2_mapToG2
* 2019/Jan/31 fix crash on x64-CPU without AVX (thanks to mortdeus)
diff --git a/test/bench.hpp b/test/bench.hpp index b12947a..12868d3 100644 --- a/test/bench.hpp +++ b/test/bench.hpp @@ -185,4 +185,6 @@ void testLagrange() Fr s; mcl::LagrangeInterpolation(s, x, y, k); CYBOZU_TEST_EQUAL(s, c[0]); + mcl::LagrangeInterpolation(s, x, y, 1); + CYBOZU_TEST_EQUAL(s, y[0]); } |