借题，问一下，可有此类算法：可快速判定一个大整数，有/无 含非 1 的平方因子？
不知道你为什么会死磕这个问题，
Rabin-Miller 强伪素数可能含平方因子吗？
https://bbs.emath.ac.cn/thread-3710-1-1.html
我在下面已经回复你了
https://oeis.org/A001220
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 = 0
for k = 0 to 5
q11 = 1
for k = 0 to 62
q63 = 0
for k = 0 to 31
q63 = 1
for k = 0 to 63
q64 = 0
for k = 0 to 31
q64 = 1
for k = 0 to 64
q65 = 0
for k = 0 to 32
q65 = 1
2、测试
1)、t = n mod 64
if q64 = 0 return n not square number, terminate
r = n mod 45045
2)、if q63 = 0 return n not square number, terminate
3)、if q65 = 0 return n not square number, terminate
4)、if q11 = 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
function isSquareOrDivBy2357(n)
if gcd(n, 840) != 1
return true
end
t = n % 840
if t in
sq = isqrt(n)
return sq * sq == n
else
return false
end
end
function isSquare1(n)
sq = isqrt(n)
return sq * sq == n
end
q11 =
q63 =[1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0,
1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1,
0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0]
q64 =[1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0]
q65 =[1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1,
0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0,
0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0,
0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0,
1, 1, 0, 0, 0, 0, 1, 0, 0, 1]
function isSquare2(n)
if q64 == 0
return false
end
r = n % 45045
if q63 == 0
return false
end
if q65 == 0
return false
end
if q11 == 0
return false
end
sq = isqrt(n)
return sq * sq == n
end
base = big(10)^16384
test = []
for i in range(0, stop = 65535)
push!(test, base + i)
end
global cnt = 0
println("1")
@time for t in test
if isSquareOrDivBy2357(t)
global cnt += 1
end
end
println(cnt)
global cnt = 0
println("2")
@time for t in test
if isSquare1(t)
global cnt += 1
end
end
println(cnt)
global cnt = 0
println("3")
@time for t in test
if isSquare2(t)
global cnt += 1
end
end
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的平方测试算法 无心人 发表于 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 \)
页:
1
[2]