这是我用来找NTT参数的代码,由于我的MATHEMATICA刚学不久,有什么不对的地方大家指正!
这里我没有找到具有较好的n次跟的NTT,水平有限啊!
mulinv:=Module[{p,f},p=
ExtendedGCD;p=p[];f=Mod]*a,a*b];Return]
nextprime:=Module[{p},
p=m+step;
While\False,p+=step];
Return;
]
nroot:=Module[{k,a,b,n2=n/2,p2=p-1,i},
k=2;
i=0;
Do\1 && PowerMod\p2,Break[]];
i++;k*=2,{16}];
If];
k=2;
i=0;
Do\1 && PowerMod\p2,Break[]];
i++;k*=2,{16}];
If];
k=4;
i=0;
Do\1 && PowerMod\p2,
Break[]];i++;k*=2,{16}];
If];
k=1;
While[(PowerMod!=p2)||(PowerMod!=1),k++];
Return;
]
findntt:=Module[{n=2^e,m,a,ia,invn,i},
m=n*w*w+1-n;
m=nextprime;
a=nroot;
ia=PowerMod;
invn=m-(m-1)/n;
Return[{n,m,a,ia,invn}];
]
nttlist:=Module[{},Return,{i,1,maxe,1}]]]
Put["ntt paramtarer,for base=10","ntt1.txt" ] ;
PutAppend,"ntt1.txt"];
这个也是我用来找NTT参数的,不过它同时找2组参数,并且增加对在NTT里使用CRT(中国余数定理)的支持
mulinv:=Module[{p,f},p=
ExtendedGCD;p=p[];f=Mod]*a,a*b];Return]
findntt:=Module[{n=2^e,i,j,z,
m,m1,m2,a1,a2,b1,b2,invm1,invm2,k1,k2,tmp,t1,t2},t1=n/2;
t2=n-1;
z=w*Sqrt;
z=Floor;
m=z;
z=Mod;
m-=z;
m+=1;
While≠True,m+=n];
m1=m;
invm1=(m*n-m+1)/n;
a1=findroot;
b1=PowerMod;
m+=n;
While≠True,m+=n];
m2=m;
invm2=(m*n-m+1)/n;
a2=findroot;
b2=PowerMod;
m=m1*m2;
k1=mulinv;
k2=mulinv;
PutAppend["___________________________________",fn];
PutAppend[{"N = ",n},fn];
PutAppend["___________________________________",fn];
PutAppend[{"M1=",m1," a1=",a1,"1/a1=",b1,"invm1=",invm1},fn];
PutAppend[{"M2=",m2,"a2=",a2,"1/a2=",b2,"invm2=",invm2},fn];
PutAppend[{"M1*M2=",m,"k1=",k1,"k2=",k2},fn];
PutAppend[{"M1M2/NWW=",N},fn];
PutAppend["___________________________________",fn];]
findroot:=Module[{i,j,l,q,b,v,f,d},
j=2;
i=p-1;
i=i/n;
q=0;
l=PowerMod;
While[( l<2) || (ispow\2),j++;q++;l=PowerMod;If[q>
200000,Break[]]];
If];
q=0;
l=2;
b=n/2;
v=p-1;
f=PowerMod;
d=PowerMod;
While[(!(f== 1 )) || (!(d == v)),l++;q++;f=PowerMod;d=PowerMod[l,
b,p];If];];
If[(f\1)&&(d\v),Return];
q=0;
l=PowerMod;
While[( l<2) || (ispow\2),j++;
q++;l=PowerMod;If]];
If];
l=PowerMod;
While[( l<2) ,j++;q++;l=PowerMod;];
Return;
]
ispow:=Module[{xx=
n},If1,Return];While\0,xx/=
2];If1,Return,Return;];]
startfindntt:=Module[{},
Put["Search For NTT Parameter",filename];
PutAppend[{"It's used for ",wordSize," word width,"},filename];
Do,{i,1,32}];]
startfindntt;
startfindntt;
startfindntt;
startfindntt;
startfindntt;
startfindntt;
startfindntt;
startfindntt;
startfindntt;
程序有点难懂
呵呵
能写出程序运行结果么？
另外有其他形式的表示
稍后会开贴讨论
不过日期可能无限向后推迟
传上个附件,里面是我用MATHEMATICA的计算结果
现在对这个附件里的文件的解释:
"Search For NTT Parameter" 每个文件都以这句打头
{"It's used for ", 10, " word width,"}表示这个文件里的参数,例如,这里是 用于 10^1进制
"___________________________________"
{"N = ", 2} 表示紧接着的下面的参数,这里是 可用于长n=2的变换
"___________________________________"
{"M1=", 17, " a1=", 16, "1/a1=", 16, "invm1=", 9}表示 其中一个模M=17,根为16,根的倒数也是16,1/2是9
{"M2=", 19, "a2=", 18, "1/a2=", 18, "invm2=", 10} 第2个模M=19,........................
{"M1*M2=", 323, "k1=", 171, "k2=", 153}M1*M2是这两个模的积,k1和k2是用于CRT的2个参数
{"M1M2/NWW=", 1.615\`4.000000000000001} 这个的意义,如果这个值小于1,那么此组参数将无法进行NTT变换
"___________________________________"
再传各附件,这是用前面第一个程序得到的,里面仅计算一组NTT参数,没有对CRT的支持
对此附件里的内容的解释:
{2, 211, 210, 210, 106},表示一个长度n=2的变换,其模M=211,根是210,根的倒数也是210,1/2是106
{4, 401, 20, 381, 301},
{8, 809, 44, 570, 708}, 表示一个长n=8的变换,模M=809,根是44,根的倒数是570,1/8是708
..
..
..
:)
多谢分享
不过，怎么说呢
有实际用途的参数不多的
:)
你做下模是2^b + 1，可能b不是2^t形式，但是s*2^t形式，s为奇数
模不是素数
变换长度是2的方幂，根也最好是2的方幂的NTT的搜索
这个实用性强些
你说的是伪费马变换吧!我上面的参数全是s*2^t形式的,但我注意过s是不是奇数.
目前为止我还没找到有效的好的NTT,那种根是2或2得幂的,正探索中....
顺带问个小问题,我做NTT变换时,是用刚才的程序先生成一堆(其实就32组)NTT参数,作ntt变换的时候根据数据的长短调用相应的参数
不知楼主是怎么做的?不可能对不同长度的数据应用相同德一组NTT参数吧?
:)
s必须是奇数，否则也可转换成这种形式
看NTT自身的限制
在我的介绍NTT的帖子里有限制条件
如果用途就是卷积，则就是了
如果是大数运算，则还需要修改下
:)
可以对不同长度的数据应用相同的NTT参数
关键是补零
在我帖子里开头有证明