| 【中文题名】 | LUCAS序列及其应用研究 |
| 【英文题名】 | On Lucas Sequences with Applications |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2004-7-8 |
| 【中关键词】 | Lucas序列,运算量,乘除法次数,整数分解,素性测定, |
| 【英关键词】 | Lucas sequences,factorization,primality testing,arithematic labor,number of multiplications., |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>数论>> |
| 【论文摘要】 |
单参数Lucas序列U_n=U_n(u)和V_n=V_n(u)定义为：U_0=0,V_0=2,U_1=1,V_1=u,U_n=uU_(n-1)-U_(n-2),V_n=uV_(n-1)-V_(n-2),n≥2.该序列在数论中有广泛应用。张振祥在文“Using Lucas sequences to factor large intcgets near group orders”[Fibonacci Quarterly，Vol．39，2001，pp．228-237；MR 2002c：11173]和文“A one-parameter quadratic-base version of ttle Baillie-PSW probable prime test”[Math．Comp．，Vol．71，2003，pp．1699-1734；MR 2003f：11191]中，以Lucas序列为主要工具分别给出了一个整数分解方法和一个素性测定方法。其中在前一篇文章中讨论了这样的一类整数分解问题：N=pq是两个奇素数之积，q=k(p+1)+r,|r|＜(p+1)/2,k≥7,((u~2-4)/p)=-1且gcd(u，N)=... |
| 【论文题纲】 |
|
摘要 |
5-7 |
|
第一章 引言 |
7-12 |
|
1.1 Lucas序列在整数分解中的应用 |
7-8 |
|
1.2 Lucas序列在素性测定中的应用 |
8-10 |
|
1.3 本文的主要工作 |
10-12 |
|
第二章 预备知识 |
12-16 |
|
2.1 Lucas序列U_n(u)，V_n(u)的基本性质 |
12-14 |
|
2.2 时间复杂度的基本概念 |
14-16 |
|
第三章 定理的证明 |
16-19 |
|
3.1 几个引理 |
16-17 |
|
3.2 定理的证明 |
17-19 |
|
第四章 算法的分析及比较 |
19-25 |
|
4.1 两个方幂模(a~s mod M)算法 |
19-21 |
|
4.2 计算U_s mod n，V_s mod n的两个算法 |
21-23 |
|
4.3 参数k的选取和实例比较 |
23-25 |
|
参考文献 |
25-27 |
|
附件: 已发表论文首页复印件 |
27 |
|
| 【DOI】 | LunWen.ID:2.2008.11237 |
