无心人 发表于 2023-5-4 10:47
同样增加一次基3强伪素数测试的BPSW
我当初问***他素数判定的实现算法，***把他的算法当成宝贝，还舍不得告诉我。
没想到你也能实现这个算法，要是早知道，我就问你了。
只可惜你在论坛上发出来之前，我已经学会了BPSW的实现算法，
我从GitHub上搜索到相关的代码，然后研究透的！
作为比较，贴上flint自带素性测试的代码，执行时间60.261s
考虑我代码少做一次基2测试，加上基2测试，以QFT为例，是30.948秒，
#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <flint/ulong_extras.h>
int main()
{
uint64_t p, cnt = 0, tst = 0;
//test();
FILE* sprp2File = fopen("2-SPRP-2-to-64.txt", "r");
if (!sprp2File)
{
perror("文件2-SPRP-2-to-64.txt不存在");
return EXIT_FAILURE;
}
char line;
while (fgets(line, 32, sprp2File) != NULL)
{
char* end;
p = strtoull(line, &end, 10);
if (n_is_prime(p))
cnt ++;
tst ++;
}
fclose(sprp2File);
printf("test: %lu, failed: %lu\n", tst, cnt);
return 0;
}
无心人 发表于 2023-5-4 11:44
作为比较，贴上flint自带素性测试的代码，执行时间60.261s
考虑我代码少做一次基2测试，加上基2测试，以QF ...
你的伪素数文件，能上传共享一下不？
要那种以2为底的强伪素数！
无心人 发表于 2023-5-4 11:44
作为比较，贴上flint自带素性测试的代码，执行时间60.261s
考虑我代码少做一次基2测试，加上基2测试，以QF ...
只要以2为底的强伪素数！
即使是以2位底的强伪素数，也有633.1M吗？还是太大了！
老外真是闲的没事干，居然2^64以下的伪素数都找出来，计算资源可真多，就是不知道他们素数判定算法怎么搞的（在找2^64以下的伪素数的时候）
国外有开源的大整数算法库，比hugecalc还要快很多！我要是没试过，我都不敢相信。
无心人 发表于 2023-5-4 10:47
同样增加一次基3强伪素数测试的BPSW
1次SLPSP测试约等于3.8次SPSP测试
用SLPSP的优点是可以进行lucas U+Lucas V+一次半强伪素数
具体见下面的代码！
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=18553&fromuid=14149
我都是开源的，但是我不敢说“原创”
nyy 发表于 2023-5-15 13:20
用SLPSP的优点是可以进行lucas U+Lucas V+一次半强伪素数
具体见下面的代码！
另外，二次域Frobenius测试和Lucas序列测试，虽然都是基于二次型，但是重要区别是即使最弱形式，二次域Frobenius测试，只要保证选择的参数 z 不是某个形如 a + bi 的复整数（a, b都是整数，且其中一个是0）的平方根，就不存在伪素数
无心人 发表于 2023-5-17 17:03
另外，二次域Frobenius测试和Lucas序列测试，虽然都是基于二次型，但是重要区别是即使最弱形式，二次域Fr ...
原创？？？？