350 rub
Journal Highly available systems №2 for 2012 г.
Article in number:
Jumping cellular automata (the results review)
Keywords: index terms - cellular automata jump cellular automata characteristic polynomial finite field the sylvester equation
Authors:
V.O. Drelikhov
Abstract:
Cellular automata serve as an example of linear automata, which can be implemented efficiently on the low-power computing devices. In this paper considered the concept of jump index of the linear automaton. The paper presents the methods overview for the synthesis of cellular automata with required jump index, and jumping cellular automata cascades also. The author proposes a new approach for solving the similarity matrix equation AX = XB on the field.
Pages: 57-62
References
  1. Колчин Д.А. Об одном методе построения каскадов «прыгающих» регистров сдвига // Материалы XVII Всеросс. школы-коллоквиума по стохастическим методам, посвященной 80-летию академика Ю.В. Прохорова. XI Всеросс. симпозиум по прикладной и промышленной математике. Кисловодск. 1-8 мая 2010 г. http://www.tvp.ru/confe-ren/vsppm11/kidag151.pdf
  2. Шестопал В.Е. Решение матричного уравнения АХ-ХВ=С // Математические заметки. Т. 19. 1976. №3. С. 449-451.
  3. Babbage S, Dodd M. Finding characteristic polynomials with jump indices. 2006.
  4. Babbage S.H., Dodd M.W. Streamciphers MICKEY and MICKEY-128, http://www.ecrypt.eu.org/stream.
  5. Bartels R.H., Stewart G.W. Solution of the matrix equation AX + XB = C, Comm. ACM. 15 (1972). P. 820-826.
  6. Boaz Tsaban. Efficient Linear Feedback Shift Registers with Maximal Period, Finite Fields and Their Applications 8. 2002. Р. 256-267.
  7. Cattell K. and Muzio J.C. An explicit similarity transform between cellular automata and LFSR matrices // Finite Fields Their Appl. Jul. 1998. V.4. №3.Р. 239-251.
  8. Cattell K. and Muzio J.C. Analysis of one-dimensional linear hybrid cellular automata over GF(q) // IEEE Trans. Comput. Jul. 1996.V. 45. №7. Р. 782-792.
  9. Cattell К. and Muzio J.C. Synthesis of one-dimensional linear hybrid cellular automata // IEEE Trans. Comput.-Aided Des. Integr.Circuits Syst. 1996.V.15. №3. Р.325-335.
  10. Chen C.L. Formulas for Solutions of Quadratic Equations over GF(2m) // IEEE Trans. Inform. Theory. 1982. V.28. №5.  P.792-794.
  11. Cid С., Gilbert Н., Johansson Т. "Cryptanalysis of Pomaranch", ECRYPT Stream Cipher Project Report 2005/060. 2005, http://www.ecrypt.eu.org/stream/
  12. Er-Chieh Ma. A finite series solution of the matrix equation AX −XB = C, S.I.A.M. J. on Appl. Math. 14 (1966). Р. 490-495.
  13. Jansen C.J.A. Partitions of polynomials: Stream ciphers based on jumping shift registers. In Cardinal J., Cerf N., Delgrange O., Markowitch O., eds.: 26th Symposium on Information Theory in the Benelux, Enschede, Werkgemeenschap voor Informatie en Communicatie theorie. 2005. Р. 277‑284.
  14. Jansen C.J.A. Stream cipher design based on jumping finite state machines. 2005.
  15. Serra M. and Slater T. A Lanczos algorithm in a finite field and its application // J. Comb. Math. Comb. Comput. 1990. V. 7.  Р. 11-32.
  16. Serra M., Cattell K., Zhang S., Muzio J.C., Miller D.M. One-Dimensional Linear Hybrid Cellular Automata: Their Synthesis, Properties and Applications to Digital Circuits Testing Dept. of Computer Science University of Victoria. Victoria, B.C., CanadaJanuary 27, 2009.
  17. Sung-Jin Cho, Un-Sook Choi, Han-Doo Kim, Yoon-Hee Hwang, Jin-Gyoung Kim, and Seong-Hun Heo. New Synthesis of One-Dimensional 90/150 Linear Hybrid Group Cellular Automata // IEEE trans. on computer-aided design of integrated circuits and systems. Sep., 2007.V. 26. №9. Р. 1720‑1724.