单参数二次基伪素数的初步研究

论文摘要

Jacobi-Sum算法和椭圆曲线素性证明算法（ECPP）是几乎多项式时间严格素性证明算法。印度计算机科学家M.Agrawal,N.Kayal和N.Saxena于2002.8.6在他们的网站http://www.cse.iitk.ac.in/上公布了全球第一个多项式时间严格素性证明算法（AKS算法）,在国际引起轰动,但AKS算法因多项式时间方次较高还不实用。人们目前普遍使用的是理论简单,算法易于实现且速度快的Rabin-Miller概率素性测试和Baillie-PSW概率素性测试。但人们对Baillie-PSW概率素性测试出错概率尚无准确结果。张振祥[Mathematics of Computation,71（2002）,1699-1734.MR 2003f:11191]先定义了单参数二次基伪素数和强伪素数.设u是大于2的整数,并记Tu=T（modT2-uT+1）,则对任一不整除u2-4的素数n有Tun-ε≡1（mod n）,其中ε为u2-4对于n的Jacobi符号。若合数n满足上式,就称n是基为Tu的（单参数二次基）伪素数,记作psp（Tu）。张振祥接着又提出Baillie-PSW测试的单参数二次基版本,简称单参数二次基测试（OPQBT）,给出了OPQBT的出错概率计算公式,并根据n的素因子个数给出了出错概率的上界。 本文对张振祥关于单参数二次基伪素数的未讨论的性质作初步研究。先证明了对于任意给定u>2有无穷多个psp（Tu）;然后讨论了乘法半群（Z[Tu]/（n）,·,1）的可逆元构成的群的阶及结构;并给出了两个二次基的乘积Ta·Tb是第三个二次基Tc（mod n）的充分必要条件;最后给出一个流程寻找108以下的所有的psp（T3）,共1460个,并对这些数进行统计分析。

论文目录

• 摘要
• 第一章 引言
• 1.1 Fermat测试和Miller测试
• 1.2 Baillie-PSW概率素性测试
• 1.3 单参数二次基伪素数和单参数二次基测试（OPQBT）
• 1.4 本文的主要工作
• 第二章 预备知识
• n和V_n的性质'>2.1 Lucas序列U_n和V_n的性质
• 2.2 Lucas伪素数的无穷性
• 第三章 单参数二次基伪素数的基的一些性质
• 3.1 单参数二次基伪素数的无穷性
• n[T_u]）'>3.2 群U（Z_n[T_u]）
• 3.3 单参数二次基的一些性质
• 第四章 数据分析
• 4.1 算法原理
• 4.2 算法流程
• 4.3 程序结果分析
• 参考文献
• 附件：两篇已发表论文首页