Просты лік

Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі
Перайсьці да: навігацыі, пошуку

Просты лікнатуральны лік, які мае роўна 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, ёсьць O (n / \ln n). Для кожнага натуральнага n ёсьць просты лік p, ня меншы за n і ня большы за 2n (пастулат Бэртрана). У арыфмэтычнай прагрэсыі a, a + q, a + 2q, a + 3q,..., дзе a і q ўзаемна простыя, існуе бясконца шмат простых лікаў (тэарэма Дырыхле). Найбольшы вядомы зараз просты лік зьяўляецца лікам Мерсэна M24036583, у яго дзесятычным запісе 7235733 лічбаў.

Тэсты на простасьць[рэдагаваць | рэдагаваць крыніцу]

Самы просты мэтад пабудовы сьпісу простых лікаў да нейкага значэньня — рэшата Эратасфэна. Для задачы праверкі, ці зьяўляецца зададзены лік простым, доўгі час практычна ўжываліся толькі імавернасныя альгарытмы (напрыклад, тэст Мілера-Рабіна). У 2002 годзе быў знойдзены дэтэрмінаваны альгарытм полінаміяльнай складанасьці. Для больш вузкіх клясаў лікаў існуюць спэцыфічныя тэсты на простасьць (напрыклад, тэст Люка-Лемэра для лікаў Мерсэна).

Простыя лікі ў тэорыі групаў[рэдагаваць | рэдагаваць крыніцу]

Нявырашаныя пытаньні адносна простых лікаў[рэдагаваць | рэдагаваць крыніцу]

Практычнае выкарыстаньне[рэдагаваць | рэдагаваць крыніцу]

На практыцы простыя лікі ўжываюцца ў крыптасыстэмах з адкрытым ключом, у генэратарах псэўдавыпадковых пасьлядоўнасьцяў.


Простыя лікі Сафі Жэрмэн[рэдагаваць | рэдагаваць крыніцу]

Просты лік p называецца простым лікам Сафі Жэрмэн калі лік 2p + 1 таксама зьяўляецца простым. Гэтыя лікі прыцягнулі ўвагу, таму што Сафі Жэрмэн (Sophie Germain, француская вучоная-матэматык, 1 красавіка 177627 чэрвеня 1831)) даказала, што Апошняя тэарэма Фэрма выконваецца для такіх лікаў. Першыя простыя лікі Сафі Жэрмэн:

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, ...

Пасьлядоўнасьць {p, 2p + 1, 2(2p + 1) + 1, ...} простых лікаў Сафі Жэрмэн называецца ланцуг Канігана (Cunningham chain) першага парадку. Кожны элемэнт гэтай пасьлядоўнасьці (акрамя першага і апошняга) ёсьць адначасова просты лік Сафі Жэрмэн і бясьпечны просты (safe prime, гэта просты лік у выглядзе 2p + 1, дзе p таксама просты).
Глядзі таксама Простыя лікі Сафі Жэрмэн (па-ангельску).