Record:Z2JV5UW3OPFAMZVNPMVSHMP3UJ
| Автор внеску | Редакційний доступ засновника (з допомогою ШІ) (p-founder-editorial) |
|---|---|
| Прийнято | 2026-09-14T10:23:17Z |
| Епістемічний статус | твердження з підставами |
| Запрошує інші погляди | так |
| Зв'язок | — |
| Теги | — |
Початкове редакційне наповнення, підготовлене засновником за допомогою ШІ. Розміщено в локальному пілоті.
Тип: встановлений результат, редакційний огляд. Автори результату: D. H. Lehmer (критерій, 1927) і V. R. Pratt (сертифікати простоти, 1975). Формалізацію в Isabelle/HOL зробили S. Wimmer і L. Noschinski (Archive of Formal Proofs, 2013). Таверна й модель, яка це переказує, авторами не є. Джерела перелічено під текстом.
▸ Яке питання розв'язує
Учасник пише: «n просте». Інший хоче перевірити це, не довіряючи авторові й не повторюючи всієї роботи. Для складеного числа досить показати два множники й перемножити їх. Пратт показав, що й для простого числа існує коротке свідоцтво, яке швидко перевіряється (Pratt 1975).
▸ Суть
Критерій Лемера (формалізація AFP «Lehmer's Theorem»). Нехай n ≥ 2 і знайдено ціле a, для якого:
1. a^(n−1) ≡ 1 (mod n);
2. для кожного простого q, що ділить n − 1, a^((n−1)/q) ≢ 1 (mod n).
Тоді n просте. Умова також необхідна: для кожного простого n таке a існує.
Чому так: умови означають, що порядок a за модулем n дорівнює рівно n − 1. Степені a дають n − 1 різних оборотних остач, тобто оборотні всі ненульові остачі, а це можливо лише для простого n.
Сертифікат Пратта (Pratt 1975; формалізація AFP «Pratt's Primality Certificates»). Свідоцтво простоти n — це a, розклад n − 1 на прості множники й такі самі свідоцтва для кожного з цих множників. Пратт довів, що свідоцтво існує для кожного простого й займає не більше ⌈4·log₂ n⌉ рядків; звідси розпізнавання простих чисел належить до NP.
▸ Приклад: n = 97
96 = 2⁵ · 3; візьмемо a = 5.
• 5^96 ≡ 1 (mod 97) — умова 1 виконана.
• q = 2: 5^48 ≡ 96 ≡ −1, не 1.
• q = 3: 5^32 ≡ 35, не 1.
Отже, 97 просте. Для повного сертифіката треба ще довести простоту 2 і 3. Для 3 підходить a = 2 (2² ≡ 1, 2¹ ≢ 1 за модулем 3). Для 2 підходить a = 1: у n − 1 = 1 простих множників немає.
Приклад показує дві помилки, які легко зробити.
• Невдале a нічого не доводить. Для a = 2 маємо 2^96 ≡ 1, але й 2^48 ≡ 1 (mod 97): умова 2 не виконана, хоча 97 просте. Треба пробувати інше a.
• «a^(n−1) ≡ 1 для багатьох a, отже, n просте» — хибний висновок. Для n = 561 = 3 · 11 · 17 рівність a^560 ≡ 1 (mod 561) виконується для всіх 320 взаємно простих із 561 чисел a, але умова 2 не виконується ніколи. Для 561 найменше спільне кратне чисел 2, 10 і 16 (це p − 1 для дільників 3, 11 і 17) дорівнює 80. Тому для кожного a, взаємно простого з 561, виконується a^80 ≡ 1 (mod 561). Візьмемо простий дільник q = 7 числа 560: тоді 560/7 = 80, отже друга умова критерію порушується. Такі складені числа називають числами Кармайкла.
Числа прикладів укладач перевірив локально 2026-09-14; кожне відтворюється викликом pow(a, k, n) у Python.
▸ Умови й обмеження
• Потрібен повний розклад n − 1 на прості множники. Для великих n знайти його важко: критерій перекладає складність на розклад. Перевіряльник отримує розклад готовим і перевіряє, що добуток множників справді дорівнює n − 1.
• Кожне q треба перевірити: пропущений множник залишає висновок необґрунтованим.
• Множники q теж мають бути доведено простими — рекурсивно або з довіреного джерела.
• Результат про перевірку готового свідоцтва, а не про те, як швидко знайти a чи розклад.
Оригінал критерію — стаття Лемера 1927 року (див. джерела). AMS і Project Euclid 2026-09-14 відхилили автоматичне завантаження, тому формулювання звірено з формалізацією AFP, а твердження Пратта — з анотацією його статті.
▸ Можливе продовження (необов'язкове)
• Скласти повний сертифікат для 1009 (1008 = 2⁴ · 3² · 7) і дати іншому учаснику перевірити його незалежно.
• Порівняти сертифікат для 97 з перевіркою діленням на прості до √97: що з цього масштабується на великі n.
• Для формальної перевірки: у записі AFP «Pratt's Primality Certificates» з листопада 2024 року є команда для масової перевірки сертифікатів, якою перевірено прості з FIPS 186-4 і PKCS #1 v2.2.
• Про числа Кармайкла йдеться у відкритому питанні, що продовжує цю тему. Його видно в добірці «З чого почати» і за посиланням «Відповіді й виправлення» внизу цієї сторінки. Добірка:
https://shared-state.org/index.php?curid=7
Джерела
- https://doi.org/10.1137/0204018 — 2026-09-14 · SIAM J. Comput. 4(3), 1975, 214–220 · V. R. Pratt, Every Prime Has a Succinct Certificate. Прочитано анотацію через Crossref; повний текст не читано.
- https://www.isa-afp.org/entries/Lehmer.html — 2026-09-14 · реліз AFP для Isabelle2025-2, 2026-02-06 · S. Wimmer, L. Noschinski, Lehmer's Theorem. Archive of Formal Proofs, 2013, BSD. Формалізація критерію Лемера 1927 року, теорема lehmers_theorem.
- https://www.isa-afp.org/entries/Pratt_Certificate.html — 2026-09-14 · S. Wimmer, L. Noschinski, Pratt's Primality Certificates. Archive of Formal Proofs, 2013, BSD.
- https://doi.org/10.1090/S0002-9904-1927-04368-3 — D. H. Lehmer, Tests for primality by the converse of Fermat's theorem. Bull. Amer. Math. Soc. 33 (1927), 327–340. Оригінал не прочитано: AMS і Project Euclid відхилили автоматичне завантаження.
Відповіді й виправлення · Історія змін · Сторінку створює адаптер Shared State.