素性测试中的平方数判定问题

mathematica

gxqcn 发表于 2019-10-8 17:12
借题，问一下，可有此类算法：可快速判定一个大整数，有/无 含非 1 的平方因子？

不知道你为什么会死磕这个问题，

Rabin-Miller 强伪素数可能含平方因子吗？
https://bbs.emath.ac.cn/thread-3710-1-1.html

我在下面已经回复你了

https://oeis.org/A001220

mathematica

gxqcn 发表于 2019-10-8 17:12
借题，问一下，可有此类算法：可快速判定一个大整数，有/无 含非 1 的平方因子？

不要死磕任何数论问题，很难的，
你就测试一下1093 3511这两个数就可以了
计算一下与1093*3511=3837523的最大公约数是否等于1

无心人

mathematica 发表于 2019-10-9 09:34
不要死磕任何数论问题，很难的，
你就测试一下1093 3511这两个数就可以了
计算一下与1093*3511=3837523 ...

数学上并没有证明除了这两个数，没有其他例子
另外，Frobenius测试只需要不是平方数，含平方因子的没问题

无心人

贴个从Henri Cohen的A Course in Computational Algebraic Number Theory扒下来的平方数检测算法
1、预计算表
for k = 0 to 10
    q11[k] = 0
for k = 0 to 5
    q11[k^2 mod 11] = 1

for k = 0 to 62
    q63[k] = 0
for k = 0 to 31
    q63[k^2 mod 63] = 1

for k = 0 to 63
    q64[k] = 0
for k = 0 to 31
    q64[k^2 mod 64] = 1

for k = 0 to 64
    q65[k] = 0
for k = 0 to 32
    q65[k^2 mod 65] = 1

2、测试
1)、t = n mod 64
    if q64[t] = 0 return n not square number, terminate
    r = n mod 45045
2)、if q63[r mod 63] = 0 return n not square number, terminate
3)、if q65[r mod 65] = 0 return n not square number, terminate
4)、if q11[r mod 11] = 0 return n not square number, terminate
5)、q = sqrt(n), if q^2 != n return n not square number, terminate
return n is square number

无心人

1. 
   
2. function isSquareOrDivBy2357(n)
   
3.     if gcd(n, 840) != 1
   
4.         return true
   
5.     end
   
6.     t = n % 840
   
7.     if t in [1, 121, 169, 289, 361, 529]
   
8.         sq = isqrt(n)
   
9.         return sq * sq == n
   
10.     else
    
11.         return false
    
12.     end
    
13. end
    
14. 
    
15. function isSquare1(n)
    
16.     sq = isqrt(n)
    
17.     return sq * sq == n
    
18. end
    
19. 
    
20. q11 =  [1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0]
    
21. q63 =  [1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0,
    
22.         0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0,
    
23.         1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0,
    
24.         0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1,
    
25.         0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
    
26.         0, 0, 0, 1, 0, 0, 0, 0]
    
27. q64 =  [1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0,
    
28.         0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
    
29.         0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
    
30.         1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
    
31.         0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
    
32.         0, 0, 1, 0, 0, 0, 0, 0, 0]
    
33. q65 =  [1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1,
    
34.         0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
    
35.         0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0,
    
36.         0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0,
    
37.         0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0,
    
38.         1, 1, 0, 0, 0, 0, 1, 0, 0, 1]
    
39. 
    
40. function isSquare2(n)
    
41.     if q64[n % 64 + 1] == 0
    
42.         return false
    
43.     end
    
44.     r = n % 45045
    
45.     if q63[r % 63 + 1] == 0
    
46.         return false
    
47.     end
    
48.     if q65[r % 65 + 1] == 0
    
49.         return false
    
50.     end
    
51.     if q11[r % 11 + 1] == 0
    
52.         return false
    
53.     end
    
54.     sq = isqrt(n)
    
55.     return sq * sq == n
    
56. end
    
57. 
    
58. base = big(10)^16384
    
59. test = []
    
60. for i in range(0, stop = 65535)
    
61.     push!(test, base + i)
    
62. end
    
63. 
    
64. global cnt = 0
    
65. println("1")
    
66. @time for t in test
    
67.     if isSquareOrDivBy2357(t)
    
68.         global cnt += 1
    
69.     end
    
70. end
    
71. println(cnt)
    
72. 
    
73. global cnt = 0
    
74. println("2")
    
75. @time for t in test
    
76.     if isSquare1(t)
    
77.         global cnt += 1
    
78.     end
    
79. end
    
80. println(cnt)
    
81. 
    
82. global cnt = 0
    
83. println("3")
    
84. @time for t in test
    
85.     if isSquare2(t)
    
86.         global cnt += 1
    
87.     end
    
88. end
    
89. println(cnt)
    

复制代码

1
  0.361999 seconds (1.33 M allocations: 33.778 MiB, 10.00% gc time)
50556

2
  6.500475 seconds (590.98 k allocations: 647.587 MiB, 1.93% gc time)
1

3
  0.529858 seconds (1.51 M allocations: 41.500 MiB, 5.29% gc time)
1
测试表明当待测试数较小时，直接开平方的时间最少，Cohen的方法最差
当待测试数字很大时候（大约大于10^1024），我提到的方法较好，但是不能反应实际的平方数，Cohen的其次，直接开平方则较差
所以推荐Cohen的平方测试算法

mathematica

无心人 发表于 2019-10-9 11:10
数学上并没有证明除了这两个数，没有其他例子
另外，Frobenius测试只需要不是平方数，含平方因子的没 ...

难道你的Frobenius测试就能排除所有的合数？

无心人

mathematica 发表于 2019-10-11 14:53
难道你的Frobenius测试就能排除所有的合数？

欢迎你找到反例
你就用简单形式找到就行：
\(  (1+\sqrt{c})^n \equiv (1 - \sqrt{c})  \mod n, (\frac{c}{n}) = -1 \)