Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
М.В. СЕМОТЮК,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Українa,
semo@i.ua
Анотація. Стаття присвячена новому застосуванню теоретико-числових перетворень. Подання систем числення цими перетвореннями дає змогу створити принципово нові і ефективні алгоритми факторизації чисел, обчислення періоду показникової функції та дискретного логарифма. Алгоритм факторизації дозволяє за один прохід розкласти будь-який скінченний добуток на множники, він є точним тестом простоти чисел. Цей алгоритм ґрунтується на поданні систем числення теоретико-числовим перетворенням і не має аналогів, оскільки використовує тільки прості арифметичні дії. Властивості простоти чисел або інші властивості чисел не застосовуються. Отже, факторизація чисел, обчислення періоду показникової функції та дискретного логарифма є арифметичними операціями, що виконуються за скінченний час і належать до P-класу складності.
Ключові слова: множина, грані множини, алгебра, кільце лишків, модуль, аксіоматика цілих чисел, теоретико-числове перетворення, система числення, основа системи числення, факторизація, арифметична операція, період показникової функції, дискретний логарифм.
