Просты лік — натуральны лік, які мае роўна 2 дзельнікі: самога сябе ды 1.
Лікі, што маюць больш за 2 дзельнікі, называюцца складовымі. Паводле асноўнае тэарэмы арыфмэтыкі, кожны лік, большы за 1, можна прадставіць у выглядзе здабытку простых лікаў, прытым толькі адным спосабам (ня ўлічваючы перастаноўкі множнікаў).
Пачатак пасьлядоўнасьці простых лікаў: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113... Простых лікаў бясконца шмат (даказаў Эўклід: хай колькасьць простых лікаў канечная, але тады ніводзін зь іх ня дзеліць іх здабытак плюс 1, што немагчыма). Леанард Ойлер паказаў, што сума лікаў, адваротных простым, разьбягаецца. Вядома, што колькасьць простых лікаў, меншых за n, ёсьць . Для кожнага натуральнага n ёсьць просты лік p, ня меншы за n і ня большы за 2n (пастулат Бэртрана). У арытмэтычнай прагрэсіі a, a + q, a + 2q, a + 3q,..., дзе a і q узаемна простыя, існуе бясконца шмат простых лікаў (тэарэма Дырыхле). Найбольшы вядомы цяпер просты лік зьяўляецца лікам Мэрсэна M24036583, у яго дзесятковым запісе 7235733 лічбаў.
Самы просты мэтад пабудовы сьпісу простых лікаў да нейкага значэньня — рэшата Эратасфэна. Для задачы праверкі, ці зьяўляецца зададзены лік простым, доўгі час практычна ўжываліся толькі імавернасныя альгарытмы (напрыклад, тэст Мілера-Рабіна). У 2002 годзе быў знойдзены дэтэрмінаваны альгарытм полінаміяльнай складанасьці. Для больш вузкіх клясаў лікаў існуюць спэцыфічныя тэсты на простасьць (напрыклад, тэст Люка-Лемэра для лікаў Мерсэна).
На практыцы простыя лікі ўжываюцца ў крыптасыстэмах з адкрытым ключом, у генэратарах псэўдавыпадковых пасьлядоўнасьцяў.
Просты лік p называецца простым лікам Сафі Жэрмэн калі лік 2p + 1 таксама зьяўляецца простым. Гэтыя лікі прыцягнулі ўвагу, таму што Сафі Жэрмэн (Sophie Germain, француская вучоная-матэматык, 1 красавіка 1776 — 27 чэрвеня 1831)) даказала, што Апошняя тэарэма Фэрма выконваецца для такіх лікаў. Першыя простыя лікі Сафі Жэрмэн:
Пасьлядоўнасьць {p, 2p + 1, 2(2p + 1) + 1, ...}
простых лікаў Сафі Жэрмэн называецца ланцуг Канігана (Cunningham chain) першага парадку. Кожны элемэнт гэтай пасьлядоўнасьці (акрамя першага і апошняга) ёсьць адначасова просты лік Сафі Жэрмэн і бясьпечны просты (safe prime, гэта просты лік у выглядзе 2p + 1
, дзе p таксама просты).
Просты лік — сховішча мультымэдыйных матэрыялаў
This article uses material from the Wikipedia Беларуская (тарашкевіца) article Просты лік, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Зьмест даступны на ўмовах CC BY-SA 4.0, калі не пазначанае іншае. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Беларуская (тарашкевіца) (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.