找回密码
 欢迎注册
查看: 49076|回复: 83

[讨论] NTT相关问题一则,有兴趣的参与

[复制链接]
发表于 2008-4-13 09:55:46 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
有$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 | 显示全部楼层
问题一好做,一个暴力搜索就能做到了。
问题二需要些数论知识了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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位,大家能顺利的找到合适的参数
而不是参考这个库那个包而没自己的东西
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-13 14:59:42 | 显示全部楼层
是小数字运算。只是我印象中HugeCalc已经提供了原根的算法。
虽然说计算原根很简单,对于n位整数,是个按概率O(n)的算法,不过如果已经有现成的,何不直接使用呢?反正这里效率并不重要
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-13 15:00:39 | 显示全部楼层
我当时就是用 HugeCalc 搜索出这类素数的,哈哈!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-13 16:28:58 | 显示全部楼层


那就再搜索一遍吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-14 08:31:02 | 显示全部楼层

筛选特定素数源代码

  1. // selPrime.cpp
  2. //

  3. //    Project -> Setting -> C/C++ -> Code Generation --> Use run-time library:
  4. //        Win32 Debug:    Debug Multithreaded DLL
  5. //        Win32 Release:    Multithreaded DLL

  6. #include <iostream.h>

  7. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h"    // 公共接口
  8. #include "../../../HugeCalc_API/CppAPI/Include/HugeIntX.h"    // 公共接口

  9. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  10. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )

  11. int main(int argc, char* argv[])
  12. {
  13. //    printf("Hello World!\n");

  14.     cout << "Call " << HugeCalc::GetVer() << endl << endl;

  15.     CHugeIntX hugeAdd;
  16.     CHugeIntX hugeNum;
  17.     UINT32 u32Bits, k;

  18.     for( u32Bits = 31; u32Bits >= 24; --u32Bits )
  19.     {
  20.         cout << endl << u32Bits << endl;
  21.         ( hugeAdd = 1 ) <<= u32Bits;
  22.         hugeNum = 1;
  23.         for ( k = 0; k < ( 1UL << ( 32 - u32Bits )); ++k )
  24.         {
  25.             if (( hugeNum += hugeAdd ).IsPrime())
  26.             {
  27.                 cout << hugeNum.GetStr( FS_NORMAL ) << "\t= "
  28.                     << (UINT32)hugeNum << endl;
  29.             }
  30.         }
  31.     }

  32. #if 1
  33.     cout << endl << "===========================" << endl << endl;

  34.     CHugeIntX hugeSub;
  35.     for( u32Bits = 32; u32Bits >= 24; --u32Bits )
  36.     {
  37.         ++(( hugeNum = 1 ) <<= u32Bits );
  38.         hugeSub = 1;
  39.         for ( k = 0; k < u32Bits; ++k )
  40.         {
  41.             if (( hugeNum -= hugeSub ).IsPrime())
  42.             {
  43.                 cout << "2^" << u32Bits << "-" << "2^" << k << "+1 = "
  44.                     << hugeNum.GetStr(FS_NORMAL) << endl;
  45.             }
  46.             hugeNum += hugeSub;

  47.             hugeSub <<= 1;
  48.         }
  49.     }
  50. #endif


  51. //    system( "pause" );

  52.     return 0;
  53. }
复制代码
请将上述代码放在 ..\HugeCalc\testDLL\src\ANSI_C++\ 目录下编译运行

上述素数均可用DWORD表示,本不必用大数类型;
但为便于扩展计,特意采用了CHugeIntX数据类型。

现在代码里面的数字稍加修改,即可得到其它范围内的素数。

HugeCalc 已提供了“原根”(PrimitiveRoot)、“指数”(MultiplicativeOrder)等数论函数,
它们也是经过高度优化过的,效率很高。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-5-1 20:04:52 | 显示全部楼层
这2个问题其实都不难,就像楼主所说,暴力搜索就行.其中第二个问题,一般的数论书中都有的介绍的.
关键是如何找到这样一个素数,使得其2是其n次根,这样才能快速计算.如果加上这个条件,那么楼主的2各问题才真的变难了,只有真的学数论的人可解.
寻找NTT的模我是用的Mathematica,介于我的水平有限,也只用的暴力搜索,诶!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 16:16 , Processed in 0.102699 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表