The Algebraic Normal Form of Addition Mod 2n

摘要：

In 1, compact formulas are derived to represent the Algebraic Normal Form (ANF) of f(X + Y mod2n) and f(X*Y mod 2n) from the ANF of f, where f is a Boolean function with n variables and Y is a constant. In this paper, based on a property of the carry bits of addition mod 2n, we give a method to compute the ANFs of the n component Boolean functions of X+Y mod2n, with time complexity O(2n), where both X and Y are variables. The total time complexity O(2n) is much lower than O(2n 22n), which is the time complexity of the computation of the ANF of the highest bit of X + Y mod 2n by the classical algorithm 15 of computation of ANF of a Boolean function from the truth table.

关键词： ANF Algebraic Nor& Form addition mod2n

作者: Peng Changyong Zhu Yuefei

作者单位: Department of Network Engineering, Zhengzhou Information Science & Technology Institute,Zhengzhou, China.

会议类型: 国际会议

会议名称: 2010 International Conference on Information Security and Artificial Intelligence(2010年信息安全与人工智能国际会议 ISAI 2010)

会议地点: 成都

会议语种:英文

页码: 189-190

在线出版日期: 2010-12-17（万方平台首次上网日期，不代表论文的发表时间）