有理逼近算法.docx

实验五、有理逼近算法

曾凡洋4012013033

1实验目的

(1)熟练掌握有理逼近算法的理论根底.

(2)熟练掌握有理逼近算法的流程.

(3)熟练掌握有理逼近算法在序列密码分析中的作用.

2实验要求

学员应当熟练掌握有理逼近算法的根本流程.给出该算法的通用函数RA(a,N),以正整数N和长为N的有限序列a??(a0,a1,a2,…,aN?1)为输入参数,以有限序列a的极小连接数和2-adic复杂度为返回值.通过对该算法的实现,熟练掌握有理逼近算法的步骤.

3实验内容

(1)写出有理逼近算法的函数RA(a,N),其中参数a??(a0,a1,a2,…,aN?1)为一条有限序列,N为该序列长度,函数返回值是有限序列的极小连接数和2-adic复杂度.

(2)计算序列

a(1000)??()

的极小连接数和2-adic复杂度.

(3)设a??(1101101110)?G(x10+x3+1),b???G(x8+x4+x3+x2+1)记?,求序列c??(c0,c1,c2,…)的极小连接数和周期.

(4)*设计一个输入和输出窗口,输入一串比特序列,输出极小连接数和2-adic复杂度.

4算法设计

第一步〔初始化〕：找到一个不为0的比特，设：

，

第二部〔循环〕：设，且以求得满足。

假设，那么令

。

(b)假设，用下属方法构造。

〔b.1)假设，那么令

其中奇数d按定理7.7.3确定

〔b.2)〔b.1)假设，那么令

其中奇数d按定理7.7.3确定

第三步〔输出〕：当k=N-1时，输出〔〕，那么，为a(N-1)的极小有理分数表示。

5实验结果

RA(a,N)函数如下：

compare(j1,j2)=

{

if(abs(j1)>=abs(j2),return(abs(j1)),return(abs(j2)););

}

find_d(m,n,x,y)=

{

local(z,d,s);

d=vector(2);

s=vector(2);

if(x*y>=0,z=-(m+n)\(x+y);if(z%2==1,d[1]=z;d[2]=z+2,d[1]=z-1;d[2]=z+1;);s[1]=compare(m+d[1]*x,n+d[1]*y);s[2]=compare(m+d[2]*x,n+d[2]*y);if(s[1]>=s[2],return(d[2]),return(d[1]);),

z=-(m-n)\(x-y);if(z%2==1,d[1]=z;d[2]=z+2,d[1]=z-1;d[2]=z+1;);s[1]=compare(m+d[1]*x,n+d[1]*y);s[2]=compare(m+d[2]*x,n+d[2]*y);if(s[1]>=s[2],return(d[2]),return(d[1]);););

}

update(a,b,c,d)=

{

local(w,r,h,g,v1,v2,v3,v4);

h=compare(a,b);

g=compare(c,d);

if(h>=g,w=find_d(a,b,c,d);a=a+w*c;b=b+w*d;c=2*c;d=2*d,w=find_d(c,d,a,b);v1=a;v2=b;v3=c;v4=d;a=v3+w*v1;b=v4+w*v2;c=2*v1;d=2*v2;);

r=[a,b,c,d];

return(r);

}

RA(a,N)=

{

local(i,k,t,p,q,P,Q,e);

t=2000;

for(i=1,N,if(a[i]!=0,t=i;break,););

if(t<=N,p=2^(t-1);q=1;P=0;Q=2;alf=0;for(j=1,t,alf=alf+a[j]*2^(j-1);),p=0;q=1);

e=vector(4);

for(k=t,N-1,alf=alf+a[k+1]*2^k;if(p==Mod(q*alf,2^(k+1)),P=2*P;Q=2*Q,e=update(p,q,P,Q);p=e[1];q=e[2];P=e[3];Q=e[4];););

print("p=");

print(p);

print("q=");

print(q);

print("2-adic=");

print(log(compare(p,q))/log(2));

}

〔2〕

结果如图：

(3)

思路：

先算出序列a的有理分数表示为，b的有理分式表示，从而得到2-adic复杂度与。

计算方法：a的周期为1023，b的周期为255，所以产生a序列1023*2+1比特，b序列255*2+1比特，代入上述