NTT相关问题一则，有兴趣的参与

无心人

有$p = b 2^t + 1$形式素数，$p < 2^32, b < root{4}{p}, b -= 1 (mod \quad 2), 10 <= t <= 28$。 问题一、求出所有这类素数。 问题二、求$\alpha$使$\alpha ^ {2 ^ {t//2}} -= - 1 (mod \quad p)$ 因完全不涉及大整数运算，故应该能快速求出 可能有相关资料，但自己做的菜香是不是啊？

无心人

问题一好做，一个暴力搜索就能做到了。 问题二需要些数论知识了

mathe

问题二就是先找出p的任意一个原根g,然后计算$g^b (mod p)$就可以了。用gxqcn的HugeCalc应该很简单是不是？

无心人

都是小数字运算啊 用HugeCalc还不够建立实例的呢

无心人

关键是问题一能得到最全的结果 将来转移到64位，大家能顺利的找到合适的参数 而不是参考这个库那个包而没自己的东西

mathe

是小数字运算。只是我印象中HugeCalc已经提供了原根的算法。 虽然说计算原根很简单，对于n位整数，是个按概率O(n)的算法，不过如果已经有现成的，何不直接使用呢？反正这里效率并不重要

gxqcn

我当时就是用 HugeCalc 搜索出这类素数的，哈哈！

无心人

那就再搜索一遍吧

gxqcn

1. // selPrime.cpp
2. //
4. // Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
5. // Win32 Debug: Debug Multithreaded DLL
6. // Win32 Release: Multithreaded DLL
8. #include <iostream.h>
10. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
11. #include "../../../HugeCalc_API/CppAPI/Include/HugeIntX.h" // 公共接口
13. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
14. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
16. int main(int argc, char* argv[])
17. {
18. // printf("Hello World!\n");
20. cout << "Call " << HugeCalc::GetVer() << endl << endl;
22. CHugeIntX hugeAdd;
23. CHugeIntX hugeNum;
24. UINT32 u32Bits, k;
26. for( u32Bits = 31; u32Bits >= 24; --u32Bits )
27. {
28. cout << endl << u32Bits << endl;
29. ( hugeAdd = 1 ) <<= u32Bits;
30. hugeNum = 1;
31. for ( k = 0; k < ( 1UL << ( 32 - u32Bits )); ++k )
32. {
33. if (( hugeNum += hugeAdd ).IsPrime())
34. {
35. cout << hugeNum.GetStr( FS_NORMAL ) << "\t= "
36. << (UINT32)hugeNum << endl;
37. }
38. }
39. }
41. #if 1
42. cout << endl << "===========================" << endl << endl;
44. CHugeIntX hugeSub;
45. for( u32Bits = 32; u32Bits >= 24; --u32Bits )
46. {
47. ++(( hugeNum = 1 ) <<= u32Bits );
48. hugeSub = 1;
49. for ( k = 0; k < u32Bits; ++k )
50. {
51. if (( hugeNum -= hugeSub ).IsPrime())
52. {
53. cout << "2^" << u32Bits << "-" << "2^" << k << "+1 = "
54. << hugeNum.GetStr(FS_NORMAL) << endl;
55. }
56. hugeNum += hugeSub;
58. hugeSub <<= 1;
59. }
60. }
61. #endif
64. // system( "pause" );
66. return 0;
67. }

复制代码

请将上述代码放在 ..\HugeCalc\testDLL\src\ANSI_C++\ 目录下编译运行 上述素数均可用DWORD表示，本不必用大数类型； 但为便于扩展计，特意采用了CHugeIntX数据类型。 现在代码里面的数字稍加修改，即可得到其它范围内的素数。 HugeCalc 已提供了“原根”（PrimitiveRoot）、“指数”（MultiplicativeOrder）等数论函数， 它们也是经过高度优化过的，效率很高。

ssikkiss

这2个问题其实都不难,就像楼主所说,暴力搜索就行.其中第二个问题,一般的数论书中都有的介绍的. 关键是如何找到这样一个素数,使得其2是其n次根,这样才能快速计算.如果加上这个条件,那么楼主的2各问题才真的变难了,只有真的学数论的人可解. 寻找NTT的模我是用的Mathematica,介于我的水平有限,也只用的暴力搜索,诶!