One uses parametric families (r(x), t(x), q(x)) of pairing-friendly elliptic curves to obtain such curves with \(\rho \) -value closer to 1, and one of the goals is to obtain families with \(\rho \) close to 1. The Brezing-Weng method and its extension allow to construct complete, complete with variable discriminant, and sparse families. To construct families using these methods one chooses a number field K, which contains a kth primitive root of unity \(\zeta _k\) , and a polynomial \(r(x)\in \mathbb {Q}[x]\) such that \(K\cong \mathbb {Q}[x]/(r(x))\) , and then obtains t(x) and q(x) in \(\mathbb {Q}[x]\) according to these methods. Obtained triple (r, t, q) satisfies part of conditions from the definition of a family, and if this triple will be useful to obtain parameters of elliptic curves depends among others if one can expect to obtain infinitely many primes or prime powers as values of q(x) for \(x\in \mathbb {N}\) . In this paper for a number field K as above of the extension degree \(n=[K:\mathbb {Q}]>2\) we will consider triples \((z,\zeta _k,\alpha )\) of elements in K such that z is a primitive element of \(K/\mathbb {Q}\) , and \(\alpha \)  has a suitable property such that \((z,\zeta _k,\alpha )\) determines a triple of polynomials (r, t, q) as above, where r is the minimal polynomial of z over \(\mathbb {Q}\) , and t and q are obtained in a suitable way. Note that if \(\sqrt{-d}\in K\) for a square-free \(d\in \mathbb {Z}_{>0}\) , then one can use triples \((z,\zeta _k,\sqrt{-d})\) to search for complete families. For a fixed primitive element \(\gamma \) of \(K/\mathbb {Q}\) we will use coordinates of elements in K in the basis \(1,\ldots ,\gamma ^{n-1}\) . Let \(1\le \rho _0<2\) be a given upper bound on \(\rho \) -value. We will give conditions on coordinates of z and \(\alpha \) in K such that if \((z,\zeta _k,\alpha )\) satisfy these conditions, then one can obtain from it a triple (r, t, q) with \(\rho \le \rho _0\) . These conditions are given by ranks of some matrices, and equivalently can be given by minors of these matrices, hence one can obtain a system of polynomial equations on coordinates of elements in K. However for larger n because of degrees of polynomials in this system it can be difficult to determine solutions of this system.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Constructing Families of Pairing-Friendly Elliptic Curves with Small \(\rho \) -Value and Rational Solutions of Some Systems of Polynomial Equations

  • Robert Dryło

摘要

One uses parametric families (r(x), t(x), q(x)) of pairing-friendly elliptic curves to obtain such curves with \(\rho \) -value closer to 1, and one of the goals is to obtain families with \(\rho \) close to 1. The Brezing-Weng method and its extension allow to construct complete, complete with variable discriminant, and sparse families. To construct families using these methods one chooses a number field K, which contains a kth primitive root of unity \(\zeta _k\) , and a polynomial \(r(x)\in \mathbb {Q}[x]\) such that \(K\cong \mathbb {Q}[x]/(r(x))\) , and then obtains t(x) and q(x) in \(\mathbb {Q}[x]\) according to these methods. Obtained triple (r, t, q) satisfies part of conditions from the definition of a family, and if this triple will be useful to obtain parameters of elliptic curves depends among others if one can expect to obtain infinitely many primes or prime powers as values of q(x) for \(x\in \mathbb {N}\) . In this paper for a number field K as above of the extension degree \(n=[K:\mathbb {Q}]>2\) we will consider triples \((z,\zeta _k,\alpha )\) of elements in K such that z is a primitive element of \(K/\mathbb {Q}\) , and \(\alpha \)  has a suitable property such that \((z,\zeta _k,\alpha )\) determines a triple of polynomials (r, t, q) as above, where r is the minimal polynomial of z over \(\mathbb {Q}\) , and t and q are obtained in a suitable way. Note that if \(\sqrt{-d}\in K\) for a square-free \(d\in \mathbb {Z}_{>0}\) , then one can use triples \((z,\zeta _k,\sqrt{-d})\) to search for complete families. For a fixed primitive element \(\gamma \) of \(K/\mathbb {Q}\) we will use coordinates of elements in K in the basis \(1,\ldots ,\gamma ^{n-1}\) . Let \(1\le \rho _0<2\) be a given upper bound on \(\rho \) -value. We will give conditions on coordinates of z and \(\alpha \) in K such that if \((z,\zeta _k,\alpha )\) satisfy these conditions, then one can obtain from it a triple (r, t, q) with \(\rho \le \rho _0\) . These conditions are given by ranks of some matrices, and equivalently can be given by minors of these matrices, hence one can obtain a system of polynomial equations on coordinates of elements in K. However for larger n because of degrees of polynomials in this system it can be difficult to determine solutions of this system.