Explicit primality criteria for h . 2(n) +/- 1

CSpace > 系统科学研究所

	Explicit primality criteria for h . 2(n) +/- 1
	Deng, Yingpu1 ; Huang, Dandan 1,2
	2016
发表期刊	JOURNAL DE THEORIE DES NOMBRES DE BORDEAUX
ISSN	1246-7405
卷号	28 期号:1 页码:55-74
摘要	Let {(T-k(1), . . .T-k(f))}(k >= 0) be a sequence of f-tuples of rational numbers defined from a seed (T-0(1), . . . ,T-0(f)), which is a given initial value, by f recurrences which are polynomials in f variables from the k-th term to deduce the (k + 1)-th term, k >= 0. We describe an algorithm which needs two such sequences with two suitable seeds to determine the primality of numbers h . 2(n) +/- 1, provided h not equal 0 (mod 17), and it runs in deterministic quasi-quadratic time. In particular, when h = 16(m) - 1, m odd, we have a test with two seeds depending only on h, not on n, while the result of Berrizbeitia and Berry (2004) implied that no finite family of seeds for their Lucasian primality test would suffice to test the primality of h . 2(n) +/- 1 for all n. The techniques which we used are Octic and Bioctic Reciprocity Laws.
关键词	Primality test Generalized Lucasian sequence Reciprocity Law Computational complexity
语种	英语
资助项目	NNSF of China[11471314] ; NSFC[11401312] ; NSF of the Jiangsu Higher Education Institutions[14KJB110012] ; National Center for Mathematics and Interdisciplinary Sciences, CAS
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000372940600003
出版者	UNIV BORDEAUX, INST MATHEMATIQUES BORDEAUX
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/22405
专题	系统科学研究所
通讯作者	Huang, Dandan
作者单位	1.Chinese Acad Sci, Acad Math & Syst Sci, NCMIS, Key Lab Math Mechanizat, Beijing 100190, Peoples R China 2.Jinling Inst Technol, Sch Software Engn, Lab Informat Secur, Nanjing 211169, Jiangsu, Peoples R China
推荐引用方式 GB/T 7714	Deng, Yingpu,Huang, Dandan. Explicit primality criteria for h . 2(n) +/- 1[J]. JOURNAL DE THEORIE DES NOMBRES DE BORDEAUX,2016,28(1):55-74.
APA	Deng, Yingpu,&Huang, Dandan.(2016).Explicit primality criteria for h . 2(n) +/- 1.JOURNAL DE THEORIE DES NOMBRES DE BORDEAUX,28(1),55-74.
MLA	Deng, Yingpu,et al."Explicit primality criteria for h . 2(n) +/- 1".JOURNAL DE THEORIE DES NOMBRES DE BORDEAUX 28.1(2016):55-74.