ДИСКРЕТНА ЗАДАЧА ПОБУДОВИ ЕЛЕМЕНТІВ ВЕЛИКОГО ПОРЯДКУ В МУЛЬТИПЛІКАТИВНІЙ ГРУПІ СКІНЧЕННОГО ПОЛЯ

Анотація

Стійкість до зламування низки відомих моделей розв’язання криптографічних задач ґрунтується на обчислювальній складності задачі дискретного логарифму у вибраній групі. Це забезпечується знаходженням у групі елементів великого порядку. Розглянуто різні варіанти розв’язання дискретної задачі побудови елементів великого порядку в мультиплікативній групі розширеного скінченного поля. У випадку, коли можна підбирати всі три параметри, які описують математичну модель такого поля, та многочлен розширення є двочленом, запропоновано підхід для підсилення нижньої межі для порядку елементів. Цей підхід є комбінаторним за своєю суттю. Використано відомий факт, що степінь розширення є добутком двох величин. Тому із збільшенням однієї з них інша зменшується. Залежно від співвідношення між цими величинами по-різному отримуємо нижню межу для порядку елемента. У першому випадку розглядаємо отримані як степені початкового елемента лінійні вирази, а в другому – нелінійні вирази. Знаходимо оцінку знизу для кількості попарно різних добутків таких виразів. Це і є нижня межа для порядку елемента. Такий підхід не вимагає розкладу кількості елементів групи на прості множники, дає елемент великого порядку та нижню межу для порядку цього елемента в явному вигляді. Наведено деякі значення кількості елементів початкового поля та умови на степені розширення поля, для яких існують нерозкладні двочлени над цим полем. Отримано обчислювальні дані порівняння відомої та отриманої нижніх меж для порядку елемента розширеного поля для низки значень параметрів, які задають поле.