О периодах генераторов последовательностей матриц над конечными полями

Размещено на http://www.allbest.ru/

О периодах генераторов последовательностей матриц над конечными полями

Тарабрин Р.В.

Аннотация

В работе исследуются периоды генераторов последовательностей матриц над конечными полями, являющихся аналогами линейного конгруэнтного генератора и мультипликативного генератора Фибоначчи. В качестве умножения матриц в генераторах выбраны умножение, обеспечивающее выполнение аксиом кольца и йорданово. Установлены преимущества и недостатки изучаемых генераторов с точки зрения получения последовательностей большого периода. Для некоторых частных случаев предложены формулы поиска периодов.

Ключевые слова: рекуррентные последовательности, генераторы последовательностей, периоды последовательностей.

генератор последовательность матрица

Annotation

The study of the periods of generators of sequences of matrices over finite fields, which are analogs of a linear congruent generator and a multiplicative Fibonacci generator, is carried out. The article studies sequences of generators in which multiplication of matrices is chosen, which ensures the fulfillment of the axioms of the ring and Jordan multiplication. The advantages and disadvantages of the studied generators from the point of view of obtaining sequences of a long period are established. For some special cases, formulas for searching for periods are proposed.

Key words: linear congruential generator, Fibonacci generator, sequence periods.

Данная работа является продолжением изучения генераторов последовательностей элементов матричных алгебр Ли, описанных в публикациях [1-6]. В данных работах рассматриваются линейный конгруэнтный генератор и мультипликативный генератор Фибоначчи, которые генерируют последовательности, элементами которых являются квадратные матрицы над простыми конечными полями. В качестве умножения в таких генераторах рассматривается скобка Ли. В результате сравнения максимальных периодов генераторов установлено, что с помощью мультипликативных генераторов Фибоначчи можно получать последовательности с большим периодом, чем с помощью линейных конгруэнтных генераторов, но доля таких последовательностей среди всех возможных значительно меньше.

Кроме того, в статье [3] описываются установленные закономерности о значениях периодов последовательностей, вырабатываемых линейным конгруэнтным генератором, заключающиеся в том, что для квадратных матриц второго порядка максимальное значение периода получилось равным 2р, где р > 2. Для квадратных матриц третьего и четвёртого порядков максимальные значения периодов можно найти как рп -- 1.

В публикации [4] установлен ещё один факт об особенностях генераторов, согласно которому сужение области поиска от GLnQF к SLnQF при случайной генерации последовательностей не дает преимуществ в нахождении максимально возможных периодов. В большинстве случаев периоды остаются такими же, но также возможны и варианты, когда значения максимальных периодов уменьшаются.

Целью данной работы является изучение максимальных значений периодов для аналогов линейного конгруэнтного генератора и мультипликативного генератора Фибоначчи в случаях, когда в качестве умножения рассматривается операция, обеспечивающая выполнение аксиом кольца, а также йорданово умножение.

Для проведения исследования в системе компьютерной алгебре Sage написаны программы, реализующие генераторы с различными видами умножения и поиском их периодов. Результат работы программ - последовательность и значение её периода.

Вычислительный эксперимент заключался в случайной генерации комбинаций матриц-коэффициентов и начальных условий, получения на их основе последовательностей, поиске периодов получившихся последовательностей и дальнейшем выборе максимального из получающихся значений периодов.

Результаты поиска таких периодов для генераторов с умножением, обеспечивающим выполнение аксиом кольца, представлены в таблице 1. В данной таблице p является характеристикой поля, п означает порядок матриц. В ячейках представлены максимальные значения периодов, которые удалось достичь при случайной генерации последовательностей. Выбор максимально возможного периода происходил как наибольшего из полученных периодов.

В таблице 2 указано процентное соотношение найденных последовательностей с наибольшим периодом по отношению к числу всех сгенерированных последовательностей с заданными параметрами p и п.

Прочерк в таблицах означает, что периода за приемлемое время найти не удаётся.

Таблица 1.

Результаты поиска максимально возможных значений периодов последовательностей

Таблица 2.

Доля последовательностей с максимальным периодом (%)

Сравнивая получившиеся максимальные значения периодов, приходим к выводу, что мультипликативные генераторы Фибоначчи дают резкий рост максимальных значений периодов при увеличении значений характеристики поля и порядка матриц. При этом количество последовательностей, обладающих максимальным периодом, уменьшается при увеличении р и п. Итак, в случае умножения матриц, обеспечивающих выполнение аксиом кольца, мультипликативный генератор Фибоначчи обладает явным преимуществом при получении последовательностей с максимальными периодами.

Данные о значениях периодов последовательностей, вырабатываемых аналогом линейного конгруэнтного генератора, позволяют предполагать некоторые закономерности и делать предположения о зависимости максимальных значений периодов от характеристики поля и порядка матрицы. Например, для квадратных матриц второго порядка максимальное значение периода получилось равным (р -- 1)(р + 1), где р > 2. Для квадратных матриц третьего, четвёртого, пятого и шестого порядков можно заметить, что максимальные значения периодов есть рп -- 1.

Результаты поиска максимально возможных периодов для генераторов с йордановым умножением представлены в таблице 3, где введены такие же обозначения, как и в таблице 1. В таблице 4 указано процентное соотношение найденных последовательностей с наибольшим периодом по отношению к числу всех сгенерированных последовательностей с заданными параметрами p и п. Прочерк в таблицах означает, что периода за приемлемое время найти не удаётся.

Таблица 3.

Результаты поиска максимально возможных значений периодов

последовательностей

Таблица 4.

Доля последовательностей с максимальным периодом (%)

Сравнение результатов максимальных значений периодов последовательностей, вырабатываемых двумя различными генераторами, позволяет сделать предположение о том, что с помощью мультипликативных генераторов Фибоначчи с запаздыванием можно получать последовательности с большими периодами, нежели последовательности, вырабатываемые линейными конгруэнтными генераторами. Однако при этом доля таких последовательностей невелика.

Данные о значениях периодов последовательностей, вырабатываемых аналогом линейного конгруэнтного генератора, позволяют предполагать некоторые закономерности и делать предположения о зависимости максимальных значений периодов от характеристики поля и порядка матрицы. Например, для квадратных матриц второго порядка максимальное значение периода получилось равным 2р, где р > 2. Для квадратных матриц третьего порядка можно заметить, что максимальные значения периодов есть рп -- 1.

Сравнение генераторов по типу умножения матриц показывает, что у последовательностей, получающихся с помощью линейных конгруэнтных генераторов с умножением матриц, обеспечивающих выполнение аксиом кольца, максимальные значения периодов при одинаковых параметрах меньше, чем значения, получающиеся при йордановом произведении. С другой стороны, лучшие значения периодов мультипликативных генераторов Фибоначчи получаются в случае обычного умножения матриц.

Использованные источники

Благовисная, А.Н. Генераторы последовательностей элементов матричных алгебр Ли [Электронный ресурс] / А.Н. Благовисная, А.А. Белый // Университетский комплекс как региональный центр образования, науки и культуры: материалы Всерос. науч.-метод. конф. (с междунар. участием), 2527 янв. 2021 г., Оренбург / М-во науки и высш. образования Рос. Федерации, Федер. гос. бюджет. образоват. учреждение высш. образования «Оренбург. гос. ун-т». - Оренбург: ОГУ,2021. - С. 1584-1587.

Пихтилькова, О.А. О генераторах последовательностей матриц над конечным полем / О.А. Пихтилькова, Е.В. Мещерина, А.Н. Благовисная // Алгебра, теория чисел, дискретная геометрия и многомасштабное моделирование: современные проблемы, приложения и проблемы истории: материалы XIX Междунар. конф., посвящ. 200-летию со дня рождения акад. П.Л. Чебышева, 18-22 мая 2021 г., Тула / редкол.: В. Н. Чубариков [и др.]. - Электрон. дан. - Тула: ТГПУ им. Л.Н. Толстого,2021. - С. 135-137.

О генераторах последовательностей матриц над конечным полем / Е.В. Мещерина, О.А. Пихтилькова, А.Н. Благовисная, Л. Б. Усова, Д. У. Шакирова // Научно-технический вестник Поволжья,2021. - № 6. - С. 176-179.

О периодах последовательностей элементов алгебр Ли GLn(F) и SLn(F) / А.А. Белый, А.Н. Благовисная, Е.В. Мещерина, Р.В. Тарабрин // Актуальные проблемы интеграции науки и образования в регионе: материалы Всерос. науч.-практ. конф. (с междунар. участием), 20-21мая 2021г., Бузулук / М-во науки и высш. образования Рос. Федерации, Федер. гос. бюджет образоват учреждение высш. образования «Оренбург. гос. ун-т», Бузулук. гуманит.- технол. ин-т (фил.) ОГУ. - Бузулук: ОГУ,2021. - С. 219-223.

Мещерина, Е.В. О реализации генераторов последовательностей элементов матричных алгебр Ли [Электронный ресурс] / Е.В. Мещерина, А.А. Белый, А.Н. Благовисная // Евразийское научное объединение,2021. - № 4-1 (74). - С. 22-24.

Белый, А.А. О графических тестах исследования последовательностей элементов матричных алгебр Ли [Электронный ресурс] / А.А. Белый, А.Н. Благовисная // Университетский комплекс как региональный центр образования, науки и культуры: материалы Всерос. науч. -метод. конф. (с междунар. участием), Оренбург, 26-27 янв. 2022 г. / Оренбург. гос. ун-т; ред. А.В. Пыхтин. - Оренбург: ОГУ,2022. - С. 1260-1267.

Размещено на Allbest.ru/