Задаволены

• крокі
• Частка 1 з 3: Тесты прастаты
• Частка 2 з 3: Як працуюць тэсты прастаты
• Частка 3 з 3: Выкарыстанне кітайскай тэарэмы аб астатках
• парады
• Што вам спатрэбіцца

Простыя лікі - гэта лікі, якія дзеляцца толькі на сябе і на 1. Усе астатнія колькасці называюцца складовымі лікамі. Ёсць мноства спосабаў вызначыць, ці з'яўляецца лік простым, і ўсе яны маюць свае перавагі і недахопы. З аднаго боку, некаторыя метады адрозніваюцца вялікай дакладнасцю, але яны даволі складаныя, калі вы маеце справу з вялікімі лікамі. З іншага боку, існуюць нашмат больш хуткія спосабы, але яны могуць прывесці да няправільным вынікаў. Выбар падыходнага метаду залежыць ад таго, з наколькі вялікімі лікамі вы працуеце.

крокі

Частка 1 з 3: Тесты прастаты

Заўвага: ва ўсіх формулах n пазначае правяраеце лік.

1. 1 Перабор дзельнікаў. дастаткова падзяліць n на ўсе простыя лікі ад 2 да акруглення значэння (${ Displaystyle { sqrt {n}}}$).
2. 2 Малая тэарэма Ферма. Папярэджанне: часам тэст ілжыва ідэнтыфікуе складовыя колькасці як простыя, нават для ўсіх велічынь a.
   • Абярэм цэлае лік a, Такое што 2 ≤ a ≤ n - 1.
   • Калі a (mod n) = a (mod n), то лік, верагодна, простае. Калі роўнасць не выконваецца, лік n з'яўляецца састаўным.
   • Праверце дадзенае роўнасць для некалькіх значэнняў a, Каб павялічыць верагоднасць таго, што правяраючыя лік сапраўды з'яўляецца простым.
3. 3 Тэст Мілера-Рабіна. Папярэджанне: часам, хоць і рэдка, для некалькіх значэнняў a тэст ілжыва ідэнтыфікуе складовыя колькасці як простыя.
   • Знайдзіце велічыні s і d, такія каб ${ Displaystyle n-1 = 2 ^ {s} * d}$.
   • Выберыце цэлы лік a у інтэрвале 2 ≤ a ≤ n - 1.
   • Калі a = +1 (mod n) або -1 (mod n), то n, верагодна, з'яўляецца простым лікам. У гэтым выпадку перайдзіце да выніку тэсту. Калі роўнасць не выконваецца, перайдзіце да наступнага кроку.
   • Узьвядзеце адказ у квадрат (${ Displaystyle a ^ {2d}}$). Калі атрымаецца -1 (mod n), то n, верагодна, простае лік. У гэтым выпадку перайдзіце да выніку тэсту. Калі роўнасць не выконваецца, паўторыце (${ Displaystyle a ^ {4d}}$ і гэтак далей) да ${ Displaystyle a ^ {2 ^ {s-1} d}}$.
   • Калі на нейкім этапе пасля ўзвядзення ў квадрат колькасці, выдатнага ад ${ Displaystyle pm 1}$ (Mod n), у вас атрымалася +1 (mod n), значыць n з'яўляецца састаўным лікам. Калі ${ Displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (Mod n), то n не з'яўляецца простым лікам.
   • Вынік тэсту: калі n прайшло тэст, паўтарыце яго для іншых значэнняў a, Каб павысіць ступень пэўнасці.

Частка 2 з 3: Як працуюць тэсты прастаты

1. 1 Перабор дзельнікаў. Па вызначэнні лік n з'яўляецца простым толькі ў тым выпадку, калі яно не дзеліцца без астатку на 2 і іншыя цэлыя лікі, акрамя 1 і самога сябе. Прыведзеная вышэй формула дазваляе выдаліць непатрэбныя крокі і зэканоміць час: напрыклад, пасля праверкі таго, дзеліцца Ці лік на 3, няма неабходнасці правяраць, дзеліцца яно на 9.
   • Функцыя floor (x) акругляе лік x да бліжэйшага цэлага ліку, якое менш або роўна x.
2. 2 Даведайцеся аб модульнай арыфметыцы. Аперацыя "x mod y" (mod з'яўляецца скарачэннем лацінскага слова "modulo", гэта значыць "модуль") азначае "падзяліць x на y і знайсці рэшту". Іншымі словамі, у модульнай арыфметыцы па дасягненні вызначанай велічыні, якую называюць модулем, Колькасці ізноў "ператвараюцца" у нуль. Напрыклад, гадзіны адлічваюць час з модулем 12: яны паказваюць 10, 11 і 12 гадзін, а затым вяртаюцца да 1.
   • У многіх калькулятарах ёсць клавіша mod. У канцы дадзенага раздзела паказана, як уручную вылічаць гэтую функцыю для вялікіх лікаў.
3. 3 Даведайцеся пра падводных камянях малой тэарэмы Ферма. Ўсе лікі, для якіх не выконваюцца ўмовы тэсту, з'яўляюцца складовымі, аднак астатнія колькасці толькі верагодна ставяцца да простых. Калі вы хочаце пазбегнуць няверных вынікаў, пашукайце n у спісе "лікаў Кармайкл" (складовых лікаў, якія задавальняюць дадзеным тэсту) і "псевдопростых лікаў Ферма" (гэтыя лікі адпавядаюць умовам тэсту толькі пры некаторых значэннях a).
4. 4 Калі зручна, выкарыстоўвайце тэст Мілера-Рабіна. Хоць дадзены метад даволі грувасткі пры вылічэннях ўручную, ён часта выкарыстоўваецца ў кампутарных праграмах. Ён забяспечвае прымальную хуткасць і дае менш памылак, чым метад Ферма. Складовае лік не будзе прынята за простае, калі правесці разлікі для больш ¼ значэнняў a. Калі вы выпадковым спосабам вылучыце розныя значэнні a і для ўсіх іх тэст дасць станоўчы вынік, можна з досыць высокай доляй упэўненасці лічыць, што n з'яўляецца простым лікам.
5. 5 Для вялікіх лікаў выкарыстоўвайце модульную арыфметыку. Калі ў вас пад рукой няма калькулятара з функцыяй mod або калькулятар не разлічаны на аперацыі з такімі вялікімі лікамі, выкарыстоўвайце ўласцівасці ступеняў і модульную арыфметыку, каб палегчыць вылічэнні. Ніжэй прыведзены прыклад для ${ Displaystyle 3 ^ {50}}$ mod 50:
   • Перапішыце выраз у больш зручным выглядзе: ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Пры разліках ўручную могуць спатрэбіцца далейшыя спрашчэння.
   • ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ Displaystyle (3 ^ {25}}$ mod 50 ${ Displaystyle * 3 ^ {25}}$ mod 50) mod 50. Тут мы ўлічылі ўласцівасць модульнага множання.
   • ${ Displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ Displaystyle (3 ^ {25}}$ mod 50 ${ Displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ Displaystyle (43 * 43)}$ mod 50.
   • ${ Displaystyle = 1849}$ mod 50.
   • ${ Displaystyle = 49}$.

Частка 3 з 3: Выкарыстанне кітайскай тэарэмы аб астатках

1. 1 Выберыце два ліку. Адно з лікаў павінна быць састаўным, а другое - як раз тое, прастату якога вы хочаце праверыць.
   • Число1 = 35
   • Число2 = 97
2. 2 Выберыце два значэння, якія больш за нуль і адпаведна менш лікаў Число1 і Число2. Гэтыя значэнні не павінны супадаць адзін з адным.
   • Значение1 = 1
   • Значение2 = 2
3. 3 Вылічыце MMI (матэматычную мультпликативную інверсію) для Числа1 і Числа2.
   • Вылічыце MMI
     • MMI1 = Число2 ^ -1 Mod Число1
     • MMI2 = Число1 ^ -1 Mod Число2
   • Толькі для простых лікаў (гэта дасць лік для складовых лікаў, але яно не будзе яго MMI):
     • MMI1 = (Число2 ^ (Число1-2))% Число1
     • MMI2 = (Число1 ^ (Число2-2))% Число2
   • напрыклад:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Стварыце табліцу для кожнай MMI аж да модуляў log2:
   • для MMI1
     • F (1) = Число2% Число1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Число1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Число1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Число1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Число1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Число1 = 1 * 1% 35 = 1
   • Вылічыце парныя Число1 - 2
     • 35 -2 = 33 (10001) па падставе 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • для MMI2
     • F (1) = Число1% Число2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Число2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Число2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Число2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Число2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Число2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Число2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Число2 = 35 * 35 mod 97 = 61
   • Вылічыце парныя Число2 - 2
     • 97 - 2 = 95 = (1011111) па падставе 2
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Вылічыце (Значение1 * Число2 * MMI1 + Значение2 * Число1 * MMI2)% (Число1 * Число2)
   • Адказ = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Адказ = (2619 + 4270)% 3395
   • Адказ = 99
6. 6 Праверце, што Число1 не з'яўляецца простым
   • Вылічыце (Адказ - Значение1)% Число1
   • 99 – 1 % 35 = 28
   • Так як 28 больш 0, то 35 не з'яўляецца простым лікам.
7. 7 Праверце, што Число2 з'яўляецца простым.
   • Вылічыце (Адказ - Значение2)% Число2
   • 99 – 2 % 97 = 0
   • Бо 0 роўны 0, то 97 - хутчэй за ўсё простае лік.
8. 8 Паўтарыце крокі з 1 па 7 па меншай меры яшчэ два разы.
   • Калі за крок 7 атрымліваецца 0:
     • Выкарыстоўвайце іншае Число1, калі Число1 не з'яўляецца простым.
     • Выкарыстоўвайце іншае Число1, калі Число1 з'яўляецца простым. У гэтым выпадку ў кроках 6 і 7 павінен атрымацца 0.
     • Выкарыстоўвайце іншыя Значение1 і Значение2.
   • Калі за крок 7 вы ўвесь час атрымліваеце 0, то з вельмі вялікай верагоднасцю Число2 з'яўляецца простым.
   • Крокі з 1 па 7 могуць прывесці да памылкі, калі Число1 не з'яўляецца простым, а Число2 з'яўляецца дзельнікам Числа1. Апісаны метад працуе ва ўсіх выпадках, калі абодва колькасці з'яўляюцца простымі.
   • Прычына, па якой неабходна паўтараць крокі з 1 па 7, заключаецца ў тым, што ў некаторых выпадках, нават калі Число1 і Лічба 2 не зьяўляюцца простымі, за крок 7 вы атрымаеце 0 (для адной або абедзвюх лікаў). Гэта здараецца рэдка.Трэба выбраць іншае Число1 (складовае), і калі Число2 не з'яўляецца простым, тады Число2 не будзе роўна нулю за крок 7 (за выключэннем выпадку, калі Число1 з'яўляецца дзельнікам Числа2 - тут простыя лікі заўсёды будуць роўныя нулю за крок 7).

парады

• Простыя лікі ад 168 да 1000: 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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Хоць пры працы з вялікімі лікамі перабор дзельнікаў з'яўляецца працаёмкім спосабам праверкі, ён даволі эфектыўны ў выпадку малых лікаў. Нават у выпадку вялікіх лікаў пачынаюць з тэставання малых дзельнікаў, а затым пераходзяць да больш складаным метадам праверкі прастаты лікаў (калі малыя дзельнікі не знойдзены).

Што вам спатрэбіцца

• Папера, ручка або кампутар