A number theoretic view on binary shift registers
Tóm tắt
We describe a number theoretic view on binary shift registers. We illustrate this approach on some basic shift registers by revisiting known and obtaining new results, which we prove using tools from basic number theory, including modular arithmetic.
Tài liệu tham khảo
Carlet, C., Goubin, L., Prouff, E., Quisquater, M., Rivain, M.: Higher-order masking schemes for s-boxes. In: Proceedings of FSE, LNCS, vol. 7549, pp. 366–384 (2012)
Elspas, B.: The theory of autonomous linear sequential networks. IRE Transactions on Circuit Theory, 45–60 (1959)
Fredricksen, H.: A survey of full length nonlinear shift register cycle algorithms. SIAM Review 24(2), 195–221 (1982)
Golomb, S.W.: Shift Register Sequences. Aegean Park Press (1981)
Hauge, E.R.: On the cycles and adjacencies in the complementary circulating register. Discrete Mathematics 145, 105–132 (1995)
Jansen, C.J.A., Franx, W.G., Boekee, D.E.: An efficient algorithm for the generation of DeBruijn cycles. IEEE Transaction on Information Theory 37(5), 1475–1478 (1991)
Lempel, A.: On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers. IEEE Transaction on Computers C–19(12), 1204–1209 (1970)
Magleby, K.B.: The synthesis of nonlinear feedback shift registers. Technical Report 6207-1, Stanford Electronics Laboratory (1963)
Mykkeltveit, J.: A proof of Golomb’s conjecture for the de Bruijn graph. Journal of Combinatorial Theory 13(1), 40–45 (1972)
Mykkeltveit, J.: Generating and counting the double adjacencies in a pure circulating shift register. IEEE Transactions on Computers C–24(3), 299–304 (1975)
Sloane, N.J.: On single-deletion-correcting codes. In: Codes and Designs, pp. 273–291 (2002)
Van Lantschoot, E.J.: Double adjacencies between cycles of a circulating shift register. IEEE Transactions on Computers C–22(10), 244–955 (1973)
Walker, E.A.: Non-linear recursive sequences. Canadian Journal of Math 11, 370–378 (1959)