Задаволены

• Крок
• Спосаб 1 з 4: паспрабуйце падзяліць
• Спосаб 2 з 4: Выкарыстанне Маленькай тэарэмы Ферма
• Спосаб 3 з 4: Выкарыстанне тэсту Мілера-Рабіна
• Метад 4 з 4: Выкарыстанне кітайскай тэарэмы пра астатак
• Парады
• Неабходнасці

Простыя лікі - гэта лікі, якія дзеляцца толькі самі па сабе і называюцца 1 - іншымі лікамі злучэнне лічбы. Калі справа даходзіць да тэсту, ці з'яўляецца лік простым, ёсць некалькі варыянтаў. Некаторыя з гэтых метадаў адносна простыя, але зусім не практычныя для большай колькасці. Іншыя тэсты, якія часта выкарыстоўваюцца, на самай справе з'яўляюцца поўнымі алгарытмамі, заснаванымі на адным верагоднасць якія часам памылкова лічаць лік простым. Працягвайце крок 1, каб даведацца, як праверыць сябе, калі вы маеце справу з простым лікам.

Крок

Спосаб 1 з 4: паспрабуйце падзяліць

Спроба падзяліць - гэта самы просты спосаб праверыць лік. Для невялікіх лічбаў гэта звычайна таксама самы хуткі спосаб. Тэст заснаваны на вызначэнні простага ліку: лік просты, калі ён дзеліцца толькі на сябе і 1.

1. Дапусцім п нумар, які вы хочаце праверыць. Падзяліце лік n на ўсе магчымыя цэлыя лікі, якія дзеляцца. Для вялікіх лікаў, такіх як n = 101, надзвычай немэтазгодна дзяліць на любыя магчымыя цэлыя лікі, меншыя за n. На шчасце, ёсць некалькі хітрасцей, якія дазваляюць зменшыць колькасць фактараў, якія падлягаюць праверцы.
2. Вызначце, калі п нават. Усе цотныя лікі цалкам дзеляцца на 2. Такім чынам, калі n цотны, вы можаце гэта сказаць n - састаўны лік (і, такім чынам, не просты лік). Каб хутка вызначыць, цотны лік, вам трэба звярнуць увагу толькі на апошнюю лічбу. Калі апошняя лічба - 2, 4, 6, 8 ці 0, то лік цотны, а не просты.
   • Адзіным выключэннем з гэтага правіла з'яўляецца сам лік 2, які, паколькі ён дзеліцца сам на сябе, і 1, таксама з'яўляецца простым. 2 - адзінае цотнае простае.
3. Частка п на любы лік паміж 2 і n-1. Паколькі ў простага ліку няма аніякіх множнікаў, акрамя сябе і 1, а паколькі цэлыя фактары меншыя за іх здабытак, праверка дзялімасці цэлага ліку, меншага за n і большага за 2, вызначыць, ці з'яўляецца n простым. Мы пачынаем пасля 2, таму што цотныя лікі (кратныя 2) не могуць быць простымі лікамі. Як вы ўбачыце ніжэй, гэта далёка не эфектыўны спосаб тэставання.
   • Напрыклад, калі мы хацелі выкарыстаць гэты метад, каб праверыць, ці проста 11, мы падзялілі б 11 на 3, 4, 5, 6, 7, 8, 9 і 10, шукаючы цэлы лік без астатку. Паколькі ні адзін з гэтых лікаў цалкам не ўпісваецца ў 11, мы можам сказаць, што 11 - адзін з'яўляецца галоўным.
4. Каб зэканоміць час, правярайце толькі да sqrt (п), акруглена ўверх. Тэставанне ліку n, правяраючы ўсе лікі ад 2 да n-1, можа хутка заняць шмат часу. Напрыклад, калі мы хацелі праверыць, ці з'яўляецца 103 простым метадам, нам давялося б падзяліць на 3, 4, 5, 6, 7 ... і г.д., аж да 102! На шчасце, правяраць падобнае не трэба. На практыцы неабходна праверыць толькі фактары паміж 2 і квадратным коранем з n. Калі квадратны корань з n не з'яўляецца лікам, акругліце яго да бліжэйшага цэлага ліку і праверце на гэты лік. Глядзіце тлумачэнні ніжэй:
   • Давайце разгледзім фактары 100. 100 = 1 × 100, 2 × 50, 4 × 25, 5 × 20, 10 × 10, 20 × 5, 25 × 4, 50 × 2 і 100 × 1. Звярніце ўвагу, што пасля 10 × 10 фактары аднолькавыя калі гэта для 10 × 10, толькі потым перагарнуў. Увогуле, мы можам ігнараваць фактары n, большыя за sqrt (n), паколькі яны проста працягваюць фактары, меншыя за sqrt (n).
   • Давайце паспрабуем прыклад. Калі n = 37, тады нам не трэба правяраць усе лікі ад 3 да 36, каб вызначыць, ці з'яўляецца n простым. Замест гэтага нам проста трэба паглядзець лічбы паміж 2 і sqrt (37) (акруглена ўверх).
     • sqrt (37) = 6,08 - мы збіраемся акругляць гэта да 7.
     • 37 не цалкам дзеліцца на 3, 4, 5, 6 і 7, і таму мы можам упэўнена сцвярджаць, што ён адзін просты лік ёсць.
5. Каб зэканоміць яшчэ больш часу, мы выкарыстоўваем толькі простыя фактары. Можна зрабіць працэс тэставання, падзяліўшы яшчэ карацей, не улічваючы тых фактараў, якія не з'яўляюцца простымі лікамі. Па вызначэнні кожны састаўны лік можа быць выражаны як здабытак двух і больш простых лікаў. Такім чынам, дзяліць лік n на састаўны лік непатрэбна - гэта эквівалентна дзяленню на простыя лікі ў некалькі разоў. Такім чынам, мы можам яшчэ больш звузіць спіс магчымых фактараў толькі да простых лікаў, меншых за sqrt (n).
   • Гэта азначае, што ўсе цотныя фактары, а таксама множнікі, кратныя простым лікам, можна прапусціць.
   • Напрыклад, паспрабуем вызначыць, просты ці не 103. Квадратны корань з 103 роўны 11 (акругляецца ўверх). Простыя лікі паміж 2 і 11 - гэта 3, 5, 7 і 11. 4, 6, 8 і 10 цотныя, а 9 кратна 3, простае лік, таму мы можам яго прапусціць. Робячы гэта, мы скарацілі спіс магчымых фактараў да 4 лічбаў!
     • 103 не цалкам дзеліцца ні на 3, 5, 7, ні на 11, таму цяпер мы ведаем, што 103 - гэта адно просты лік ёсць.

Спосаб 2 з 4: Выкарыстанне Маленькай тэарэмы Ферма

У 1640 г. французскі матэматык П'ер дэ Ферма ўпершыню прапанаваў тэарэму (цяпер названую яго імем), якая можа быць вельмі карыснай для вызначэння таго, ці з'яўляецца лік простым. Тэхнічна тэст Ферма прызначаны для праверкі таго, што лік складаецца, а не проста. Гэта таму, што тэст можа паказаць з "абсалютнай упэўненасцю", што лік складаецца, але толькі "верагоднасць", што лік з'яўляецца простым. Маленькая тэарэма Ферма карысная ў сітуацыях, калі спроба падзяліць немэтазгодна і калі ёсць спіс нумароў, якія з'яўляюцца выключэннямі з тэарэмы.

1. Дапусцім п нумар прызначаны для тэставання. Вы выкарыстоўваеце гэты тэст, каб вызначыць, ці з'яўляецца дадзены лік n простым. Аднак, як ужо адзначалася вышэй, гэтая тэарэма можа часам памылкова характарызаваць некаторыя злучэнні як простыя. Важна прыняць гэта да ўвагі і праверыць свой адказ, які тлумачыцца ніжэй.
2. Выберыце цэлы лік а паміж 2 і п-1 (уключна). Дакладны ўвесь лік, які вы абралі, не важны. Паколькі параметры для a ўключаюць 2 і n-1, вы таксама можаце іх выкарыстоўваць.
   • Прыклад: 100 галоўных ці не. Дапусцім, возьмем 3 у якасці тэставага значэння - гэта паміж 2 і n-1, таму гэтага дастаткова.
3. вылічыць а (мод п). Для выпрацоўкі гэтага выразу неабходны пэўныя веды пра матэматычную сістэму модульная матэматыка. У модульнай матэматыцы лічбы вяртаюцца да нуля пры дасягненні пэўнага значэння, таксама вядомага як модуль. Вы можаце думаць пра гэта як пра гадзіннік: у рэшце рэшт стрэлка гадзінніка вернецца да 1 гадзіны пасля 12, а не да 13 гадзін. Модуль адзначаецца як (mod п). Такім чынам, на гэтым этапе вы вылічыце a з модулем n.
   • Іншы метад - вылічыць a, потым падзяліць яго на n, а потым выкарыстоўваць астатнюю частку ў якасці адказу. Спецыялізаваныя калькулятары з функцыяй модуля могуць быць вельмі карыснымі пры дзяленні вялікіх лікаў, таму што яны могуць адразу вылічыць астатнюю частку дзялення.
   • Выкарыстоўваючы такі калькулятар у нашым прыкладзе, мы бачым, што 3/100 мае рэшту 1. Такім чынам, 3 (мод 100) - гэта 1.
4. Калі мы разлічваем гэта ўручную, мы выкарыстоўваем паказчык ступені як кароткі фармат. Калі ў вас няма калькулятара з функцыяй модуля, выкарыстоўвайце абазначэнне з паказчыкам ступені, каб палегчыць працэдуру вызначэння астатняга. Глядзі ніжэй:
   • У нашым прыкладзе мы разлічваем 3 з модулем 100. 3 - вельмі і вельмі вялікая лічба - 515 377 520 732 031 331 036 461 129 765 621 272 702 107 522 001 - настолькі вялікая, што з ёй становіцца вельмі складана працаваць. Замест таго, каб выкарыстоўваць 48-значны адказ для 3, нам лепш запісаць яго як паказчык ступені (((((((3)*3))))*3)). Памятайце, што ўзвядзенне паказчыка ступені можа прывесці да множання паказчыкаў ((x) = x).
     • Цяпер мы можам вызначыць астатняе. Пачніце з рашэння (((((((3) * 3))))) * * 3)) ва ўнутраным наборы дужак і папраўцеся, падзяліўшы кожны крок на 100. Пасля таго, як мы знойдзем астатняе, мы будзем выкарыстоўваць гэта для наступнага кроку, а не для рэальнага адказу. Глядзі ніжэй:
       • (((((((9) * 3)))) * * 3)) - 9/100 не мае астачы, таму мы можам працягваць.
       • ((((((27)))) * 3)) - 27/100 не мае астатку, таму мы можам рухацца далей.
       • (((((729))) * 3)) - 729/100 = 7 R 29. Наш астатак - 29. Мы працягваем наступны крок, а не 729.
       • ((((29=841)) * 3)) - 841/100 = 8 R 41. Мы выкарыстоўваем наш астатак 41 на наступным этапе.
       • (((41 = 1681) * 3)) - 1681/100 = 16 R 81. Мы выкарыстоўваем наш астатак 81 на наступным этапе.
       • ((81*3 = 243)) - 243/100 = 2 R 43. Мы выкарыстаем наш астатак 43 на наступным этапе.
       • (43 = 1849) - 1849/100 = 18 R 49. Мы выкарыстаем наш астатак 49 на наступным этапе.
       • 49 = 2401 - 2401/100 = 24 R 1. наш канчатковы астатак - 1. Іншымі словамі, 3 (мод 100) = 1. Звярніце ўвагу, што гэта той самы адказ, які мы разлічылі на папярэднім этапе!
5. Даведайцеся, калі а (мод п) = а (мод п). Калі не, n - састаўны. Калі дакладна, то н напэўна, (але не ўпэўнены) просты лік. Паўтарэнне тэсту з рознымі значэннямі для можа зрабіць вынік больш пэўным, але ёсць рэдкія складаныя лікі, якія задавальняюць тэарэме Ферма для усе значэнні а. Яны называюцца лікамі Кармайкла - найменшы з іх - 561.
   • У нашым прыкладзе 3 (мод 100) = 1 і 3 (мод 100) = 3,1 ≠ 3, таму можна сказаць, што 100 - гэта састаўны лік.
6. Выкарыстоўвайце лічбы Кармайкла, каб быць упэўненымі ў сваім выніку. Веданне, якія лічбы адпавядаюць серыі Кармайкла, перш чым працягнуць, можа зэканоміць шмат клопатаў наконт таго, ці з'яўляецца лік простым. Увогуле, лікі Кармайкла - гэта здабытак асобных простых лікаў, дзе для ўсіх простых лікаў лічыцца, што калі p - дзельнік n, то таксама p-1 - дзельнік n-1. Інтэрнэт-спіс лікаў Кармайкла можа быць вельмі карысным для вызначэння таго, ці з'яўляецца лік простым, з дапамогай Малой тэарэмы Ферма.
   
   

Спосаб 3 з 4: Выкарыстанне тэсту Мілера-Рабіна

Тэст Мілера-Рабіна працуе гэтак жа, як і невялікая тэарэма Ферма, але лепш спраўляецца з нестандартнымі лікамі, такімі як лікі Кармайкла.

1. Дапусцім п гэта няцотная лічба, якую мы хочам праверыць на першаснасць. Як і ў метадах, указаных вышэй, n - зменная, для якой мы хочам вызначыць першаснасць.
2. Ціск п-1 у выглядзе 2 × d пры якім d няцотная. Лік n просты, калі няцотны. Такім чынам, n - 1 павінна быць цотным. Паколькі n - 1 цотны, яго можна запісаць як ступень у 2 разы, большую за няцотны лік. Такім чынам, 4 = 2 × 1; 80 = 2 × 5; і гэтак далей.
   • Дапусцім, мы хочам вызначыць, ці з'яўляецца n = 321 простым. 321 - 1 = 320, што мы можам выказаць як 2 × 5.
     • У гэтым выпадку n = 321 - прыдатны лік. Вызначэнне n - 1 пры n = 371 можа запатрабаваць вялікага значэння для d, што ўскладняе ўвесь працэс на познім этапе. 371 - 1 = 370 = 2 × 185
3. Выберыце любы нумар а паміж 2 і п-1. Выбранае дакладнае значэнне не мае значэння - проста яно павінна быць менш за n і больш за 1.
   • У нашым прыкладзе з n = 321 мы выбіраем a = 100.
4. вылічыць а (мод п). Калі а = 1 альбо -1 (мод п), затым праходзіць п тэст Мілера-Рабіна і ёсць напэўна просты лік. Як і ў выпадку з Малой тэарэмай Ферма, гэты тэст не можа з поўнай дакладнасцю вызначыць першаснасць ліку, але патрабуе дадатковых тэстаў.
   • У нашым прыкладзе з n = 321, a (mod n) = 100 (mod 321). 100 = 10 000 000 000 (мод 321) = 313. Мы выкарыстоўваем спецыяльны калькулятар альбо стэнаграфічны метад з паказчыкам ступені, як было апісана раней, каб знайсці астатнюю частку 100/321.
     • Паколькі мы не атрымалі 1 або -1, мы не можам з дакладнасцю сказаць, што n простае. Але нам трэба зрабіць яшчэ больш - чытайце далей.
5. Паколькі вынік не роўны 1 або -1, вылічыце а, а, ... і гэтак далей, аж да аd. Вылічыце паднятае да ступені d раз, да 2. Калі адно з гэтых роўна 1 або -1 (мод п), затым праходзіць п тэсты Мілера-Рабіна і, верагодна, галоўны. Калі вы вызначылі, што n праходзіць тэст, праверце свой адказ (гл. Крок ніжэй). Калі n не праходзіць любога з гэтых тэстаў, гэта адзін складзены нумар.
   • Нагадаем, у нашым прыкладзе значэнне а роўна 100, значэнне s роўна 6, а d роўна 5. Мы працягваем тэставанне, як паказана ніжэй:
     • 100 = 1 × 10.
       • 1 × 10 (мод 321) = 64,64 ≠’ 1 альбо -1. Працягвайце спакойна.
     • 100 = 1 × 10.
       • 1 × 10 (мод 321) = 244.244 ≠ 1 альбо -1.
     • На гэтым мы можам спыніцца. s - 1 = 6 - 1 = 5. Цяпер мы дасягнулі 4d = 2, і няма магутнасцей у 2 разы d ніжэй 5d. Паколькі ні адзін з нашых разлікаў не адказаў 1 або -1, мы можам сказаць, што n = 321 складзены нумар ёсць.
6. Калі п праходзіць тэст Мілера-Рабіна, паўтарыце для астатніх значэнняў а. Калі вы выявілі, што значэнне n можа быць простым, паспрабуйце яшчэ раз з іншым выпадковым значэннем, каб пацвердзіць вынік тэсту. Калі n на самай справе просты, гэта будзе дакладна для любога значэння a. Калі n - састаўны лік, ён не атрымаецца на тры чвэрці значэнняў a. Гэта дае вам большую ўпэўненасць, чым Малая тэарэма Ферма, дзе пэўныя састаўныя лікі (лікі Кармайкла) праходзяць тэст на любое значэнне а.

Метад 4 з 4: Выкарыстанне кітайскай тэарэмы пра астатак

1. Падбярыце два нумары. Адзін з лікаў не з'яўляецца простым, а другі - лік, які правяраецца на першаснасць.
   • "Тэст нумар1" = 35
   • Тэст нумар 2 = 97
2. Выберыце дзве кропкі дадзеных, большыя за нуль і менш за TestNumber1 і TestNumber2, адпаведна. Яны не могуць быць роўныя паміж сабой.
   • Дадзеныя1 = 1
   • Дадзеныя2 = 2
3. Разлічыце MMI (Матэматычны мультыплікатыўны адваротны) для тэсту Number1 і Test Number2
   • Разлічыце MMI
     • MMI1 = Тэст Нумар2 ^ -1 Мод Тэст Нумар1
     • MMI2 = Тэст Нумар1 ^ -1 Мод Тэст Нумар2
   • Толькі для простых лікаў (вынік атрымаецца і для няпростых лікаў, але гэта не MMI):
     • MMI1 = (TestNumber2 ^ (TestNumber1-2))% TestNumber1
     • MMI2 = (TestNumber1 ^ (TestNumber-2))% TestNumber2
   • Такім чынам:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
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
   • Вылічыце двайковы лагарыфм TestNumber1 - 2
     • 35 -2 = 33 (10001) база 2
     • MMI1 = F (33) = F (32) * F (1) мод 35
     • MMI1 = F (33) = 1 * 27 Мод 35
     • MMI1 = 27
   • Для MMI2
     • F (1) = нумар тэсту1% нумар тэсту2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Нумар тэсту2 = 35 * 35 мод 97 = 61
     • F (4) = F (2) * F (2)% Нумар тэсту2 = 61 * 61 мод 97 = 35
     • F (8) = F (4) * F (4)% Нумар тэсту2 = 35 * 35 мод 97 = 61
     • F (16) = F (8) * F (8)% Нумар тэсту2 = 61 * 61 мод 97 = 35
     • F (32) = F (16) * F (16)% Нумар тэсту2 = 35 * 35 мод 97 = 61
     • F (64) = F (32) * F (32)% Нумар тэсту2 = 61 * 61 мод 97 = 35
     • F (128) = F (64) * F (64)% Нумар тэсту2 = 35 * 35 мод 97 = 61
   • Вылічыце двайковы лагарыфм TestNumber2 - 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. Вылічыць (Data1 * TestNumber2 * MMI1 + Data2 * TestNumber1 * MMI2)% (TestNumber1 * TestNumber)
   • Адказ = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Адказ = (2619 + 4270)% 3395
   • Адказ = 99
6. Пераканайцеся, што "TestNumber1" не з'яўляецца простым1
   • Вылічыць (адказ - дадзеныя1)% Тэст нумар1
   • 99 -1 % 35 = 28
   • Паколькі 28 больш за 0, 35 не з'яўляецца простым
7. Праверце, ці з'яўляецца TestNumber2 простым
   • Вылічыць (адказ - дадзеныя2)% нумара тэсту2
   • 99 - 2 % 97 = 0
   • Паколькі 0 роўна 0, 97 з'яўляецца патэнцыяльным простым лікам
8. Паўтарыце крокі з 1 па 7 як мінімум яшчэ два разы.
   • Калі крок 7 роўны 0:
     • Выкарыстоўвайце іншы "TestNumber1", калі TestNumber1 не з'яўляецца простым.
     • Выкарыстоўвайце іншы TestNumber1, дзе TestNumber1 на самай справе просты. У гэтым выпадку крокі 6 і 7 роўныя 0.
     • Выкарыстоўвайце розныя кропкі дадзеных для data1 і data2.
   • Калі крок 7 заўсёды роўны 0, то верагоднасць таго, што лік 2 з'яўляецца простым лікам, вельмі вялікая.
   • Крокі з 1 па 7, як вядома, з'яўляюцца няправільнымі ў пэўных выпадках, калі першы лік не з'яўляецца простым, а другі - простым каэфіцыентам непростага ліку "Тэставы нумар1". Гэта працуе ва ўсіх сцэнарыях, калі абедзве лічбы простыя.
   • Прычына паўтарэння этапаў з 1 па 7 заключаецца ў тым, што ёсць некалькі сцэнарыяў, калі, нават калі TestNumber1 не просты, а TestNumber2 не просты, любая лічба з кроку 7 усё роўна роўная нулю. Гэтыя ўмовы сустракаюцца рэдка. Змяніўшы TestNumber1 на іншае непростае лік, калі TestNumber2 не просты, TestNumber2 больш не будзе роўны нулю на этапе 7. За выключэннем выпадку, калі "TestNumber1" з'яўляецца каэфіцыентам TestNumber2, простыя лікі заўсёды будуць роўныя нулю. Крок 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
• Калі спроба падзяліць павольней, чым больш складаныя метады, яна ўсё яшчэ эфектыўная для меншых лічбаў. Нават пры тэставанні большых лічбаў нярэдка спачатку праверыць малыя лічбы, перш чым пераходзіць на больш дасканалыя метады.

Неабходнасці

• Папера, ручка, аловак і / або калькулятар для распрацоўкі