Linearization Method and Linear Complexity

ISCAS OpenIR

	Linearization Method and Linear Complexity
	Hidema Tanaka
	2008
发表期刊	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
卷号	E91-A 期号:1 页码:22-29
摘要	We focus on the relationship between the linearization method and linear complexity and show that the linearization method is another effective technique for calculating linear complexity. We analyze its effectiveness by comparing with the logic circuit method. We compare the relevant conditions and necessary computational cost with those of the Berlekamp-Massey algorithm and the Games-Chan algorithm. The significant property of a linearization method is that it needs no output sequence from a pseudo-random number generator (PRNG) because it calculates linear complexity using the algebraic expression of its algorithm. When a PRNG has n [bit] stages (registers or internal states), the necessary computational cost is smaller than O(2n). On the other hand, the Berlekamp-Massey algorithm needs O(N2) where N ( 2n) denotes period. Since existing methods calculate using the output sequence, an initial value of PRNG influences a resultant value of linear complexity. Therefore, a linear complexity is generally given as an estimate value. On the other hand, a linearization method calculates from an algorithm of PRNG, it can determine the lower bound of linear complexity.
收录类别	其他
合作性质	其它
关键词	Algebraic Cryptanalysis Linear Complexity Linearization Method Pseudo-random Number Generator Stream Cipher
语种	英语
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/1367
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Hidema Tanaka. Linearization Method and Linear Complexity[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,2008,E91-A(1):22-29.
APA	Hidema Tanaka.(2008).Linearization Method and Linear Complexity.IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,E91-A(1),22-29.
MLA	Hidema Tanaka."Linearization Method and Linear Complexity".IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E91-A.1(2008):22-29.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
bj01151891.pdf（673KB）			开放获取	使用许可	请求全文