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

nyy

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

我当初问***他素数判定的实现算法，***把他的算法当成宝贝，还舍不得告诉我。
没想到你也能实现这个算法，要是早知道，我就问你了。
只可惜你在论坛上发出来之前，我已经学会了BPSW的实现算法，
我从GitHub上搜索到相关的代码，然后研究透的！

无心人

作为比较，贴上flint自带素性测试的代码，执行时间60.261s
考虑我代码少做一次基2测试，加上基2测试，以QFT为例，是30.948秒，

1. #include <stdbool.h>
   
2. #include <stdio.h>
   
3. #include <stdint.h>
   
4. #include <stdlib.h>
   
5. #include <flint/ulong_extras.h>
   
6. 
   
7. int main()
   
8. {
   
9.   uint64_t p, cnt = 0, tst = 0;
   
10.   //test();
    
11.   FILE* sprp2File = fopen("2-SPRP-2-to-64.txt", "r");
    
12.   if (!sprp2File)
    
13.   {
    
14.     perror("文件2-SPRP-2-to-64.txt不存在");
    
15.     return EXIT_FAILURE;
    
16.   }
    
17.   char line[32];
    
18.   while (fgets(line, 32, sprp2File) != NULL)
    
19.   {
    
20.     char* end;
    
21.     p = strtoull(line, &end, 10);
    
22.     if (n_is_prime(p))
    
23.       cnt ++;
    
24.     tst ++;
    
25.   }
    
26. 
    
27.   fclose(sprp2File);
    
28.   printf("test: %lu, failed: %lu\n", tst, cnt);
    
29.   return 0;
    
30. }
    
31. 
    

复制代码

nyy

无心人 发表于 2023-5-4 11:44
作为比较，贴上flint自带素性测试的代码，执行时间60.261s
考虑我代码少做一次基2测试，加上基2测试，以QF ...

你的伪素数文件，能上传共享一下不？
要那种以2为底的强伪素数！

nyy

无心人 发表于 2023-5-4 11:44
作为比较，贴上flint自带素性测试的代码，执行时间60.261s
考虑我代码少做一次基2测试，加上基2测试，以QF ...

只要以2为底的强伪素数！

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 ...

原创？？？？