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)$
因完全不涉及大整数运算，故应该能快速求出
可能有相关资料，但自己做的菜香是不是啊？ 问题一好做，一个暴力搜索就能做到了。
问题二需要些数论知识了 问题二就是先找出p的任意一个原根g,然后计算$g^b (mod p)$就可以了。用gxqcn的HugeCalc应该很简单是不是？ :)
都是小数字运算啊
用HugeCalc还不够建立实例的呢 关键是问题一能得到最全的结果
将来转移到64位，大家能顺利的找到合适的参数
而不是参考这个库那个包而没自己的东西 是小数字运算。只是我印象中HugeCalc已经提供了原根的算法。
虽然说计算原根很简单，对于n位整数，是个按概率O(n)的算法，不过如果已经有现成的，何不直接使用呢？反正这里效率并不重要 我当时就是用 HugeCalc 搜索出这类素数的，哈哈！:) :lol
那就再搜索一遍吧
筛选特定素数源代码
// selPrime.cpp//
// Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
// Win32 Debug: Debug Multithreaded DLL
// Win32 Release: Multithreaded DLL
#include <iostream.h>
#include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
#include "../../../HugeCalc_API/CppAPI/Include/HugeIntX.h" // 公共接口
#pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
#pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
int main(int argc, char* argv[])
{
// printf("Hello World!\n");
cout << "Call " << HugeCalc::GetVer() << endl << endl;
CHugeIntX hugeAdd;
CHugeIntX hugeNum;
UINT32 u32Bits, k;
for( u32Bits = 31; u32Bits >= 24; --u32Bits )
{
cout << endl << u32Bits << endl;
( hugeAdd = 1 ) <<= u32Bits;
hugeNum = 1;
for ( k = 0; k < ( 1UL << ( 32 - u32Bits )); ++k )
{
if (( hugeNum += hugeAdd ).IsPrime())
{
cout << hugeNum.GetStr( FS_NORMAL ) << "\t= "
<< (UINT32)hugeNum << endl;
}
}
}
#if 1
cout << endl << "===========================" << endl << endl;
CHugeIntX hugeSub;
for( u32Bits = 32; u32Bits >= 24; --u32Bits )
{
++(( hugeNum = 1 ) <<= u32Bits );
hugeSub = 1;
for ( k = 0; k < u32Bits; ++k )
{
if (( hugeNum -= hugeSub ).IsPrime())
{
cout << "2^" << u32Bits << "-" << "2^" << k << "+1 = "
<< hugeNum.GetStr(FS_NORMAL) << endl;
}
hugeNum += hugeSub;
hugeSub <<= 1;
}
}
#endif
// system( "pause" );
return 0;
}请将上述代码放在 ..\HugeCalc\testDLL\src\ANSI_C++\ 目录下编译运行
上述素数均可用DWORD表示，本不必用大数类型；
但为便于扩展计，特意采用了CHugeIntX数据类型。
现在代码里面的数字稍加修改，即可得到其它范围内的素数。
HugeCalc 已提供了“原根”（PrimitiveRoot）、“指数”（MultiplicativeOrder）等数论函数，
它们也是经过高度优化过的，效率很高。 这2个问题其实都不难,就像楼主所说,暴力搜索就行.其中第二个问题,一般的数论书中都有的介绍的.
关键是如何找到这样一个素数,使得其2是其n次根,这样才能快速计算.如果加上这个条件,那么楼主的2各问题才真的变难了,只有真的学数论的人可解.
寻找NTT的模我是用的Mathematica,介于我的水平有限,也只用的暴力搜索,诶!