| 【中文题名】 | 寻找是强伪素数的Carmichael数 |
| 【英文题名】 | Finding Carmichael Numbers which are Strong Pseudoprimes |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-12-11 |
| 【中关键词】 | Carmichael数,Rabin-Miller测试,强伪素数,素性测定,计算数论, |
| 【英关键词】 | Carmichael numbers,Rabin-Miller test,strong pseudoprimes,primality testing,computational number theory, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>数论>> |
| 【论文摘要】 | 定义ψ_m是关于前m个素数基的最小强伪素数。如果知道ψ_m的准确值，那么对小于ψ_m的整数N，我们就有一个确定性素性测定算法，它不仅容易实现而且比Jacobi-Sum算法、椭圆曲线素性证明算法和AKS算法速度都要快。Pomerance等[Math．Comp．Vol．35，1980，pp．1003-1026；MR 82g：10030]和Jaeschke[Math．Comp．Vol．61，1993，pp．915-926，MR 94d：11004]给出ψ_m(1≤m≤8)的准确值。张振祥和汤敏(Math．Comp．Vol．72，2003，pp．2085-2097；MR 2004c：11008]用快速算法找出10~(20)以内的全部关于前5个素数基的强伪素数的C_3-数。这里C_3-数指的是三素因子的Carmichael数N=q_1q_2q_3，q_1≡q_2≡q_3≡3 mod 4。因为在一定的范围之内C_3-数是强伪素数的概率高，所以很可能就是ψ_m的准确值。他们得到ψ_9，ψ_(10)和ψ_(11)的一个猜想值：
ψ_9=ψ_(10)=ψ_(11)=3825 12305 65464 13051=... |
| 【论文题纲】 |
|
摘要 |
5-7 |
|
第一章 引言 |
7-12 |
|
1.1 Fermat测试和Rabin-Miller测试 |
7-8 |
|
1.2 确定性Rabin-Miller测试的研究成果 |
8-11 |
|
1.3 本文的主要工作 |
11-12 |
|
第二章 预备知识 |
12-17 |
|
2.1 强伪素数和Carmichael数 |
12-14 |
|
2.2 搜索C_3-数的快速算法 |
14-17 |
|
第三章 寻找C_(3,1)-数的快速算法 |
17-22 |
|
3.1 C_(3,1)-数的充分必要条件 |
17-18 |
|
3.2 算法流程 |
18-19 |
|
3.3 例子和搜索结果 |
19-22 |
|
第四章 寻找C_(3,2)-数的快速算法 |
22-26 |
|
4.1 C_(3,2)-数的充分必要条件 |
22-23 |
|
4.2 算法流程 |
23-24 |
|
4.3 例子和搜索结果 |
24-26 |
|
第五章 小结 |
26-28 |
|
参考文献 |
28-30 |
|
附件：两篇已发表论文首页 |
30-31 |
|
| 【DOI】 | LunWen.ID:2.2008.11307 |
