Рандомiзованi алгоритми перевiрки чисел на простоту

Автор(и)

  • Oleksandra Kozachok Київський національний університет імені Тараса Шевченка

DOI:

https://doi.org/10.18523/2617-70803202038-47

Ключові слова:

алгоритми, прост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зованих алгоритмiв перевiрки чисел на простоту, наводимо необхiднi теореми.

Біографія автора

Oleksandra Kozachok, Київський національний університет імені Тараса Шевченка

Студентка 3 курсу механiко-математичного факультету Київського нацiонального унiверситету iменi Тараса Шевченка. Сфера наукових iнтересiв — алгебра, теорiя чисел.

Посилання

Jr. Carl Pomerance, John L. Selfridge and Samuel S. Wagstaff, “The pseudoprimes to 25 · 109”, Mathematics of Computation. 151 (1980).

https://dx.doi.org/10.1090%2FS0025-5718- 1980-0572872-7.

Michael O. Rabin, “Probabilistic algorithm for testing primality”, Journal of Number Theory. 12 (1980). https://doi.org/10.1016%2F0022-314X%2880%2990084-0.

Song Y. Yan, Primality Testing and Integer Factorization in Public-Key Cryptography (Springer, 2009).

Cristian S. Calude, Information and Randomness: An Algorithmic Perspective (Springer, 2002).

Prabhakar Raghavan Rajeev Motwani, Randomized Algorithms (Cambridge University Press, 1995).

Juraj Hromkovic, Design and Analysis of Randomized Algorithms (Springer, 2005).

Ronald L. Rivest, Thomas H. Cormen, Charles E. Leiserson and Clifford Stein, Introduction to Algorithms (The MIT Press, 2009).

Eli Upfal and Michael Mitzenmacher, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (Cambridge University Press, 2017).

O. N. Vasilenko, Teoretiko-chislovyie algoritmy v kriptografii (MTsNMO, 2006).

Robert Baillie and Samuel Wagstaff, “Lucas Pseudoprimes”, Mathematics of Computation. 151 (1980). https://dx.doi.org/10.1090%2FS0025-5718-1980-0583518-6.

##submission.downloads##

Опубліковано

2021-02-24