期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

最短加法链算法 被引量：7

AN ALGORITHM FOR GENERATING THE SHORTEST ADDITION CHAINS
下载PDF
导出
摘要 本文讨论了关于正整数 n的最短加法链问题 .利用已取得的关于正整数 n的最短加法链长度 l(n)的上、下界的理论成果 ,构造了在回溯法中对状态空间树进行剪枝的精细的剪枝函数 ,从而设计出产生任意正整数 This paper is concerned with the computational aspects of gererating the shortest addition chains for an integer n. Theoretically developed lower and upper bounds for the minimal length of the addition chains for an integer n are exploited to construct a subtle pruning function used in the backtracking algorithm. Finally an efficient algorithm for generating the shortest addition chains for an integer n is presented.
作者 王晓东
机构地区 福州大学计算机科学与技术系
出处 《小型微型计算机系统》 CSCD 北大核心 2001年第10期1250-1253,共4页 Journal of Chinese Computer Systems
基金 福建省科学技术厅项目 (2 0 0 0 Z14 8) 国家 973项目 (G19980 3 0 60 0 T)资助
关键词 最短加法链 状态空间树 回溯法 剪枝技术 算法 数据结构 Shortest addition chains State space trees Backtracking algorithms Pruning techniques
分类号 TP311.12 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献9

  • 1[1]F.Bergeron,J.Berstel,S.Brlek,and C.Duboc. Addition chains using continued fractions[J].Algorithms,1989,10,403～412.
  • 2[2]J.Bos and M.Coster. Addition chain heuristics[C]. in Proc. CRYPTO89,1990 400～407.
  • 3[3]D.Dobkin and R.J.Lipton. Addition chain methods for the evaluation of specific polynomials[J]. SIAM J.Comput.,1980,9,121～125.
  • 4[4]P.Downey,B.Leong and R.Sethi, Computing sequences with addition chains[J]. SIAM J.Comput.1981,10,638～646.
  • 5[5]D.E.Knuth. The Art of computer programming[M].Vol 2,3rd ed.,Addison-Wesley, Reading, MA,1997,461～485.
  • 6[6]A.Schonhage. A lower bound for the length of addition chains[J], Theoret. Comput. Science 1,1975. 1～12
  • 7[7]E.G.Thurber. The Scholz-Brauer problem on addition chains. Pacific J. Math.,49,229～242, 1973.
  • 8[8]E.G.Thurber. Addition chains and solutions of l(2n)=l(n) and l(2n-1)=n+l(n)-1[J]. Discrete Math.1976 16, 279～289.
  • 9[9]E.G.Thurber. Addition chains-an erratic sequence[J]. Discrete Math.1993, 122, 287～305.

同被引文献39

  • 1安宾,王晓东,段远源,王智学.p-T热力学面上水和水蒸气密度的快速计算[J].应用基础与工程科学学报,2012,20(S1):190-198. 被引量：2
  • 2贺毅朝,刘坤起.Rabin密码算法的快速实现研究[J].计算机应用研究,2006,23(9):51-53. 被引量：2
  • 3STINSON DR.密码学原理与实践[M].冯登国,译.北京:电子工业出版社,2003.
  • 4冯登国 裴定一.密码学导引[M].北京：科学出版社,2001.230-231.
  • 5Daniel Bleichenbacher,Achim Flammenkamp.An efficient algorithm for computing shortest addition chains[J].SIAM Journal of Discrete Mathematics,1997:10(1):15-17.
  • 6STALLINGS W.密码编码学与网络安全--原理与实践[M].刘玉珍,等译.北京:电子工业出版社,2004.
  • 7KNUTH DE.The Art of Computer Programming:Seminumerical Algorithms,Volume 2[M].3rd edition.Addtion-Wesley,2003.
  • 8ROSE KH.Elementary Number Theory and Its Application[M].Addison-Wesley,1984.
  • 9DOWNEY P,LEONY B,SETHI R.Computing Sequence with Addition Chains[J].SIAM Journal of Computing,1981,10(3):638 -646.
  • 10DIFFIE W,HELLMAN ME.New Direction in Cryptography[J].IEEE Transactions on Information Theory,1976,IT-22(6):644 -654.

引证文献7

二级引证文献20

小型微型计算机系统
2001年 第10期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部