[1]陈汉武,李志强,徐宝文.置换群与整数间一对一 Hash函数的构建[J].东南大学学报(自然科学版),2008,38(2):225-227.[doi:10.3969/j.issn.1001-0505.2008.02.008]
 Chen Hanwu,Li Zhiqiang,Xu Baowen.Construction of one-for-one Hash function mapping between permutation group and integral number[J].Journal of Southeast University (Natural Science Edition),2008,38(2):225-227.[doi:10.3969/j.issn.1001-0505.2008.02.008]
点击复制

置换群与整数间一对一 Hash函数的构建()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
38
期数:
2008年第2期
页码:
225-227
栏目:
计算机科学与工程
出版日期:
2008-03-20

文章信息/Info

Title:
Construction of one-for-one Hash function mapping between permutation group and integral number
作者:
陈汉武1 李志强12 徐宝文1
1 东南大学计算机科学与工程学院, 南京 210096; 2 扬州大学信息工程学院, 扬州 225009
Author(s):
Chen Hanwu1 Li Zhiqiang12 Xu Baowen11
School of Computer Science and Engineering, Southeast University, Nanjing 210096,China)2(College of Information Engineering, Yangzhou University, Yangzhou 225009,China
关键词:
Hash函数 置换群 量子信息 可逆逻辑
Keywords:
Hash function permutation group quantum information reversible logic
分类号:
TP3-05
DOI:
10.3969/j.issn.1001-0505.2008.02.008
摘要:
为了提高量子可逆逻辑电路自动生成与优化的效率,给出了一个在置换群与整数域上满足一对一映射的Hash函数构建方法.一个n×n的量子可逆逻辑门的输入和输出对可有2n!种组合,若将一个组合对应一个置换,则一切2n次置换的集合就组成一个置换群.Hash函数H(X)利用每一个置换中数字的排列位置,求出该数字的逆序数并计算其函数值,将置换群的元素X(a0a1…a2n-1)映射到整数Z∈{0,1,…,2n!-1}的集合上,快速确定计算位置.该函数不但可以大大提高量子可逆逻辑综合算法的效率,而且结构简单,性质良好,具有一般性意义.
Abstract:
For improving the efficiency of reversible logic circuit automation and optimization of quantum, a construction of one-for-one Hash function mapping between permutation group and integral number is proposed. There are 2n! combinatorial duals of input/output in a reversible logic gate of n×n quantum. If a combinatorial dual corresponds to a permutation, then a permutation group can be created with the set composed by all 2n permutations. The Hash function H(X) maps an element X(a0a1…a2n-1) of a permutation group onto an integer Z∈{0,1,…,2n!-1} by counting athwart ordinal number of every number in a permutation by using its arrangement and computing its function value, and quickly confirming the position. The efficiency of synthetic algorithms for reversible logic of quantum can be greatly improved by using this function.Moreover, this function has simple structure, good performance and universality.

参考文献/References:

[1] Agrawal A, Jha N K.Synthesis of reversible logic[C] //Proceedings of the Design,Automation and Test in Europe Conference and Exhibition.Paris,2004,2:1384-1385.
[2] 何雨果,孙吉贵.基于Haar小波的多尺度分析量子电路[J].科学通报,2005,50(20):2314-2316.
  He Yyguo,Sun Jigui.The construction of multiscale analysis quantum circuits based on Haar wavelet[J].Chinese Science Bulletin,2005,50(20):2314-2316.(in Chinese)
[3] Bennett C H.Logical reversibility of computation [J].IBM Journal of Research and Development,1973,17(6):525-532.
[4] Shende V V,Prasad A K,Markov I L,et al.Reversible logic circuit synthesis[C] //Proceedings of the ACM/IEEE International Conference on Computer-Aided Design.San Jose,California,2002:125-132.
[5] Shende V V,Prasad A K,Markov I L,et al.Synthesis of reversible logic circuits[J].IEEE Trans on Circuits and Systems-Ⅰ,2003, 22(6):723-729.
[6] Miller D M,Maslov D,Dueck G W.A transformation based algorithm for reversible logic synthesis[C] //Proceedings of the 40th Design Automation Conference.Anaheim,CA,USA,2003:318-323.
[7] Song X Y,Yang G W,Perkowski M,et al.Algebraic characteristics of reversible gates[J].Theory of Computing Systems,2004,37(2):311-319.
[8] Yang G W,Song X Y,Perkowski M,et al.Fast synthesis of exact minimal reversible circuits using group theory[C] //Proceedings of IEEE ASP-DAC.Shanghai,China,2005,2:18-21.

相似文献/References:

[1]赵耿,袁阳,王冰.基于交叉耦合映象格子的单向Hash函数构造[J].东南大学学报(自然科学版),2009,39(4):728.[doi:10.3969/j.issn.1001-0505.2009.04.015]
 Zhao Geng,Yuan Yang,Wang Bing.One-way Hash function construction based on crossing coupled map lattice[J].Journal of Southeast University (Natural Science Edition),2009,39(2):728.[doi:10.3969/j.issn.1001-0505.2009.04.015]

备注/Memo

备注/Memo:
作者简介: 陈汉武(1955—),男,博士,教授,博士生导师, hw_chen@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60572071)、江苏省自然科学基金资助项目(BK2005053,BM2006504,BK2007104)、江苏省高校自然科学基金资助项目(06KJB520137).
引文格式: 陈汉武,李志强,徐宝文.置换群与整数间一对一 Hash函数的构建[J].东南大学学报:自然科学版,2008,38(2):225-227.
更新日期/Last Update: 2008-03-20