数学研发论坛

 找回密码
 欢迎注册
查看: 460|回复: 19

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

[复制链接]
发表于 2019-9-22 08:49:12 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
如果奇合数\( q \)满足费马素性测试 \( b^{(q-1)/2} \equiv \pm1  \mod q\) 称为以b为基的Fermat伪素数(Fermat pseudoprime),以下简称fpsp(b)

更进一步,如果奇合数\( q \),\( q - 1 = 2^k m, m\)为奇数,且
满足下面两个条件之一 ,(米勒罗宾测试)
1、\( b^{m} \equiv \pm1  \mod q\)
2、\( b^{2^im} \equiv \pm1  \mod q, i < k\)
称为以b为基的强伪素数(strong pseudoprime),以下简称spsp(b)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:02:35 | 显示全部楼层
有用的几个性质
1、若n是fpsp(b),则gcd(n, b)=1
2、spsp(b)必然是fpsp(b)
3、如果n同时是是fpsp(b1), fpsp(b2)那么n必然是fpsp(b1b2) ,反之则不成立,比如最小的fpsp(6)是35,而35既不是fpsp(2),也不是fpsp(3)
4、存在一类整数C,是所有满足gcd(C, x)=1的fpsp(x),即卡米切尔数(Carmichael number )
5、n以内卡米切尔数大于\( n^{2/7 }\)
6、spsp(b)要比fpsp(b)少的多,很多卡米切尔数是fpsp(b),但不是spsp(b)
7、简单的计算可以发现一个事实,n以内的卡米切尔数,spsp(b), fpsp(b),数量依次递增

有人证明n以内卡米切尔数个数\( C(n)  > n^{0.332} \),计算表明10^15的卡米切尔数有105212个,所以,\( C(n) > \sqrt[3]{n} , n >= 10^{15}\) ?
我猜想,n以内spsp(b)数量大于 \( \sqrt[3]{n} \),而小于 \( \sqrt{n} \)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:29:31 | 显示全部楼层
GMP里的素性测试用了高度复合数210,原理未知

理论计算表明如果n是奇数,通过一次米勒罗宾测试是合数的概率是1/4,费马素性测试合数的概率是1/2
2^64内的实际计算表明,真实概率远小于这个,总体上,通过费马素性测试的合数多于米勒罗宾测试,
所以实践中采用多次米勒罗宾测试来减少出错可能

实践计算表明,spsp(2)数量要少于spsp(b), b > 2,一般一次测试采用b=2
同样,因为合数b并不能减少米勒罗宾测试出错概率,所以我倾向于采用素数的基b的米勒罗宾测试,即用b=2,3,5,7....

用ψn表示通过前n个素数的强伪素数测试的最小合数,则:
ψ1 =  2047 = 23 * 89
ψ2 =  1373653 = 829 * 1657
ψ3 =  25326001 = 2251 * 11251
ψ4 =  32150 31751 = 151 * 751 * 28351
ψ5 =  215 23028 98747 = 6763 * 10627 * 29947
ψ6 =  347 47496 60383 = 1303 * 16927 * 157543
ψ7 = ψ8 =  34155 00717 28321 = 10670053 * 32010157
ψ9 = ψ10 = ψ11 =  3825 12305 65464 13051 = 149491 * 747451 * 34233211

实践中,也可以采取随机整数基测试

如果n是大整数,二进制有k位,一次米勒罗宾测试出错的实际概率 \( < k^2*4^{2−\sqrt{k}} \)   (Damg˚ard et al. 1993)
实际上k = 500, 概率小于 \( 4^{-28} \),当然我猜想,应该小于\( 4^{-125} \),即2-4次就足够坚信n是素数了(张振祥建议次数用6次)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:42:52 | 显示全部楼层
Julia实现Fermat素性测试源代码

  1. function fermatProbablePrimeTest(n, b)
  2.     if gcd(n, b) > 1
  3.         return false
  4.     end
  5.     a = powermod(b, (n-1)>>1, n)
  6.     return (a == 1) || (a == (n-1))
  7. end

  8. println("341 test: ", fermatProbablePrimeTest(341, 2))
  9. println("561 test: ", fermatProbablePrimeTest(561, 2))
  10. println("2047 test: ", fermatProbablePrimeTest(2047, 2))
  11. println("I17 test: ", fermatProbablePrimeTest(11111111111111111, 2))
  12. println("I19 test: ", fermatProbablePrimeTest(1111111111111111111, 2))
  13. println("2^31-1 test: ", fermatProbablePrimeTest(2^31-1, 2))
  14. println("2^67-1 test: ", fermatProbablePrimeTest(2^67-1, 2))
复制代码


341 test: true
561 test: true
2047 test: true
I17 test: false
I19 test: true
2^31-1 test: true
2^67-1 test: false
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:42:54 | 显示全部楼层
Julia实现Miller Rabin强素性测试源代码

  1. function millerRabinProbablePrimeTest( n, b )
  2.     #n - 1 = 2^k * m, m % 2 != 0
  3.     k = trailing_zeros(n-1)
  4.     m = (n-1) >> k
  5.     a = powermod(b, m, n)
  6.     if (a == 1) || (a == (n-1))
  7.         return true
  8.     else
  9.         for i in 1:k-1
  10.             a = powermod(a, 2, n)
  11.             if a == n - 1
  12.                 return true
  13.             end
  14.         end
  15.     end
  16.     return false
  17. end

  18. println("====================")
  19. println("Miller Rabin Probable Prime Test")
  20. println("341 test: ", millerRabinProbablePrimeTest(341, 2))
  21. println("561 test: ", millerRabinProbablePrimeTest(561, 2))
  22. println("2047 test: ", millerRabinProbablePrimeTest(2047, 2))
  23. println("I17 test: ", millerRabinProbablePrimeTest(11111111111111111, 2))
  24. println("I19 test: ", millerRabinProbablePrimeTest(1111111111111111111, 2))
  25. println("2^31-1 test: ", millerRabinProbablePrimeTest(2^31-1, 2))
  26. println("2^67-1 test: ", millerRabinProbablePrimeTest(2^67-1, 2))
  27. println("====================")
复制代码



====================
Miller Rabin Probable Prime Test
341 test: false
561 test: false
2047 test: true
I17 test: false
I19 test: true
2^31-1 test: true
2^67-1 test: false
====================


julia> millerRabinProbablePrimeTest(big(2)^607-1, 2)
true

julia> millerRabinProbablePrimeTest(big(2)^9941-1, 2)
true

julia> millerRabinProbablePrimeTest(big(2)^9947-1, 2)
false

@time millerRabinProbablePrimeTest(big(2)^21701-1, 2)
  1.604359 seconds (1.97 k allocations: 809.485 KiB)
true

@time millerRabinProbablePrimeTest(big(2)^132049-1, 2)
128.894809 seconds (1.60 M allocations: 24.091 GiB, 0.56% gc time)
true
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:42:58 | 显示全部楼层
Frobenius素性测试,

有用广义斐波那契卢卡斯序列描述的,但是我更倾向于用二次域描述的算法,更简洁
/*
备注下,BPSW用的是递归序列形式的测试,参考
1、https://en.wikipedia.org/wiki/Frobenius_pseudoprime
2、https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test
是有很多伪素数的,
而这里的二次域形式的根据网页1提供的线索,伪素数出现可能极低,至少wiki并没有列出来
如果有,在n小于2^60情况下,至少有个低于20的素因子或者c>128(c很大的可能很低很低)
*/


定义二次域,\( \ZZ(\sqrt{c}) \) 上面的整数 \( a + b \sqrt{c}  \), 其中 \(a, b, c \in \ZZ \)
且Jacobi符号\( (\frac{c}{n}) = -1 \)
/*要求n不是完全平方数*/

第一种形式是,
\( (1 + \sqrt{c})^n \equiv 1 - \sqrt{c}  \mod n \)

第二种形式是,
\( (a + b\sqrt{c})^n \equiv a - b\sqrt{c}  \mod n \)

第一种形式,是第二种形式,a, b都等于1的特例
如果n是素数,则两种形式都成立,如果n是合数,能使恒等式成立的是Frobenius伪素数,简称FPP

第一种形式,10^8内没发现伪素数,经过了双向验证,
Frobenius验证通过的,测试是不是非素数,没有发现,
常规素性测试通过的,测试是不是Frobenius验证为非素数,没有发现

2019-10-7,暴力遍历了所有\(2^{64}\)以内的基2强伪素数,除了\( 1093^2, 3511^2\)这两个会导致测试死循环外,其他都通过测试,确认非素数
2019-10-9,测试代码里更新了,如果满足Jacobi Symbol (p, n) = -1的最小奇素数p大于137,就检测n是不是完全平方数,如果是,就直接返回非素数,
测试表明,大多数非完全平方数,满足Jacobi Symbol (p, n) = -1的最小奇素数p小于60,大于60的比例很低



  1. using Primes

  2. struct Quadratic{T <: Integer, C} <: Integer
  3.    re::T
  4.    ir::T
  5. end

  6. function qfmul(left:: Quadratic{T, C}, right:: Quadratic{T, C}) where {T <: Integer, C}
  7.     re = left.re * right.re + left.ir * right.ir * C
  8.     ir = left.re * right.ir + left.ir * right.re
  9.     return Quadratic{T, C}(re, ir)
  10. end

  11. function qfmod(left:: Quadratic{T, C}, r:: T) where {T <: Integer, C}
  12.     re = left.re % r
  13.     ir = left.ir % r
  14.     return Quadratic{T, C}(re, ir)
  15. end

  16. function qfmulmod(left:: Quadratic{T, C}, right:: Quadratic{T, C}, r::T) where {T <: Integer, C}
  17.     re = (left.re * right.re + left.ir * right.ir * C) % r
  18.     ir = (left.re * right.ir + left.ir * right.re) % r
  19.     return Quadratic{T, C}(re, ir)
  20. end

  21. function qfpowermod(x::Quadratic{T, C}, p::T , m::T) where {T <: Integer, C}
  22.     @assert p >= 0
  23.     p == 0 && return Quadratic{T, C}(1, 0)
  24.     #b = oftype(m,mod(x,m))  # this also checks for divide by zero
  25.     b = x
  26.     t = prevpow(2, p)
  27.     r = Quadratic{T, C}(1, 0)
  28.     while true
  29.         if p >= t
  30.             r = qfmulmod(r, b, m)
  31.             p -= t
  32.         end
  33.         t >>>= 1
  34.         t <= 0 && break
  35.         r = qfmulmod(r, r ,m)
  36.     end
  37.     return r
  38. end

  39. function jacobi(a, b)
  40.     tab2 = [0, 1, 0, -1, 0, -1, 0, 1]
  41.     if b == 0
  42.         if abs(a)==1
  43.             return 1
  44.         else
  45.             return 0
  46.         end
  47.     end
  48.     if iseven(a) && iseven(b)
  49.         return 0
  50.     end
  51.     v = trailing_zeros(b)
  52.     b = b >> v
  53.     if iseven(v)
  54.         k = 1
  55.     else
  56.         k = tab2[a & 7 + 1]
  57.     end
  58.     if b < 0
  59.         b = -b
  60.     end
  61.     if a < 0
  62.         k = -k
  63.     end
  64.     while a != 0
  65.         v = trailing_zeros(a)
  66.         a = a >> v
  67.         if isodd(v)
  68.             k *= tab2[b & 7 + 1]
  69.         end
  70.         if a & b & 3 == 3
  71.             k = -k
  72.         end
  73.         r = abs(a)
  74.         a = b % r
  75.         b = r
  76.     end
  77.     if b > 1
  78.         return 0
  79.     else
  80.         return k
  81.     end
  82. end

  83. function frobenius(n)
  84.     small = [
  85.                3,   5,  7, 11, 13, 17, 19, 23,
  86.               29,  31, 37,  41, 43, 47, 53, 59,
  87.               61,  67, 71, 73, 79, 83, 89, 97,
  88.               101,103,107,109,113,127,131,137
  89.             ]
  90.     find = false
  91.     global p = 0
  92.     for c in small
  93.         if jacobi(c, n) == -1
  94.             find = true
  95.             global p = c
  96.             break
  97.         end
  98.     end
  99.     if !find
  100.         #n is prefect square number?
  101.         sq = isqrt(n)
  102.         if sq * sq == n
  103.                 return false
  104.         end
  105.         c = Primes.nextprime(last(small)+1)
  106.         while jacobi(c, n) != -1
  107.             c = Primes.nextprime(c+1)
  108.         end
  109.         global p = c
  110.     end
  111.     #println("$n: $p")
  112.     b = Quadratic{typeof(n), p}(1, 1)
  113.     r = qfpowermod(b, n, n)
  114.     return (r.re == 1) && (r.ir == n - 1)
  115. end

  116. global t = 0
  117. global b = big(10)^67
  118. @time for i in range(3, step = 2, stop = 999999)
  119.     test = b + i
  120.     if isqrt(test)^2 == test
  121.         continue
  122.     end

  123.     if isprime(test)
  124.         if !frobenius(test)
  125.             println("frobenius error at $test")
  126.         end
  127.         global t += 1
  128.         if t % 1000000 == 0
  129.             println(t)
  130.         end
  131.     end
  132. end
  133. println("end")
复制代码


详细的理论分析见附件论文

Counterexamples for Frobenius primality test.pdf

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:43:03 | 显示全部楼层
Extended Quadratic Frobenius Primality Test
扩展的二次域Frobenius素性检测算法,简称EQFT

定义环\(\RR(n, c) = \ZZ(x)/(n, x^2-c)\)
环上的整数\(z=ax+b, a, b \in \ZZ_n, \overline{z}=-ax+b, N(z)=\overline{z} \bullet z=b^2-ca^2\)

算法1,Extended Quadratic Frobenius Test (EQFTac)
前置测试:
输入,奇数\(n\geq5\)
1: 如果n被不大于13素数整除,返回n是合数
2: 如果n是完全平方数,返回n是合数
3: 找到最小的c,jacobi符号\((\frac{c}{n})=-1\),输出c
第二部分测试:
输入\(n, c, r_3 \in \{1\} \cup \{\xi \in R(n, c) | \phi_3(\xi)=0\}, r_4 \in \{1, -1\} \cup \{\xi \in R(n, c) | \phi_4(\xi)=0\}\)   
其中\(\phi_3(x)=x^2+x+1, \phi_4(x)=x^2+1 \)
\(u, v\)满足\(n^2-1=2^u3^vq, (q, 6)=1\)
4、随机选择\(z \in R(n,c)^*\)满足\((\frac{N(z)}{n})=1\)
5、如果\(z^n \neq \overline{z}\)或者\( z^{(n^2-1)/2} \neq 1\),返回n是合数
6、如果\( z^{3^vq} \neq 1 \)并且\( z^{2^i3^vq} \neq -1 \) 对所有\(i = 0, ..., u-2\),返回n是合数
7、如果6找到的\(i_0 \geq 1\), 满足 \( z^{2^{i_0}3^vq}=-1 \) (最多只能有一个值)
    令\(R_4(z)=z^{2^{i_0 - 1}3^vq} \)否则,令\( R_4(z)=z^{3^vq}(=\pm 1) \)
    如果\( r_4 \neq \pm 1 \)并且\( R_4(z)  \notin \{\pm 1, \pm r_4 \} \) ,返回n是合数
8、如果\( z^{2^uq} \neq 1 \)并且\( \phi_3(z^{2^u3^iq}) \neq 0 \) 对所有\(i = 0, ..., v-1\), 返回n是合数
9、如果8找到的\(i_0 \geq 1\), 满足 \( \phi_3(z^{2^u3^{i_0}q}) = 0 \) ,  (最多只能有一个值)
    令\(R_3(z)=z^{2^u3^{i_0}q} \),否则,令\( R_3(z)= 1 \)
    如果\( r_3 \neq 1 \)并且\( R_3(z)  \notin \{1, r_3^{\pm 1} \} \) ,返回n是合数
10、如果\( r_3 = 1 \) 并且 \( R_3(z) \neq 1 \)
      则令 \( s_3 = R_3(z) \) 否则 \( s_3 = r_3 \)
     如果 \( r_4 = \pm 1 \) 并且 \( R_4(z) \neq \pm 1 \)
      则令  \( s_4 = R_4(z) \) 否则 \( s_4 = r_4 \)
     返回n可能是素数,和\( s_3, s_4 \)

算法2,Extended Quadratic Frobenius Test (EQFTwc)
输入,奇数\( n \geq 5\)
输出, n是合数或者可能素数, \( c \in \ZZ_n, r_{24} \in R(n, c)^*, (\frac{c}{n}) = -1, \phi_{24}(r_{24}) = 0 \)
1、如果,n能被2,3整除,返回n是合数
2、如果,n是完全平方数,或者完全立方数,返回n是合数
3、找到小c,满足\( (\frac{c}{n}) = -1 \)
4、计算, \( r \in R(n, c) \)满足\( r^2 + r + 1 = 0 \), 可能返回n是合数
5、a:  如果 \( n \mod 3 \equiv 1 \) 随机选择 \( z \in R(n, c)^* \) 且 \( (\frac{N(z)}{n}) = -1, res_3(z) \neq 1 \)
     b:  否则 \( n \mod 3 \equiv 2 \)
               重复
                      做 Miller-Rabbin 测试,可能返回n是合数
                      随机选择 \( z \in R(n, c)^* \) 满足 \( (\frac{N(z)}{n}) = -1 \) 计算 \( res_3(z) \)
               直到,或者  Miller-Rabbin返回n是合数,或者找到\( z \)满足 \( res_3(z) \neq 1 \)
6、如果 \( z^n \neq \overline{z} \) 返回n是合数
7、令 \( r_{24} = z^{(n^2-1)/24}\) 如果 \( r_{24}^8 \neq r^{\pm 1} \) 或者 \( r_{24}^{12} \neq - 1 \)返回n是合数
8、返回n是可能素数,\(c, r_{24} \)

子序列迭代
输入 \( n, c, r_{24} \) 满足条件如上
9、随机选择\( z \in R(n, c)^* \)
10、如果 \( z^n \neq \overline{z} \) 返回n是合数
11、如果 \( z^{(n^2-1)/24} \notin \{ r_{24}^i | i = 0, ...., 23 \}\)返回n是合数
12、返回,n是可能素数

这个翻译的比较崩溃,说实话,有点看不懂加迷惑,好在下面的算法要比这个优秀,完全可以实现出来,这个就不实现了
原版论文已上传,有问题的看论文吧

BRICS-RS-03-9.pdf

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:43:06 | 显示全部楼层
EQFT的简化实现在附件的论文里,
称为\(Simplified \: Quadratic \: Frobenius \: test\),简称\(SQFT\)

一、前置算法 \(MR2 (Miller-Rabin \: test \: with \: basis \: two \: or \: a \: small \: nonresidue)\)
输入: 奇数\(n\)
输出: \(n\)为合数,或者
           \( c, (\frac{c}{n}) = -1,\epsilon \in R(n, c),  \epsilon^4 = -1,  \phi_8(\epsilon) = 0 \)
1、\( n \mod 4 = 3 \)
                计算 \( \alpha = 2^{(n-3)/4}  (\mod n) \)
                如果\( 2\alpha^2 \neq \pm 1  (\mod n) \) 输出\(n\)是合数
                否则,输出\(c = -1, \epsilon = \alpha + \alpha x \)
2、\( n \mod 8 = 5 \)
                计算 \( \alpha = 2^{(n-1)/4}  (\mod n) \)
                如果\( \alpha^2 \neq - 1  (\mod n) \) 输出\(n\)是合数
                否则,输出\(c = 2, \epsilon = \frac{1 + \alpha}{2} x \)
3、\( n \mod 8 = 1 \)
                如果\(n\)是完全平方数,输出\(n\)是合数
                否则找到小的\(c\)满足\( (\frac{c}{n}) = - 1 \) //c从3开始
                计算 \( \alpha = c^{(n-1)/8}  (\mod n) \)
                如果\( \alpha^4 \neq - 1  (\mod n) \) 输出\(n\)是合数
                否则,输出\(c = -1, \epsilon = \alpha \)

二、SQFT循环 \(SQFT_{round}\)
输入: 奇数\(n\),\( c, (\frac{c}{n}) = -1,\epsilon \in R(n, c),  \epsilon^4 = -1,  \phi_8(\epsilon) = 0 \)
输出:\(n\)是合数或者可能是素数
1、随机选择\( z \in R(n, c) \)满足\( (\frac{N(z)}{n}) = -1 \)
2、如果\( z^n \neq \overline{z} \) 输出\(n\)是合数
3、如果\( z^{(n^2-1)/8} \notin \{ \pm \epsilon, \pm \epsilon^3 \} \) 输出\(n\)是合数
4、输出\(n\)可能是素数

三、SQFT测试 \(SQFT: (Simplified \: Quadratic \: Frobenius \: test) \)
输入: \(n, n > 20 \), 测试次数\(t\)
输出:\(n\)是合数或者可能是素数
1、如果\(n\)被小于\(20\)素数整除,输出\(n\)是合数
2、调用算法\(MR2\)
3、如果\(n\)没被判定为合数,则\(MR2\)输出\(c, \epsilon \)
4、重复\(t\)次:
        用\(n, c, \epsilon \)调用算法\( SQFT_{round} \),如果算法判定\(n\)是合数,则终止
5、输出\(n\)可能是素数
       
附加三次根测试的\(SQFT3\)算法
四、SQFT3循环 \( SQFT3_{round} \)
输入:整数\( n, gcd(n, 6) = 1 \), 小整数\( c, (\frac{c}{n} ) = -1 \),
          值\( \epsilon, \epsilon^4 = -1 \)和\( \epsilon_3 \)满足   \( \epsilon_3  =1 \) 或者 \( \phi_3(\epsilon_3) = 0\),   

输出:\( n \)是合数,或者是可能的素数,同时输出下面的值
         \( {\epsilon'}_3 \), 满足   \( {\epsilon'}_3  =1 \) 或者 \( \phi_3({\epsilon'}_3) = 0\),   
         如果, \( \epsilon_3 \neq 1\),那么  \({\epsilon'}_3  = \epsilon_3^{\pm 1} \)
1、随机选择\( z \in R(n, c) \)满足\( (\frac{N(z)}{n}) = -1 \)
2、如果\( z^n \neq \overline{z} \) 输出\(n\)是合数
3、如果\( z^{(n^2-1)/8} \notin \{ \pm \epsilon, \pm \epsilon^3 \} \) 输出\(n\)是合数
4、置\( u = v_3(n^2 - 1), n^2 - 1 = 3^u r \)  //这里的\(v_3\)看不出什么意思来~
5、令\( i = \min\{ j: 0 \leq j \leq u, z^{3^j r} = 1 \} \)
6、如果\( i = 0\),输出\(n\)可能是素数,\( {\epsilon'}_3 = \epsilon_3 \)
7、置\( {\epsilon'}_3 = z^{3^{i-1}r}  \)
8、如果\( \epsilon_3 = 1 \) 且 \( \phi_3({\epsilon'}_3) \neq 0 \),输出n是合数
9、如果\( \epsilon_3 \neq 1 \) 且\( {\epsilon'}_3 \neq \epsilon_3^{\pm 1} \),输出n是合数
10、输出\(n\)可能是素数和 \({\epsilon'}_3\)

五、SQFT3测试 \( SQFT3 \)
输入: \(n, n > 200 \), 测试次数\(t\)
输出:\(n\)是合数或者可能是素数
1、如果 \(n\)被小于\(200\)素数整除,输出\(n\) 是合数
2、调用\(MR2\),如果判定 \(n\)是合数,结束
3、从\(MR2\)获得输出的\( c, \epsilon \),并且置 \( \epsilon_3 = 1 \)
4、循环\(t\)次
        用\( n, c, \epsilon, \epsilon_3 \)调用\( SQFT3_{round} \)
        如果\( SQFT3_{round} \)判定\(n\)是合数,结束
        置\( \epsilon_3 = {\epsilon'}_3 \),这里  \( {\epsilon'}_3 \)是算法\( SQFT3_{round} \)的输出
5、输出\(n\)可能是素数

乘法实现:
\(w, z \in R(n, c), w = A_wx + B_w, z = A_zx + B_z \)
\(z · w = (m_1 + m_2)x + (cA_z + B_z)(A_w + B_w) − cm_1 − m_2 \)
\( m_1 = A_zB_w , m_2 = B_zA_w \)

ASimpleFrobeniusPrimalityTest.pdf

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:43:15 | 显示全部楼层
椭圆曲线素性检验算法ECPP
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-9-22 09:43:17 | 显示全部楼层
基于Jacobi和的分圆域素性检验算法

Primality Testing and Jacobi Sums.zip

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

Primality Testing and Jacobi Sums.z02

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

Primality Testing and Jacobi Sums.z01

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-10-19 17:10 , Processed in 0.126004 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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