Рандом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я чисел.

Посилання

  1. Jr. Carl Pomerance, John L. Selfridge and Samuel S. Wagstaff, “The pseudoprimes to 25 · 109”, Mathematics of Computation. 151 (1980).
  2. https://dx.doi.org/10.1090%2FS0025-5718- 1980-0572872-7.
  3. Michael O. Rabin, “Probabilistic algorithm for testing primality”, Journal of Number Theory. 12 (1980). https://doi.org/10.1016%2F0022-314X%2880%2990084-0.
  4. Song Y. Yan, Primality Testing and Integer Factorization in Public-Key Cryptography (Springer, 2009).
  5. Cristian S. Calude, Information and Randomness: An Algorithmic Perspective (Springer, 2002).
  6. Prabhakar Raghavan Rajeev Motwani, Randomized Algorithms (Cambridge University Press, 1995).
  7. Juraj Hromkovic, Design and Analysis of Randomized Algorithms (Springer, 2005).
  8. Ronald L. Rivest, Thomas H. Cormen, Charles E. Leiserson and Clifford Stein, Introduction to Algorithms (The MIT Press, 2009).
  9. Eli Upfal and Michael Mitzenmacher, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (Cambridge University Press, 2017).
  10. O. N. Vasilenko, Teoretiko-chislovyie algoritmy v kriptografii (MTsNMO, 2006).
  11. 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

Як цитувати

[1]
Kozachok, O. 2021. Рандомiзованi алгоритми перевiрки чисел на простоту. Могилянський математичний журнал. 3, (Лют 2021), 38–47. DOI:https://doi.org/10.18523/2617-70803202038-47.

Номер

Том 3 (2020): Могилянський математичний журнал

Розділ

Статті

Ліцензія

Авторське право (c) 2021 Oleksandra Kozachok

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Автори, які публікуються у цьому журналі, погоджуються з такими умовами:

а) Автори зберігають за собою авторські права на твір на умовах ліцензії Creative Commons Attribution License CC BY 4.0, котра дозволяє іншим особам вільно поширювати (копіювати і розповсюджувати матеріал у будь-якому вигляді чи форматі) та змінювати (міксувати, трансформувати, і брати матеріал за основу для будь-яких цілей, навіть комерційних) опублікований твір на умовах зазначення авторства.

б) Журнал дозволяє автору (авторам) зберігати авторські права без обмежень.

в) Автори мають право укладати самостійні додаткові угоди щодо поширення твору (наприклад, розміщувати роботу в електронному репозитарії), за умови збереження посилання на його першу публікацію. (Див. Політика Самоархівування)

г) Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у репозитаріях) тексту статті, як до подання його до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).