[关闭]
@devilogic 2017-10-23T00:35:08.000000Z 字数 18952 阅读 3582

玩命的销售日志 2017.10.23

日志 devilogic

image_1br6840ssnir1ta0gf319821irap.png-11.2kB

最近一直没有写日志,销售工作有点忙而我又不是很擅长。不太会忽悠,广告词也不知道该如何说。厂矿大院成长起来的孩子总体来说还是实在。总之见了客户尽量说实话,感觉客户也不傻还是能分辨谁说的假谁说的真,也算是跑销售的心得体会。
最近把公司销售&售前的提成重新整了一下,提高了团队的积极性。销售主管和我说某同行提成政策又改了之前也没兑现。想想同行中某些人的操行,应该还是能做出这种事情的。
我一直以来以为我是个烂人,常干点不靠谱儿事情,也常吹牛逼。一直以来对自己的人品没啥自信。创业这几年突然让我找回了人品的自信,时长感慨自己是个好人。
上个月在机场看到看雪的一篇关于RSA的帖子。就想把RSA都完整的探讨一下。在写到确定素数算法时,我想把一些著名的素性测试算法都探讨一遍。近几年最著名的就算AKS算法了。由三个印裔的哥们设计的(算法的名称取自他们的首字母)。所以就在国庆期间翻译了这篇论文。中文翻译过来大意叫做在多项式时间内的素性确定算法。其实算法本身并不复杂,理解起来也不难。但是其中有一个多项式消减问题。国庆期间大概花了一个小时左右写好了算法流程本身。然而多项式消减这个操作我陆陆续续写了两周
左右。
其实本来也花不到那么长的时间,只是范了程序员的通病,慢慢的把一个小程序越写越大,到基本功能完成时写了行左右的python代码(如果用C/C++的话,应该在行左右)。实现了一个简易的符号系统(其中对外的输出使用Latex的数学公式表示),可以做二项式展开多项式合并,以及多项式的加减乘除操作。在上周天的感觉在数值为分数时自动配方不是很好,又重写了一个叫做yvalue的数值类,把浮点数与整数在保存时,就转化成分数的形式。在求值时才展开。还可以处理类似这样的形式。连分数的处理是OK的。
多项式的消减的逻辑还是很烧脑的。本来AKS只需要一个一元次的展开即可,出于一个程序员的态度,我还是完成了多元多次式的运算。下图显示了。后的商式与余式。其中展开后的结果。

1508692014(1).png-10.1kB
可以从"https://coding.net/u/devilogic/p/hkfiction/git/tree/master/ysym"下载这份代码。年底要是有时间可能会陆陆续续的完善这个符号计算库。把自动积分,微分也加进去。如果再有时间就写一个类似sympy的库(貌似sympy不支持多项式的运算)。希望这个小小的愿望可以得到实现吧。
下图是我实现的AKS算法的流程输出,感觉可以当做教学课件了。现在网上基本找不到AKS的完整真正实现,有些实现都是直接把代入一个固定的数值,这样其实不能算是AKS算法,只能算是该算法的一个应用。这样在数值小的时候没问题,当要确定的一个数过大时就没有用了。其中多项式消减操作就是为了避免处理数值过大后大数运算带来的效率问题。
下图是程序的输出截图:
1508697010(1).png-89.1kB
可以从"https://coding.net/u/devilogic/p/hkfiction/git/blob/master/aks.py"下载这份代码。
这份代码中,需要使用大数运算库gmpy2的支持。运行环境为python34python27。3.6目前不支持原因在于gmpy2不支持3.6的版本。另外还需要说明的是程序有bug没有修订,gmpy2没有在所有的运算中使用,空了时间再填补上吧。
下面译文还有一些需要说明的是有些是我自己的注释,使用以下这种方式:

这里是我的注释


1.介绍

由于在现代密码学中需要非常大的素数来参与运算,所以素数的判定非常的重要。

我们使用PRIMES来代替素数集合。素数定义本身已经给出了一种算法来确定一个整数。尝试使用去除以每个整数,如果有任意可以整除。那么合数。否则它是一个素数。

。为什么是它的界限。一个很简单
的证明是,一个合数是最少两个素数相乘组成的。设,其中
那么设;如果,那么。如果假设
。那么。所以与条件矛盾。

这种测试算法在古希腊被称为埃拉托色尼[1] (ca. 240 BC)分解法。它需要遍历所有小于的素数,这很低效,需要花费大概步去决定是否是一个素数。一个更加有效的测试是基于费马小定理[2]:对于任意素数与一个任意不能整除它的整数,存在。给定一个整数去确定整数是否是一个素数时,需要对反复进行次平方,但是,它仍然不是一个总是正确的测试,因为有些是合数是也可以通过这个测试(这些被称作为卡米切尔数[3])。无论如何,费马小定理都是有效素性测试算法的基础。

直到在1960年,复杂理论[4]出现,从而将问题的复杂性进行标准化并且将复杂性问题的种类进行了定义(例如素性测试就是一个复杂性问题)。素性测试才被重视起来。开始这个问题被认为是一个[5]问题:如果不是一个素数,那么拥有一个非平凡因子将很容易的被验证。在1974年,Pratt认为这个问题是一个问题(因此将它放入)。

在1975,Miller使用一个基于费马小定理的属性去证明扩展黎曼假设[6]。很快的他的测试被Rabin修改为一个无条件但是是随机多项式时间的算法。在1974年索洛韦和Strassen也独立的提出了一个不同的随机多项式时间算法,这个算法使用了一个素数,对于每一个存在(是雅可比符号[7])。他们的算法在扩展黎曼假设的条件下也可以直接确定素数。后来有基于不同特性的随机多项式时间测试素数的算法。

在1983年,Adleman,Pomerance,与 Rumely在素性测试方面取得了一个决定性的进展,这个算法可以运行在时间(之前所有的算法都是在指数时间)。他们的算法(感觉上)是Miller算法的更加通用的形式并且使用更高级的相互作用规则。在1986年,Goldwasser与Kilian提出一个基于椭圆曲线[8]在大多数输入(所有的输入都被认为是合乎条件的)条件下可以运行在多项式时间。这使素性测试变得很容易(指导那时,所有的随机算法产生的验证结果都仅仅是复合性的)。基于他们的想法,一个类似的算法被Aktin发明。Adleman与Huang修改Goldwasser-Kilian的随机算法期望在所有的输入条件下运行在多项式时间。

一个无条件多项式时间确定素数的算法是这个研究的最终目标。尽管到现在这项研究已经取得了极大的成绩,但是离最终目标还有段距离。在这篇论文中,我们达到了最终目的。我们在确定一个数是否是素数在时间内。在一些条件下,我们的算法会做的更好:普遍认为在苏菲日耳曼素[9]的密度下(如果素数那么也是素数),我们的算法仅花费步。我们的算法是基于在有限域多项式环的费马小定理。证明我们定理的正确性只需要一些简单的代数功能(除了在之间有一个非常大的素因子的筛选法的结果并且甚至不需要证明这个算法是工作在这个很短的时间内)。之前的算法证明要复杂的多。

在第二节,我们简单阐述了这个算法的核心思想。在第三节,我们明确了一些标记的使用。在第四节,我们证明了这个算法的正确性。在第五个小节,我们分析这个算法的性能。在第六节我们探讨对这个算法优化的方法。

其实这节就是介绍一下多项式时间确定素数算法的在历史上的取得的进展。


2.核心思路

我们的测试是基于费马小定理。它也是随机多项式时间算法的基础。

这里我们先花些时间来探讨下费马小定理,这是很有必要的。
如果是一个素数,那么对于所有的整数,数的整数倍。又可以表示为:


举例说明,如果并且那么,并且
如果互素,上边的等式可以两边消去一个费马小定理的形式为

举例说明,如果并且,那么并且的整数倍。
以上就是费马小定理的基本内容。论文中的第二节就是其使用多项式理论对其证明的一个过程。

引理 2.1 使并且。当且仅当


是素数。

其实以上就是费马小定理的一般化形式

证明: 循环遍历的系数在

忘记组合公式的同学看这里:

如果是一个素数。则 因此所有的系数为0。

个人比较讨厌,没有来由的数学等式,那就让我们展开来讨论一下这个等式。在探讨之前先把二项式定理放到前面膜拜一
下牛顿他老人家。

二项式展开式定理:令为实数,是一个正整数。则

展开等式的左边得到如下的等式:

其中除了第一项与最后一项都不能被整除法,其余的项当模时,它们都被削减掉了。当削减掉中间的项后等式变成剩下的就是

如果是一个合数。假设的一个素因子并且使得。然而不能整除并且与互素,因此的系数非。因此在模的环[10]中为非

以上的等式暗示了一个简单的素性测试方法:给定一个输入,选择一个数并且测试等式是否相等。但是,这需要花费

表示对于任意一个,则
因为上述等式的系数项有个,最坏的情况是当模后(此时,
一个合数),每个系数项都为非

因为在最坏的情况下计算左边等式个系数。一个简化方法是等式两边都模一个多项式,其中的。等同于测试如下等式:


根据引理 2.1,对于所有的,当素数时都满足等式。现在的问题是有很少的合数时也满足此等式。

总体来说就是:我们选择一个合适的数,如果等式满足,那么对于一些少量的合数,对于大量的与一个合适数关于在多项式时间有界,因此我们获得一个在多项式时间内确定素数的算法。


3.标记与预读

关于以及问题的详细解释参见参考资料。

表明模的环。是模的有限域[11],其中素数
回想一下如果是素数,是一个在域的次可削减多项式,那么是以为阶的有限域。我们将使用来表示在环内的等式

上述等式就是表示首先对模做削减操作,随后在做
的操作,保证结果在环中。

我们使用符号来表示,其中表示变量的函数。例如,对于任意一个。我们使用表示以为底的对数,自然对数使用来表示。

分别表明自然数集与整数集。给定,其中,其中是满足元素群的最小的阶,。它使用来表示。对于欧拉函数表示满足所有小于的素数的个数。其中对于每一个,则

引理3.1 使用表示前数的最小公倍数。对于


4.算法与证明

输入一个大于1的正整数
1. 如果对于每一个,则,输出合数
2. 找到一个最小的整数,使得
3. 如果对于一些,则,输出合数
4. 如果,输出素数
5. 循环测试每一个,如果输出合数
6. 输出素数

定理 4.1 以上算法返回素数,当且仅当是素数。
在以下得小节中,我们应用这个定理到所有得引理中。下面得定理就是一个简单得应用。

引理 4.2 如果是一个素数,以上算法将返回素数
证明:如果是一个素数,那么步骤1到3将绝不会返回合数。通过引理 2.1,进入到循环中也不能返回合数。因此算法将返回素数在步骤4或者步骤6。

以上引理的反向证明需要花一点功夫。如果算法在步骤4返回素数,那么前3个步骤没有都没有发现非平凡因子。因此仅剩一种情况是步骤6。

这个算法拥有两个重要的步骤(25):步骤2中寻找一个合适的而步骤5验证整数是否符合等式。在此之前我们首先要确定的量级。

步骤2与5是这个算法的一个难点,所以作者帮忙找出了一个很合适值,
就是引理 4.3提出的理论。

引理 4.3[12] 存在

证明:当时,满足所有条件。当时,那么 并且根据引理 3.1。观察到对于一个最大的值对于任意,是。现在考虑将不下式整除的最小的


根据以上的观察将不能被任何的素因子整除,除非可以被整除。因此也不能被以上结果整除。是最小的不能被上述结果整除的值,由此可见。更进一步的,由于对于每个都不能被整除以及。所以,

(保证第二个不等式的所有的),根据引理 3.1,数的第一个最小公倍数至少是。因此,

由于,必然存在的一个素因子,使得。由于步骤3或者步骤4可以确定的素性。因此,我们有。由于(步骤3或者步骤4将确定的类型),。在这节剩余的部分将讨论数的问题。而且,使得

步骤5用于验证等式。由于在这个步骤算法不输出合数,所以,我们有:


对于每个(如果,那么等式必然成立)。意味着:

对于每个,根据引理2.1,我们有:

对于每个,根据等式与等式

对于每个,在上述等式中,两者的表现都与素数一样。我们给这种属性取个名称:
定义4.4 对于一个多项式与一个数,我们称内省的(introspective)对于当:

对于在等式与等式内省的,还是比较清晰的。
下面的引理展示了内省数是符合乘法法则的。
引理4.5 如果对于是内省的,那么也是。
证明:由于对于是内省的,我们有:

同样,由于对于是内省的,我们有(将替换成):

上式中可被 整除。
合并上面两个等式,我们可以得到:

所以多项式的内省数是符合乘法原则的。

引理4.6 如果内省数对于每个多项式成立,那么对于它们的积也成立。
证明:

上述两个引理意味在每个在集合中的数对于多项式集合都成立。现在我们定义基于以上两个集合的两个群。

第一个群是的所有剩余类。由于通过观察,,因此它是(模的既约剩余类)的一个子群。设来表示这个群并且(表示群的数量)。是通过产生的,所以其阶
为了定义第二个群,我们需要一些关于在有限域上的分圆多项式的基础知识。

使用来表示在上的次分圆多项式。多项式可以被整除并且其因子是阶为的不可约因子。让表示这样一个不可约因子。由于,所以的阶大于。第二个群是所有在中模可被消减的多项式。使用来表示它。这个群是通过在域中的多项式产生的,并且是群的整数倍的子群。
下面的引理证明了群长度的一个下界。

引理4.7(Hendrik Lenstra Jr.)
证明:首先要说明的是是分圆多项式的一个因子,是在中的次本原单位根。
现在我们的说明的是任意两个在中阶小于的多项式在中的映射都有不同的值。让表示在中的这样两个多项式。假设在域,设。我们有在域。由于的内省数,并且可以被整除,所以在域中我们得到:


这意味着对于每个是多项式的一个根。由于(的一个子群),每个都是次本原单位根。因此在中当时,有相异根。可是通过选择可以使得的阶小于。这是这与假设矛盾,在
对于在中的每一个,其中并且。因此在两两相异。又因为的阶大于,在中对于每个(),。因此在中至少存在个不同的一阶多项式,因此在中至少存在个相异的阶的多项式。
在这种情况下,不是的纯幂次形式,而的长度的一个上界也可以确定:
引理4.8 如果不是的纯幂次形式,那么
证明,考虑以下的子集:

如果不是的纯幂次形式,那么集合
个,其中每个元素两两相异。由于,其中至少两个在中的数同余。设。因此我们有:

,那么

所以在域

因此是多项式在域中的一个根。中的任意元素,因此在中多项式至少有个两两相异的根。的阶是。这说明
通过预估出来的的规模,我们现在证明算法的正确性:
引理4.9 如果算法返回素数,那么是素数。
证明,假设算法返回素数,根据引理4.7意味着对于

根据引理4.8,如果不是的纯幂次形式,那么。因此对于一些。如果那么算法将在第一步返回合数。因此,
以上就是整个算法的完整证明。


到这里为止就是AKS的原理部分,后边的部分是效率分析与未来改进的地方,没兴趣的可以不做了解了。这里我们稍微做下总结,并且按照程序员的角度一步步的分析并给出Python语言的实现。

  1. #!/usr/bin/python
  2. # coding:utf-8
  3. #import numpy as np
  4. import math
  5. import ysym
  6. from ysym.ypolynomial import *
  7. import gmpy2
  8. def is_prime_by_AKS(n):
  9. """
  10. 使用AKS算法确定n是否是一个素数
  11. True:n是素数
  12. False:n是合数
  13. """
  14. def __is_integer__(n):
  15. """
  16. 判断一个数是否是整数
  17. """
  18. i = int(n)
  19. f = n - i
  20. return not f
  21. def __phi__(n):
  22. """
  23. 欧拉函数,测试小于n并与n互素的个数
  24. """
  25. res = n
  26. a = n
  27. for i in range(2, a+1):
  28. if a % i == 0:
  29. res = res // i * (i - 1)
  30. while a % i == 0:
  31. a //= i
  32. if a > 1:
  33. res = res // a * (a - 1)
  34. return res
  35. def __gcd__(a, b):
  36. """
  37. 计算a b的最大公约数
  38. """
  39. if b == 0:
  40. return a
  41. return __gcd__(b, a % b)
  42. print("步骤1, 确定%d是否是纯次幂" % n)
  43. for b in range(2, math.floor(math.log2(n))+1):
  44. a = n**(1/b)
  45. if __is_integer__(a):
  46. return False
  47. print("步骤2,找到一个最小的r,符合o_r(%d) > (log%d)^2" % (n, n))
  48. maxk = math.floor(math.log2(n)**2)
  49. maxr = max(3, math.ceil(math.log2(n)**5))
  50. nextR = True
  51. r = 0
  52. for r in range(2, maxr):
  53. if nextR == False:
  54. break
  55. nextR = False
  56. for k in range(1, maxk+1):
  57. if nextR == True:
  58. break
  59. nextR = (gmpy2.mpz(n**k % r) == 0) or (gmpy2.mpz(n**k % r) == 1)
  60. r = r - 1 # 循环多增加了一层
  61. print("r = %d" % r)
  62. print("步骤3,如果 1 < gcd(a, %d) < %d,对于一些 a <= %d, 输出合数" % (n, n, r))
  63. for a in range(r, 1, -1):
  64. g = __gcd__(a, n)
  65. if g > 1 and g < n:
  66. return False
  67. print("步骤4,如果n=%d <= r=%d,输出素数" % (n, r))
  68. if n <= r:
  69. return True
  70. print("步骤5")
  71. print("遍历a从1到\sqrt{\phi(r=%d)}logn=%d" % (r, n))
  72. print("如果(X+a)^%d != X^%d+a mod {X^%d-1, %d}$输出合数" % (n, n, r, n))
  73. # 构造P = (X+a)^n mod (X^r-1)
  74. print("构造多项式(X+a)^%d,并且进行二项式展开" % n)
  75. X = multi_ysymbols('X')
  76. a = multi_ysymbols('a')
  77. X_a_n_expand = binomial_expand(ypolynomial1(X, a), n)
  78. print(X_a_n_expand)
  79. X.pow(r)
  80. reduce_poly = ypolynomial1(X, ysymbol(value=-1.0))
  81. print("构造消减多项式 %s" % reduce_poly)
  82. print("进行运算 (X+a)^%d mod (X^%d-1)" % (n, r))
  83. r_equ = ypolynomial_mod(X_a_n_expand, reduce_poly)
  84. print("得到余式: %s" % r_equ)
  85. print("进行运算'余式' mod %d 得到式(A)" % n)
  86. A = ypolynomial_reduce(r_equ, n)
  87. print("A = %s" % A)
  88. print("B = x^%d+a mod x^%d-1" % (n, r))
  89. B = ypolynomial1(multi_ysymbols('X', power=31), a)
  90. B = ypolynomial_mod(B, reduce_poly)
  91. print("B = %s" % B)
  92. C = ypolynomial_sub(A, B)
  93. print("C = A - B = %s" % C)
  94. maxa = math.floor(math.sqrt(__phi__(r)) * math.log2(n))
  95. print("遍历a = 1 to %d" % maxa)
  96. print("检查每个'%s = 0 (mod %d)'" % (C, n))
  97. for a in range(1, maxa+1):
  98. print("检查a = %d" % a)
  99. C.set_variables_value(a=a)
  100. v = C.eval()
  101. if v % n != 0:
  102. return False
  103. print("步骤6 输出素数")
  104. return True
  105. if __name__ == "__main__":
  106. n = 31
  107. print("检查'%d'是否为素数" % n)
  108. result = is_prime_by_AKS(n)
  109. if result is True:
  110. print("YES")
  111. else:
  112. print("NO")
  113. else:
  114. pass

5.时间复杂性分析与优化

这里先列出在上运算的复杂度以备参考

以下的算法复杂度分析是直接给出的,这种计算是基于比特位的数进行加减乘除运算是在时间内的。简单得讲,在两个系数最多比特位的阶多项式上进行以上运行能在步能完成。

引理 5.1 这个算法的渐进时间为
证明,算法的步骤1花费大约
算法的步骤2,我们要找到一个满足。这需要遍历测试每个(,其中)。对于一个特殊的,模的乘法最多花费因此这将花费。根据引理 4.3我们仅需要尝试次不同的。因此步骤2总共需要花费
第三个步骤计算个数的gcd。每个gcd需要花费,所以步骤3总共花费的步骤4仅需要花费
步骤5中,我们需要验证个等式。每个等式需要花费倍的系数的长度为阶多项式时间。因此每个等式能被在个时间步内被验证。因此步骤5的时间复杂度是。因此这个步骤占整个算法花费的绝大部分时间。
这个算法性能提高的关键字在于对的估计(引理 4.3)。当然最好的情况是当并且算法的复杂度在。事实上,有两个猜想猜测这样一个

Artin猜想:给定任意数非完全平方的,那么素数的数量对于是逐渐趋向于,这里Artin常数,

Sophie-Germain素数分布猜想:对于素数个数小于等于,那么仍然是一个素数并且渐进于,这里是孪生素数常量(估计接近)。具有这种属性的素数被称为Sophie-Germain素数。

Artin猜想-当时对于有效。在对Artin猜想的证明已经取得了一些进展[GM84,GMM85,HB86],这个猜想在一定条件的广义黎曼假设下成立是被承认的。
如果第二个猜想成立,我们应当断定:
根据Sophie-Germain素数分布,至少存在个素数在之间,其中是一个合适的常数。对于这样一个素数或者。任意对于每个都被整除,因此像这样的素数的数量上界是。这意味着必然存在一个素数以致。这样的一个将花费的时间复杂度。
对于这个猜想也取得了一些进展。设表示的最大素因子。[Gol69]说明了,其中是素数并且,同时具有正的密度。对于这个理论的进一步提高,Fouvry做了以下工作:
引理 5.2[Fou85] 存在常熟,对于所有的:


以上引理当指数大于时被证实[BH96]。使用以上引理我们可以提高我们的算法性能。
引理 5.3 这个算法的时间复杂度为
证明,通过以上的讨论,一个高密度的素数分布(是素数)意味着步骤2可以找到一个,其中。这将把这个算法的复杂度降低到
最近,Hendrik LenstraCarl Pomerance[LP03]提出了这个算法的修改版本并证明了算法的复杂度在

6.未来要做的事情

在我们的算法中,步骤5的循环需要运行次确保群的规模足够大。如果我们可以找到一个比集合产生的群更小的规模则这个迭代的次数可以被减少。
如果[BP01]提出的猜想被验证并且在范围内[KS02]被证实,则我们的算法复杂度可以在
猜想 如果是一个不能整除的素数,并且如果


那么是素数或者
如果这个猜想是正确的,我们可以修改我们的算法首先寻找一个不能整除的数。以致能在范围内。这是因为素数的积小于并且至少是([Apo97])。然后我们可以测试全等式成立或者不成立。验证这个全等式需要花费。这将有的时间复杂度。
近期,Hendrik LenstraCarl Pomerance[LP03b]提出一些参数表明以上猜想是错误的。但是,对于一些变量这个猜想仍然是正确的(例如,如果我们强行指定

感谢

作者感谢的一些话,这里就不翻译了。

参考资料

[AB03] M. Agrawal and S. Biswas. Primality and identity testing via Chinese remaindering. Jl. of the ACM, 50:429–443, 2003.

[AH92] L. M. Adleman and M.-D. Huang. Primality testing and two dimensional Abelian varieties over finite fields. Lecture Notes in Mathematics, 1512, 1992.

[AKS03] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. PRIMES is in P. Preprint
(http://www.cse.iitk.ac.in/news/primality v3.ps), February 2003.

[Apo97] T. M. Apostol. Introduction to Analytic Number Theory. Springer-Verlag, 1997.

[APR83] L. M. Adleman, C. Pomerance, and R. S. Rumely. On distinguishing prime numbers from
composite numbers. Ann. Math., 117:173–206, 1983.

[Atk86] A. O. L. Atkin. Lecture notes of a conference, boulder (colorado). Manuscript, August 1986.

[BH96] R. C. Baker and G. Harman. The Brun-Titchmarsh Theorem on average. In Proceedings of a conference in Honor of Heini Halberstam, Volume 1, pages 39–103, 1996.

[BP01] Rajat Bhattacharjee and Prashant Pandey. Primality testing. Technical report, IIT Kanpur,
2001. Available at http://www.cse.iitk.ac.in/research/btp2001/primality.html.

[Car10] R. D. Carmichael. Note on a number theory function. Bull. Amer. Math. Soc., 16:232–238,
1910.

[Fou85] E. Fouvry. Theoreme de Brun-Titchmarsh; application au theoreme de Fermat. Invent. Math.,
79:383–407, 1985.

[GK86] S. Goldwasser and J Kilian. Almost all primes can be quickly certified. In Proceedings of
Annual ACM Symposium on the Theory of Computing, pages 316–329, 1986.

[GM84] R. Gupta and M. Ram Murty. A remark on Artin’s conjecture. Inventiones Math., 78:127–130,
1984.

[GMM85] R. Gupta, V. Kumar Murty, and M. Ram Murty. The Euclidian algorithm for S integers. In
CMS Conference Proceedings, pages 189–202, 1985.

[Gol69] M. Goldfeld. On the number of primes p for which p+a has a large prime factor. Mathematika,
16:23–27, 1969.

[HB86] D. R. Heath-Brown. Artin’s conjecture for primitive roots. Quart. J. Math. Oxford, (2) 37:27–
38, 1986.

[KS02] Neeraj Kayal and Nitin Saxena. Towards a deterministic polynomialtime test. Technical report, IIT Kanpur, 2002. Available at
http://www.cse.iitk.ac.in/research/btp2002/primality.html.

[KSS02] Adam Kalai, Amit Sahai, and Madhu Sudan. Notes on primality test and analysis of AKS.
Private communication, August 2002.

[Lee90] J. V. Leeuwen, editor. Handbook of Theoretical Computer Science, Volume A. Elsevier, 1990.

[Len02] H. W. Lenstra, Jr. Primality testing with cyclotomic rings. Unpublished
(http://cr.yp.to/papers.html#aks has an exposition of Lenstra’s argument), August 2002.

[LN86] R. Lidl and H. Niederreiter. Introduction to finite fields and their applications. Cambridge
University Press, 1986.

[LP03a] H. W. Lenstra, Jr. and Carl Pomerance. Primality testing with gaussian periods. Private
communication, March 2003.

[LP03b] H. W. Lenstra, Jr. and Carl Pomerance. Remarks on Agrawal’s conjecture. Unpublished
(http://www.aimath.org/WWN/primesinp/articles/html/50a/), March 2003.

[Mac02] Martin Macaj. Some remarks and questions about the AKS algorithm and related conjecture.
Unpublished (http://thales.doa.fmph.uniba.sk/macaj/aksremarks.pdf), December 2002.

[Mil76] G. L. Miller. Riemann’s hypothesis and tests for primality. J. Comput. Sys. Sci., 13:300–317,
1976.

[Nai82] M. Nair. On Chebyshev-type inequalities for primes. Amer. Math. Monthly, 89:126–129, 1982.

[Pra75] V. Pratt. Every prime has a succinct certificate. SIAM Journal on Computing, 4:214–220,
1975.

[Rab80] M. O. Rabin. Probabilistic algorithm for testing primality. J. Number Theory, 12:128–138,
1980.

[SS77] R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM Journal on Computing, 6:84–86, 1977.

[vzGG99] Joachim von zur Gathen and J¨urgen Gerhard. Modern Computer Algebra. Cambridge University Press, 1999

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注