| 【中文题名】 | 一个推广的Lucas型素性测定算法 |
| 【英文题名】 | A Generalized Lucasian Primality Test |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-12-11 |
| 【中关键词】 | Lucas型素性测定算法,Lucas序列,Causs整数环,四次剩余特征,本原不可约元, |
| 【英关键词】 | Lucasian primality test,Lucas sequences,the ring of Gaussian integers,bi-quadratic residue characters,primary irreducibles, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>数论>> |
| 【论文摘要】 | 特殊形式的自然数，例如形式为M_(h，n)=h·2~n±1的数(h奇数，n正整数)，常是人们特别有兴趣的研究对象．经典的Lucas-Lehmer测试就是关于Mersenne素数2~p-1的快速多项式时间严格素性证明算法．这个测试包含一个Lucas序列{w_j:j≥0}，其中w_0为起始值(称为种子)，它对于所有奇素数p都取同一个值w_0=4，而w_j+1=w_j~2-2．关于Mersenne素数的Lucas-Lehmer测试可推广为对于M_(h，n)的Lucas型素性测试．在这个推广中，种子w_0既依赖于n又依赖于h．然而，就象寻找Mersenne素数那样，人们要做的事是：对固定的奇数h，当n增加时，搜索形式为M_(h，n)的素数．于是，如果可能的话，最好有一个不依赖于n的种子．对h≠0 mod 3，这是很容易的事．Bosma [Explicity primality criteria for h·2~n±1，Math．Comp．61(1993)，97-109，s7-s9．MR 1197510(94c:11005)]对每一个正奇数h≡0 mod3，h＜10~5(但h?4~m-1)，确定了一个有限集，使得对任意... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
Abstract |
6-7 |
|
第一章 引言 |
7-11 |
|
1.1 Lucas-Lehmer型素性测定算法 |
7-9 |
|
1.2 Berrizbeitia-Berry的改进算法 |
9-10 |
|
1.3 本文的主要工作 |
10-11 |
|
第二章 预备知识 |
11-15 |
|
2.1 高斯整环Z[i]的基本算术 |
11 |
|
2.2 四次剩余特征的基本性质 |
11-13 |
|
2.3 Lucas序列及n+1测试方法 |
13-15 |
|
第三章 推广的Lucas型素性测定算法 |
15-20 |
|
3.1 算法原理及其证明 |
15-16 |
|
3.2 算法所用种子的情况的进一步说明 |
16-18 |
|
3.3 算法流程和具体例子 |
18-20 |
|
第四章 算法的进一步研究 |
20-34 |
|
4.1 一些定义 |
20-21 |
|
4.2 种子集的选取 |
21-25 |
|
4.3 广义序列集 |
25-27 |
|
4.4 程序设计 |
27-34 |
|
参考文献 |
34-35 |
|
| 【DOI】 | LunWen.ID:2.2008.11304 |
