Рандомізовані алгоритми перевiрки чисел на простоту
Loading...
Date
2020
Authors
Козачок, Олександра
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Рандомiзацiя та ймовiрнiсний пiдхiд у побудовi алгоритмiв займають помiтне мiсце. Через
обмеженiсть обчислювальних ресурсiв та складнiсть багатьох задач у деяких випадках отримати точнi результати є неможливим або занадто витратним, тому результати можуть
мiстити деяку невизначенiсть. Також у деяких випадках недетермiнованiсть алгоритму є його
перевагою, наприклад у задачах криптографiї, або корисною характеристикою, як-от у симуляцiях процесiв, що мiстять невизначенi параметри.
У цiй роботi ми розглядаємо основнi поняття та твердження, що стосуються рандомiзованих алгоритмiв перевiрки чисел на простоту, наводимо необхiднi теореми.
Randomization and probabilistic approach in the algorithms development occupy prominent place. Due to limited computing resources and complexity many tasks in some cases it’s impossible to obtain accurate results or it’s too costly, so the results may contain some uncertainty. There are also cases when the indeterminacy of the algorithm is its advantage, for example in cryptography problems, or a useful characteristic: in simulations of processes containing undefined parameters. In this paper, we consider the basic concepts and statements concerning randomized algorithms for checking numbers for simplicity, we present the necessary theorems.
Randomization and probabilistic approach in the algorithms development occupy prominent place. Due to limited computing resources and complexity many tasks in some cases it’s impossible to obtain accurate results or it’s too costly, so the results may contain some uncertainty. There are also cases when the indeterminacy of the algorithm is its advantage, for example in cryptography problems, or a useful characteristic: in simulations of processes containing undefined parameters. In this paper, we consider the basic concepts and statements concerning randomized algorithms for checking numbers for simplicity, we present the necessary theorems.
Description
Keywords
алгоритми, простi числа, рандомiзованi алгоритми, перевiрка чисел на простоту, стаття, algorithms, prime numbers, randomized algorithms, primality tests
Citation
Козачок О. Я. Рандомізовані алгоритми перевiрки чисел на простоту / Козачок О. Я. // Могилянський математичний журнал. - 2020. - Т. 3. - С. 38-47.