数学研发论坛

 找回密码
 欢迎注册
12
返回列表 发新帖
楼主: 无心人

[讨论] 关于伪素数与素性测试的一些事情

[复制链接]
 楼主| 发表于 2019-9-22 09:43:21 | 显示全部楼层
未完待续,不要插楼
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-27 15:08:33 | 显示全部楼层
素性测试从费马测试,到米勒罗宾测试,条件越来越严格,但是测试还是在\( \ZZ_n \)中进行
而Frobenius为代表的一些测试,则把测试扩展到了代数数域的二次域甚至三次域等
Jacobi和的严格素性证明,则用到了分圆域,其实本质也是代数数域,只不过,比二次域或者三次域更复杂了

椭圆曲线则显得比较另类,用到了椭圆曲线的知识

其实这个跟整数分解一样,一开始是连分数,然后是二次域,最后是一般代数域,同样也用到了椭圆曲线的方法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-28 09:53:55 | 显示全部楼层
继续刷楼
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2019-9-29 09:19:14 | 显示全部楼层
无心人 发表于 2019-9-22 09:43
基于Jacobi和的分圆域素性检验算法

我觉得你可真够无聊的,其实
baillie psw算法已经够好的了,
https://bbs.emath.ac.cn/forum.ph ... 776&fromuid=865
这儿有现成的代码!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-29 11:21:28 | 显示全部楼层
mathematica 发表于 2019-9-29 09:19
我觉得你可真够无聊的,其实
baillie psw算法已经够好的了,
https://bbs.emath.ac.cn/forum.php?mod=vie ...


你可能不知道BPSW的算法里,除了Miller-Rabin的另一个算法,是跟我说的Frobenius类似的算法,你觉得,对它的优化,值不值得去讨论?
你实现那个,是用F-L序列实现的,而对F-L改进的算法是我说的基于二次域的\(1+\sqrt{c}\) 的,实现起来简单多了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-10-1 09:47:07 | 显示全部楼层
无心人 发表于 2019-9-29 11:21
你可能不知道BPSW的算法里,除了Miller-Rabin的另一个算法,是跟我说的Frobenius类似的算法,你觉得, ...

你说的我不懂,但是我知道bpsw目前来说还没发现反例,真的很优秀!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-10-1 09:56:29 | 显示全部楼层
无心人 发表于 2019-9-29 11:21
你可能不知道BPSW的算法里,除了Miller-Rabin的另一个算法,是跟我说的Frobenius类似的算法,你觉得, ...

一个2为底的miller rabin+一个lucas动参数的测试,
两者联合起来都已经很难找到反例了,
如果多几个miller rabin测试+几个lucas动参数,更难找到反例。
两者的因数分解的模的形式不一样,所以壬就考虑联合起来,
但是没想到很难找到反例!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-10-6 10:14:25 | 显示全部楼层
mathematica 发表于 2019-10-1 09:56
一个2为底的miller rabin+一个lucas动参数的测试,
两者联合起来都已经很难找到反例了,
如果多几个mill ...


那个二次形式的Frobenius测试,就是你说的lucas在二次域的变形,原理是一样的,你可以看我给的wiki链接,但是,有个重要区别是,整数递归形式的测试,是存在很多伪素数例子的,而二次域的形式,10^8内我没找到伪素数,你可以说整数形式已经足够了,没有反例,但是这只是因为两个测试的伪素数没有发现叠加部分而已,而二次域形式的直接来自二次域的Fermat小定理,有论文分析过出现伪素数的可能,条件要远远的比整数上的fermat小定理的伪素数形式严格,甚至只要排除n是完全平方,二次域形式的Frobenius是可以独立做测试的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-10-7 09:46:53 | 显示全部楼层
素性测试的基于GMP的C源代码看大数分解程序YAFU的源代码
解压后
头文件在./include/mpz_prp_prime.h
源文件在./top/mpz_prp_prime.c
这是从头文件里扒下来的它实现的测试名字
  1. /* ******************************************************************
  2. * mpz_prp: (also called a Fermat pseudoprime)
  3. * A "pseudoprime" to the base a is a composite number n such that,
  4. * (a,n)=1 and a^(n-1) = 1 mod n
  5. * ******************************************************************/
  6. int mpz_prp(mpz_t n, mpz_t a);

  7. /* *************************************************************************
  8. * mpz_euler_prp: (also called a Solovay-Strassen pseudoprime)
  9. * An "Euler pseudoprime" to the base a is an odd composite number n with,
  10. * (a,n)=1 such that a^((n-1)/2)=(a/n) mod n [(a/n) is the Jacobi symbol]
  11. * *************************************************************************/
  12. int mpz_euler_prp(mpz_t n, mpz_t a);

  13. /* *********************************************************************************************
  14. * mpz_sprp: (also called a Miller-Rabin pseudoprime)
  15. * A "strong pseudoprime" to the base a is an odd composite n = (2^r)*s+1 with s odd such that
  16. * either a^s == 1 mod n, or a^((2^t)*s) == -1 mod n, for some integer t, with 0 <= t < r.
  17. * *********************************************************************************************/
  18. int mpz_sprp(mpz_t n, mpz_t a);

  19. /* *************************************************************************
  20. * mpz_fibonacci_prp:
  21. * A "Fibonacci pseudoprime" with parameters (P,Q), P > 0, Q=+/-1, is a
  22. * composite n for which V_n == P mod n
  23. * [V is the Lucas V sequence with parameters P,Q]
  24. * *************************************************************************/
  25. int mpz_fibonacci_prp(mpz_t n, long int p, long int q);

  26. /* *******************************************************************************
  27. * mpz_lucas_prp:
  28. * A "Lucas pseudoprime" with parameters (P,Q) is a composite n with D=P^2-4Q,
  29. * (n,2QD)=1 such that U_(n-(D/n)) == 0 mod n [(D/n) is the Jacobi symbol]
  30. * *******************************************************************************/
  31. int mpz_lucas_prp(mpz_t n, long int p, long int q);

  32. /* *********************************************************************************************
  33. * mpz_stronglucas_prp:
  34. * A "strong Lucas pseudoprime" with parameters (P,Q) is a composite n = (2^r)*s+(D/n), where
  35. * s is odd, D=P^2-4Q, and (n,2QD)=1 such that either U_s == 0 mod n or V_((2^t)*s) == 0 mod n
  36. * for some t, 0 <= t < r. [(D/n) is the Jacobi symbol]
  37. * *********************************************************************************************/
  38. int mpz_stronglucas_prp(mpz_t n, long int p, long int q);

  39. /* *******************************************************************************************
  40. * mpz_extrastronglucas_prp:
  41. * Let U_n = LucasU(p,1), V_n = LucasV(p,1), and D=p^2-4.
  42. * An "extra strong Lucas pseudoprime" to the base p is a composite n = (2^r)*s+(D/n), where
  43. * s is odd and (n,2D)=1, such that either U_s == 0 mod n or V_s == +/-2 mod n, or
  44. * V_((2^t)*s) == 0 mod n for some t with 0 <= t < r-1 [(D/n) is the Jacobi symbol]
  45. * *******************************************************************************************/
  46. int mpz_extrastronglucas_prp(mpz_t n, long int p);

  47. /* ***********************************************************************************************
  48. * mpz_selfridge_prp:
  49. * A "Lucas-Selfridge pseudoprime" n is a "Lucas pseudoprime" using Selfridge parameters of:
  50. * Find the first element D in the sequence {5, -7, 9, -11, 13, ...} such that Jacobi(D,n) = -1
  51. * Then use P=1 and Q=(1-D)/4 in the Lucas pseudoprime test.
  52. * Make sure n is not a perfect square, otherwise the search for D will only stop when D=n.
  53. * ***********************************************************************************************/
  54. int mpz_selfridge_prp(mpz_t n);

  55. /* *********************************************************************************************************
  56. * mpz_strongselfridge_prp:
  57. * A "strong Lucas-Selfridge pseudoprime" n is a "strong Lucas pseudoprime" using Selfridge parameters of:
  58. * Find the first element D in the sequence {5, -7, 9, -11, 13, ...} such that Jacobi(D,n) = -1
  59. * Then use P=1 and Q=(1-D)/4 in the strong Lucase pseudoprime test.
  60. * Make sure n is not a perfect square, otherwise the search for D will only stop when D=n.
  61. * **********************************************************************************************************/
  62. int mpz_strongselfridge_prp(mpz_t n);

  63. /* **********************************************************************************
  64. * mpz_bpsw_prp:
  65. * A "Baillie-Pomerance-Selfridge-Wagstaff pseudoprime" is a composite n such that
  66. * n is a strong pseudoprime to the base 2 and
  67. * n is a Lucas pseudoprime using the Selfridge parameters.
  68. * **********************************************************************************/
  69. int mpz_bpsw_prp(mpz_t n);

  70. /* ****************************************************************************************
  71. * mpz_strongbpsw_prp:
  72. * A "strong Baillie-Pomerance-Selfridge-Wagstaff pseudoprime" is a composite n such that
  73. * n is a strong pseudoprime to the base 2 and
  74. * n is a strong Lucas pseudoprime using the Selfridge parameters.
  75. * ****************************************************************************************/
  76. int mpz_strongbpsw_prp(mpz_t n);

  77. /* **********************************************************************************
  78. * APR-CL (also known as APRT-CLE) is a prime proving algorithm developed by:
  79. * L. Adleman, C. Pomerance, R. Rumely, H. Cohen, and A. K. Lenstra
  80. * APRT-CLE = Adleman-Pomerance-Rumely Test Cohen-Lenstra Extended version
  81. * You can find all the details of this implementation in the Cohen & Lenstra paper:
  82. *    H. Cohen and A. K. Lenstra, "Implementation of a new primality test",
  83. *    Math. Comp., 48 (1987) 103--121
  84. *
  85. * This C/GMP version is a conversion of Dario Alpern's Java based APRT-CLE code
  86. * His code was based on Yuji Kida's UBASIC code
  87. *
  88. * Based on APRT-CLE Written by Dario Alejandro Alpern (Buenos Aires - Argentina)
  89. * From: Last updated September 10th, 2011. See http://www.alpertron.com.ar/ECM.HTM
  90. *
  91. * With improvements based on Jason Moxham's APRCL v1.15 code, from 2003/01/01
  92. * *********************************************************************************/

  93. int mpz_aprcl(mpz_t N);
  94. int mpz_aprtcle(mpz_t N, int verbose);
复制代码

yafu-1.34-src.zip

670.56 KB, 下载次数: 0, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-10-9 09:36:01 | 显示全部楼层
无心人 发表于 2019-10-7 09:46
素性测试的基于GMP的C源代码看大数分解程序YAFU的源代码
解压后
头文件在./include/mpz_prp_prime.h

在我看来,baillie psw算法足够了,不自信的话,就再加几个miller随机的测试,不纠结!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-7-11 05:55 , Processed in 0.156912 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表