无心人 发表于 2008-4-13 09:55:46

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)$

因完全不涉及大整数运算,故应该能快速求出
可能有相关资料,但自己做的菜香是不是啊?

无心人 发表于 2008-4-13 09:58:59

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

mathe 发表于 2008-4-13 10:13:25

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

无心人 发表于 2008-4-13 11:55:14

:)

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

无心人 发表于 2008-4-13 12:07:05

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

mathe 发表于 2008-4-13 14:59:42

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

gxqcn 发表于 2008-4-13 15:00:39

我当时就是用 HugeCalc 搜索出这类素数的,哈哈!:)

无心人 发表于 2008-4-13 16:28:58

:lol

那就再搜索一遍吧

gxqcn 发表于 2008-4-14 08:31:02

筛选特定素数源代码

// 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)等数论函数,
它们也是经过高度优化过的,效率很高。

ssikkiss 发表于 2008-5-1 20:04:52

这2个问题其实都不难,就像楼主所说,暴力搜索就行.其中第二个问题,一般的数论书中都有的介绍的.
关键是如何找到这样一个素数,使得其2是其n次根,这样才能快速计算.如果加上这个条件,那么楼主的2各问题才真的变难了,只有真的学数论的人可解.
寻找NTT的模我是用的Mathematica,介于我的水平有限,也只用的暴力搜索,诶!
页: [1] 2 3 4 5 6 7 8 9
查看完整版本: NTT相关问题一则,有兴趣的参与