BPSW和QFT素性检验算法执行时间比较

nyy

即使是以2位底的强伪素数，也有633.1M吗？还是太大了！

nyy

老外真是闲的没事干，居然2^64以下的伪素数都找出来，计算资源可真多，就是不知道他们素数判定算法怎么搞的（在找2^64以下的伪素数的时候）

nyy

国外有开源的大整数算法库，比hugecalc还要快很多！我要是没试过，我都不敢相信。

nyy

无心人 发表于 2023-5-4 10:47
同样增加一次基3强伪素数测试的BPSW

1次SLPSP测试约等于3.8次SPSP测试

用SLPSP的优点是可以进行lucas U+Lucas V+一次半强伪素数

具体见下面的代码！
https://bbs.emath.ac.cn/forum.ph ... 3&fromuid=14149

我都是开源的，但是我不敢说“原创”

无心人

nyy 发表于 2023-5-15 13:20
用SLPSP的优点是可以进行lucas U+Lucas V+一次半强伪素数

具体见下面的代码！

另外，二次域Frobenius测试和Lucas序列测试，虽然都是基于二次型，但是重要区别是即使最弱形式，二次域Frobenius测试，只要保证选择的参数 z 不是某个形如 a + bi 的复整数（a, b都是整数，且其中一个是0）的平方根，就不存在伪素数

nyy

无心人 发表于 2023-5-17 17:03
另外，二次域Frobenius测试和Lucas序列测试，虽然都是基于二次型，但是重要区别是即使最弱形式，二次域Fr ...

原创？？？？

nyy

无心人 发表于 2023-5-17 17:03
另外，二次域Frobenius测试和Lucas序列测试，虽然都是基于二次型，但是重要区别是即使最弱形式，二次域Fr ...

你选择lucas测试的参数与BPSW不同

BPSW算法，就是指miller rabin（n-1）+lucas（n+1），与参数选择没多大关系！

nyy

无心人 发表于 2023-5-17 17:03
另外，二次域Frobenius测试和Lucas序列测试，虽然都是基于二次型，但是重要区别是即使最弱形式，二次域Fr ...

真受不了你，给我点评那么多，不与你争论这个问题了

nyy

无心人 发表于 2023-5-17 17:03
另外，二次域Frobenius测试和Lucas序列测试，虽然都是基于二次型，但是重要区别是即使最弱形式，二次域Fr ...

二次域Frobenius测试, 我不懂得这个

nyy

无心人 发表于 2023-5-17 17:03
另外，二次域Frobenius测试和Lucas序列测试，虽然都是基于二次型，但是重要区别是即使最弱形式，二次域Fr ...

你写的代码对大整数有用吗？还是只对比较小的整数有用？