新的素数检测方法  

A New Method for Detecting Prime Numbers

作　　者：周从尧 余未[2] 汤小宁 汤康恩 

机构地区：[1]湖南大学信息科学与工程学院,湖南长沙410028 [2]宁波大学理学院数学系,浙江宁波315211 [3]Oracle(中国)软件有限公司,北京100020

出　　处：《数学的实践与认识》2013年第24期251-257,共7页Mathematics in Practice and Theory

摘　　要：提出了一个快速而简单的素数检测方法,它的时间复杂性为O(log^(3+ε)N)这里0<ε≤1,空间复杂性为O(logN),N≡3(mod 4)时,时间复杂性为O(log^(2+ε)N),是迄今为止最快的多项式算法.This Paper provides a very fast and simplely method for primality proving, It＇ s time complexity is O（log2^3＋εN）. Where 0〈ε≤1, space complexity is O（log2N）, when N-3（mod 4）, It＇ s time complexity is O（log2^2＋εN）.

关 键 词：数论 算法 计算数论 素数检测 

分 类 号：O156[理学—数学]