主权项 |
1.一种用以计算E (M,X,N)之方法,其中M,X,N为整数,E (M,X,N)意指先算出M之X次方,再以结果除以N之余数,该方法具有下列特征:(1)整数X用另一整数B>1为基数表示为Xn-1 Xn-2……………………XiXo,(2)预设R=1,从i=n-1至i=0,重复下列四个步骤,(I)计算E (R,B,N),(II)计算E (M,Xi,N),(III)计算(I),(II)结果之乘积,并用以替代R,(IV)i减1,最终之R即为结果,(3)特征(2)(II)中计算E (M,Xi,N),1<Xi≦B之方法为将Xi对应到一个数列,mt mt-1……………m1 m0,其中Xi=mt>mt-1>mt-2…………>m1>m0=0,而且ms=mu+mv,u,v<s,0≦s≦t,然后,依右往左顺序,计算E(M,m,N),E (M,m2,N),…………E(M,mt-1,N),并以mj,u≦j≦t为索引存于一个记忆装置MEM中,(4)特征(2)(II)及(3)中计算E(M,m,N)时,先以m为索引于记忆装置MEM中检查是否已存在,倘若已存在,就不必计算,直接由MEM中取出。图式简单说明:第一图列出1至256每个整数的数例。 |