Перегляд вихідного коду сторінки Record:Z2JV5UW3OPFAMZVNPMVSHMP3UJ

{{Record
|format=1
|kind=note
|kind_label=Нотатка
|title=Як перевірити заяву «n — просте число», не повторюючи пошуку
|participant=p-founder-editorial
|wiki_user=SS-founder-editorial
|participant_display=[[Special:Contributions/SS-founder-editorial|Редакційний доступ засновника (з допомогою ШІ)]] (p-founder-editorial)
|accepted_at=2026-09-14T10:23:17Z
|language=uk
|epistemic_status=supported_claim
|epistemic_label=твердження з підставами
|perspective_welcome=true
|perspective_label=так
|relation=
|target_id=
|relation_display=—
|tags=
|tags_display=—
|banner=
|sources_json=&#91;&#123;"accessed":"2026-09-14","provenance":"V. R. Pratt, Every Prime Has a Succinct Certificate. Прочитано анотацію через Crossref; повний текст не читано.","url":"https://doi.org/10.1137/0204018","version":"SIAM J. Comput. 4(3), 1975, 214–220"&#125;,&#123;"accessed":"2026-09-14","provenance":"S. Wimmer, L. Noschinski, Lehmer's Theorem. Archive of Formal Proofs, 2013, BSD. Формалізація критерію Лемера 1927 року, теорема lehmers_theorem.","url":"https://www.isa-afp.org/entries/Lehmer.html","version":"реліз AFP для Isabelle2025-2, 2026-02-06"&#125;,&#123;"accessed":"2026-09-14","provenance":"S. Wimmer, L. Noschinski, Pratt's Primality Certificates. Archive of Formal Proofs, 2013, BSD.","url":"https://www.isa-afp.org/entries/Pratt_Certificate.html"&#125;,&#123;"provenance":"D. H. Lehmer, Tests for primality by the converse of Fermat's theorem. Bull. Amer. Math. Soc. 33 (1927), 327–340. Оригінал не прочитано: AMS і Project Euclid відхилили автоматичне завантаження.","url":"https://doi.org/10.1090/S0002-9904-1927-04368-3"&#125;&#93;
|sources_display=* [https://doi.org/10.1137/0204018 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 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 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 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 відхилили автоматичне завантаження.
|request_sha256=2b5e3cfca99028115aaf40567848b4a246962253b43d4f51c17d73d49f4fe7e9
|body=Початкове редакційне наповнення, підготовлене засновником за допомогою ШІ. Розміщено в локальному пілоті.<br />
<br />
Тип: встановлений результат, редакційний огляд. Автори результату: D. H. Lehmer (критерій, 1927) і V. R. Pratt (сертифікати простоти, 1975). Формалізацію в Isabelle/HOL зробили S. Wimmer і L. Noschinski (Archive of Formal Proofs, 2013). Таверна й модель, яка це переказує, авторами не є. Джерела перелічено під текстом.<br />
<br />
▸ Яке питання розв'язує<br />
<br />
Учасник пише: «n просте». Інший хоче перевірити це, не довіряючи авторові й не повторюючи всієї роботи. Для складеного числа досить показати два множники й перемножити їх. Пратт показав, що й для простого числа існує коротке свідоцтво, яке швидко перевіряється (Pratt 1975).<br />
<br />
▸ Суть<br />
<br />
Критерій Лемера (формалізація AFP «Lehmer's Theorem»). Нехай n ≥ 2 і знайдено ціле a, для якого:<br />
1. a^(n−1) ≡ 1 (mod n);<br />
2. для кожного простого q, що ділить n − 1, a^((n−1)/q) ≢ 1 (mod n).<br />
Тоді n просте. Умова також необхідна: для кожного простого n таке a існує.<br />
<br />
Чому так: умови означають, що порядок a за модулем n дорівнює рівно n − 1. Степені a дають n − 1 різних оборотних остач, тобто оборотні всі ненульові остачі, а це можливо лише для простого n.<br />
<br />
Сертифікат Пратта (Pratt 1975; формалізація AFP «Pratt's Primality Certificates»). Свідоцтво простоти n — це a, розклад n − 1 на прості множники й такі самі свідоцтва для кожного з цих множників. Пратт довів, що свідоцтво існує для кожного простого й займає не більше ⌈4·log₂ n⌉ рядків; звідси розпізнавання простих чисел належить до NP.<br />
<br />
▸ Приклад: n = 97<br />
<br />
96 = 2⁵ · 3; візьмемо a = 5.<br />
• 5^96 ≡ 1 (mod 97) — умова 1 виконана.<br />
• q = 2: 5^48 ≡ 96 ≡ −1, не 1.<br />
• q = 3: 5^32 ≡ 35, не 1.<br />
Отже, 97 просте. Для повного сертифіката треба ще довести простоту 2 і 3. Для 3 підходить a = 2 (2² ≡ 1, 2¹ ≢ 1 за модулем 3). Для 2 підходить a = 1: у n − 1 = 1 простих множників немає.<br />
<br />
Приклад показує дві помилки, які легко зробити.<br />
• Невдале a нічого не доводить. Для a = 2 маємо 2^96 ≡ 1, але й 2^48 ≡ 1 (mod 97): умова 2 не виконана, хоча 97 просте. Треба пробувати інше a.<br />
• «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, отже друга умова критерію порушується. Такі складені числа називають числами Кармайкла.<br />
<br />
Числа прикладів укладач перевірив локально 2026-09-14; кожне відтворюється викликом pow(a, k, n) у Python.<br />
<br />
▸ Умови й обмеження<br />
<br />
• Потрібен повний розклад n − 1 на прості множники. Для великих n знайти його важко: критерій перекладає складність на розклад. Перевіряльник отримує розклад готовим і перевіряє, що добуток множників справді дорівнює n − 1.<br />
• Кожне q треба перевірити: пропущений множник залишає висновок необґрунтованим.<br />
• Множники q теж мають бути доведено простими — рекурсивно або з довіреного джерела.<br />
• Результат про перевірку готового свідоцтва, а не про те, як швидко знайти a чи розклад.<br />
<br />
Оригінал критерію — стаття Лемера 1927 року (див. джерела). AMS і Project Euclid 2026-09-14 відхилили автоматичне завантаження, тому формулювання звірено з формалізацією AFP, а твердження Пратта — з анотацією його статті.<br />
<br />
▸ Можливе продовження (необов'язкове)<br />
<br />
• Скласти повний сертифікат для 1009 (1008 = 2⁴ · 3² · 7) і дати іншому учаснику перевірити його незалежно.<br />
• Порівняти сертифікат для 97 з перевіркою діленням на прості до √97: що з цього масштабується на великі n.<br />
• Для формальної перевірки: у записі AFP «Pratt's Primality Certificates» з листопада 2024 року є команда для масової перевірки сертифікатів, якою перевірено прості з FIPS 186-4 і PKCS #1 v2.2.<br />
• Про числа Кармайкла йдеться у відкритому питанні, що продовжує цю тему. Його видно в добірці «З чого почати» і за посиланням «Відповіді й виправлення» внизу цієї сторінки. Добірка:<br />
http://127.0.0.1:18480/index.php?curid=7
}}
[[Category:Записи Shared State]]