HomeIssuesFeatures of maximal period polynomial generators over the Galois ring

Features of maximal period polynomial generators over the Galois ring | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 1 (27).

For a polynomial mapping over the Galois ring R = GR(q n,p n) with the cardinality q n and characteristic p n, the maximal length of a cycle equals q(q - 1)p n-2. In this paper, we present an algorithm for constructing the system of representatives of all maximal length cycles and an algorithm for constructing an element in a cycle of maximal length for a polynomial substitution f G R[x]. The complexity of the first algorithm equals d(q - 1)q n-1 multiplication operations and d(q - 1)q n-1 addition operations in R, the complexity of the second algorithm equals dq multiplication operations and dq addition operations in R where d = deg(f).
Download file
Counter downloads: 79
  • Title Features of maximal period polynomial generators over the Galois ring
  • Headline Features of maximal period polynomial generators over the Galois ring
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1 (27)
  • Date:
  • DOI
Keywords
Galois ring, nonlinear recurrent sequences, полиномиальный конгруэнтный генератор, псевдослучайные последовательности, нелинейные генераторы, кольца Галуа
Authors
References
Елизаров В. П. Конечные кольца. М.: Гелиос АРВ, 2006. 304с.
Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. М.: Гелиос АРВ, 2003. 749c.
Ермилов Д. М. О цикловой структуре биективных полиномиальных преобразований колец Галуа максимального периода // Обозрение прикл. и промышл. матем. 2013. Т. 20. Вып. 3.
Нечаев А. А. Полиномиальные преобразования конечных коммутативных колец главных идеалов // Матем. заметки. 1980. Т. 27. Вып. 6. С. 885-899.
Ермилов Д. М, Козлитин О. А. Цикловая структура полиномиального генератора над кольцом Галуа // Матем. вопросы криптографии. 2013. Т. 4. Вып. 1. С. 27-57.
Викторенков В. Е. Орграф полиномиального преобразования над коммутативным локальным кольцом // Обозрение прикл. и промышл. матем. 2000. Т. 7. Вып. 2. С. 327.
Анашин В. С. Равномерно распределенные последовательности целых -адических чисел // Дискретная математика. 2002. Т. 14. Вып. 4. С. 1-63.
Ларин М. В. Транзитивные полиномиальные преобразования колец вычетов // Дискретная математика. 2002. Т. 14. Вып. 2. C. 20-32.
Кнут Д. Искусство программирования. Т. 2. М.: Вильямс, 2000.
Carlitz L. Functions and polynomials (mod <sup>n</sup>) // Acta Arithm. 1964. No. 9. P. 66-78.
Анашин В. С. О группах и кольцах, обладающих транзитивными полиномами // XVI Всес. алгебраическая конф. Тезисы. Ч. II. Л., 1981. C.4-5.
Features of maximal period polynomial generators over the Galois ring | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 1 (27).
Features of maximal period polynomial generators over the Galois ring | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 1 (27).
Download full-text version
Counter downloads: 252