本文是René Schoof在1995年发表在《波尔多数论杂志》上的一篇论文,标题为"Counting points on elliptic curves over finite fields"。文章探讨了如何有效地计算有限域上椭圆曲线上的点数,这是数论中的一个重要问题,特别是在密码学领域,特别是在公钥加密算法如ElGamal和RSA中,椭圆曲线的点数量是安全性的关键参数。 论文首先介绍了Shanks的baby-step-giant-step (BSGS)策略,这是一种经典的计算有限域上椭圆曲线点数的方法。该策略将问题分解为两个步骤:婴儿步骤(较小规模的搜索)和巨人步骤(通过指数运算估计点的数量)。这种方法在有限域不是太大时非常实用,因为它可以在合理的时间内完成计算,尽管其时间复杂度大约为O(sqrt(p)),其中p是有限域的素数。 然而,Schoof意识到,当有限域变得非常大时,这种方法效率较低。因此,他提出了两种新的算法来解决这一挑战。第一种算法是基于椭圆曲线的Endomorphism Ring结构,利用了复数域上的整数环与椭圆曲线上的有理点之间的联系,将问题转化为计算某些特定整数的阶。这个过程更为高效,时间复杂度可以降低到接近线性,具体来说是O(log^3 p),这在处理大素数时具有显著优势。 第二种算法是更进一步的改进,它利用了模形式理论,尤其是Hecke算子。通过构造一个相关的模形式,并利用模形式的性质,Schoof得以设计出一种更为复杂的算法,理论上其时间复杂度可以达到最优的O(log p)。这个突破性的成果极大地推动了椭圆曲线算法的发展,尤其是在计算大素数域上的点数时,使得算法的性能得到了显著提升。 Schoof的这篇论文不仅提供了对有限域上椭圆曲线点数计数问题的深入理解,还引入了两种革命性的算法,这些算法在实际应用中对于密码学的安全性和效率有着深远的影响。后续的研究者在此基础上继续优化和扩展,使得椭圆曲线在现代密码学、编码理论以及数论中的应用更加广泛和高效。
![](https://csdnimg.cn/release/download_crawler_static/10966888/bg7.jpg)
![](https://csdnimg.cn/release/download_crawler_static/10966888/bg8.jpg)
剩余36页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
- 粉丝: 0
- 资源: 2
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)