关于Schoof算法的一个注记
|
摘要
寻找对椭圆曲线公钥体制(ECC)有用的椭圆曲线，关键在于求有限域上椭圆曲线有理点群的阶。一个公认的有效算法是1985年由R．Schoof提出的Schoof算法。在第一节里，我们介绍了椭圆曲线公钥密码体制的思想，同时还简单地介绍了几种寻找该密码体制所需要的椭圆曲线的方法。
在第二节里，我们介绍了Schoof算法所涉及的数学理论及此算法的基本思想。
在Schoof算法的具体实现中，需要用到有限域Fp~2的原根。在实用中，常常只需要大约200以内的p。第三节中，我们从有限域Fp的原根出发得到了一个求Fp~2的原根的算法，而且对较小的p(p＜200)得到Fp~2的原根表。
The key to finding a useful elliptic curve for Elliptic Curve Cryptosystem (ECC) is to compute the order of elliptic curve rational points group over a finite field. A well-known effective algorithm is Schoof's Algorithm introduced by R. Schoof in 1985. In Section 1, we briefly introduce the idea of ECC and several methods of finding useful elliptic curves needed for ECC.
In Section 2, we introduce mathematical theories and basic idea of Schoof's Algorithm.
In the practical realization of Schoof's Algorithm, a primitive root of a finite field Fp~(2) is needed. Generally, we only need a prime p less than 200 in practice. In Section 3, we get an algorithm to look for a primitive root of Fp~(2) from a given primitive root of the finite field Fp. What's more, a table of primitive roots over Fp~(2) can be provided for those prime numbers p (p<200).
在第二节里，我们介绍了Schoof算法所涉及的数学理论及此算法的基本思想。
在Schoof算法的具体实现中，需要用到有限域Fp~2的原根。在实用中，常常只需要大约200以内的p。第三节中，我们从有限域Fp的原根出发得到了一个求Fp~2的原根的算法，而且对较小的p(p＜200)得到Fp~2的原根表。
The key to finding a useful elliptic curve for Elliptic Curve Cryptosystem (ECC) is to compute the order of elliptic curve rational points group over a finite field. A well-known effective algorithm is Schoof's Algorithm introduced by R. Schoof in 1985. In Section 1, we briefly introduce the idea of ECC and several methods of finding useful elliptic curves needed for ECC.
In Section 2, we introduce mathematical theories and basic idea of Schoof's Algorithm.
In the practical realization of Schoof's Algorithm, a primitive root of a finite field Fp~(2) is needed. Generally, we only need a prime p less than 200 in practice. In Section 3, we get an algorithm to look for a primitive root of Fp~(2) from a given primitive root of the finite field Fp. What's more, a table of primitive roots over Fp~(2) can be provided for those prime numbers p (p<200).
引文
[1] N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48(1987), 203-209.
[2] V. Miller, Use of elliptic curves in cryptography, Advances in Cryptology-Crypto'85, Springer-Verlag (1986), 417-426.
[3] Silverman, The arithmetic of elliptic curves, GTM106, Springer-Verlag, 1977.
[4] 朱文余、孙琦，计算机密码应用基础，科学出版社，2000年．
[5] R. School, Counting points on elliptic curves over finite fields, Journal de Theorie des Nombers de Bordeaux, 7(1995), 219-254.
[6] R. Schoof, Elliptic curve over finite fields and the computation of square roots mod P. Mathematics of Computation, 44(1985), 483-494.
[7] 华罗庚著，《数论导引》，科学出版社，1957年出版
[8] 柯召，孙琦著，《数论讲义》，高等教育出版社，1986年出版
[9] Lidl, R. & Niederreiter, H., Finite Fields, Encycl. of Math. and Its Appl., Vol. 20, Addison-Wesley, Reading Mass, 1983
[10] N. Koblitz, p-adic Numbers, p-adic Analysis and Zeta-Functions, GTM 58, Springer-Verlag (1984).
[11] N. Koblitz, A Course in Number Theory and Cryptography, 2nd ed., GTM 114, Springer-Verlag(1994).
[2] V. Miller, Use of elliptic curves in cryptography, Advances in Cryptology-Crypto'85, Springer-Verlag (1986), 417-426.
[3] Silverman, The arithmetic of elliptic curves, GTM106, Springer-Verlag, 1977.
[4] 朱文余、孙琦，计算机密码应用基础，科学出版社，2000年．
[5] R. School, Counting points on elliptic curves over finite fields, Journal de Theorie des Nombers de Bordeaux, 7(1995), 219-254.
[6] R. Schoof, Elliptic curve over finite fields and the computation of square roots mod P. Mathematics of Computation, 44(1985), 483-494.
[7] 华罗庚著，《数论导引》，科学出版社，1957年出版
[8] 柯召，孙琦著，《数论讲义》，高等教育出版社，1986年出版
[9] Lidl, R. & Niederreiter, H., Finite Fields, Encycl. of Math. and Its Appl., Vol. 20, Addison-Wesley, Reading Mass, 1983
[10] N. Koblitz, p-adic Numbers, p-adic Analysis and Zeta-Functions, GTM 58, Springer-Verlag (1984).
[11] N. Koblitz, A Course in Number Theory and Cryptography, 2nd ed., GTM 114, Springer-Verlag(1994).