On Polynomial Interpolations related to Verheul Homomorphisms
On Polynomial Interpolations related to Verheul Homomorphisms
复制标题
与 Verheul 同态相关的多项式插值
DOI：
10.1112/s1461157000001224
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Takakazu Satoh
中科院分区：
文献类型：
--
作者：
Takakazu Satoh
Verheul 同态是从域乘法群的有限子群到椭圆曲线的群同态。 Verheul 表明 Verheul 同态的计算难度与计算 Diffie-Hellman 问题的难度密切相关。设p 5 为素数，N 为满足√ 12p < N < 2p/√ 3 的素数，其中N = p。令 E 为 Fp 上的普通椭圆曲线，并令 C ⊂ E 为 N 阶循环子群。令 H 为所有 N 个单位根的群（包含在 Fp 的代数闭包中），并令 φ 为从 H 到 C 的 Verheul 同构。我们考虑一个多项式 P，使得 P(z) 是对于所有 z ∈ H − {1} 的 φ(z) 的 X 坐标。我们表明，对于至少大约 58% 的对 (E, C)，P 的非常数项的系数都没有消失。
The Verheul homomorphism is a group homomorphism from a finite subgroup of the multiplicative group of a field to an elliptic curve. The hardness of computation of the Verheul homomorphism was shown by Verheul to be closely related to the hardness of the computational Diffie–Hellman problem. Let p 5 be a prime, and let N be a prime satisfying √ 12p < N < 2p/ √ 3, where N = p. Let E be an ordinary elliptic curve over Fp, and let C ⊂ E be a cyclic subgroup of order N . Let H be the group of all N th roots of unity (contained in the algebraic closure of Fp), and let φ be the Verheul isomorphism from H to C. We consider a polynomial P such that P(z) is the X-coordinate of φ(z) for all z ∈ H − {1}. We show that, for at least approximately 58% of pairs (E, C), none of the coefficients of the non-constant terms of P vanishes.