Садржај

• Кораци
• 1. део од 3: Тестови једноставности
• 2. део 3: Како тестови једноставности функционишу
• 3. део 3: Коришћење кинеске теореме остатака
• Савјети
• Шта ти треба

Прости бројеви су бројеви који су дељиви само са собом и са 1. Сви остали бројеви називају се сложени бројеви. Постоји много начина да се утврди да ли је број прост, а сви имају своје предности и недостатке. С једне стране, неке од метода су врло тачне, али су прилично сложене ако се бавите великим бројевима. С друге стране, постоје много бржи начини, али они могу довести до нетачних резултата. Избор одговарајуће методе зависи од тога са колико великих бројева радите.

Кораци

1. део од 3: Тестови једноставности

Белешка: у свим формулама н означава број који треба проверити.

1. 1 Набрајање делилаца. Довољно је поделити н на све просте бројеве од 2 до заокружене вредности (${ дисплаистиле { скрт {н}}}$).
2. 2 Ферматова мала теорема. Упозорење: понекад ће тест лажно идентификовати сложене бројеве као просте, чак и за све вредности а.
   • Изаберимо цео број атако да 2 ≤ а ≤ н - 1.
   • Ако је а (мод н) = а (мод н) онда је број вероватно прост. Ако једнакост није задовољена, број н је сложен.
   • Проверите дату једнакост за више вредности акако би се повећала вероватноћа да је број који се тестира заиста прост.
3. 3 Миллер-Рабин тест. Упозорење: понекад, иако ретко, за више вредности а, тест ће лажно идентификовати сложене бројеве као просте.
   • Нађи количине с и д такве да ${ дисплаистиле н-1 = 2 ^ {с} * д}$.
   • Изаберите цео број а у опсегу 2 ≤ а ≤ н - 1.
   • Ако је а = +1 (мод н) или -1 (мод н), онда је н вероватно прост. У том случају идите на резултат теста. Ако једнакост не важи, пређите на следећи корак.
   • Уоквирите свој одговор (${ дисплаистиле а ^ {2д}}$). Ако добијете -1 (мод н), онда је н вероватно прост број. У том случају идите на резултат теста. Ако једнакост не успе, поновите (${ дисплаистиле а ^ {4д}}$ и тако даље) до ${ дисплаистиле а ^ {2 ^ {с-1} д}}$.
   • Ако у неком кораку након квадрата број осим ${ дисплаистиле пм 1}$ (мод н), добили сте +1 (мод н), тако да је н композитни број. Ако ${ дисплаистиле а ^ {2 ^ {с-1} д} нек пм 1}$ (мод н), тада н није прост.
   • Резултат теста: ако н прође тест, поновите га за остале вредности ада се повећа самопоуздање.

2. део 3: Како тестови једноставности функционишу

1. 1 Набрајање делилаца. По дефиницији, број н је једноставан само ако није дељив са 2 и другим целим бројевима осим 1 и самим собом. Горња формула вам омогућава да уклоните непотребне кораке и уштедите време: на пример, након провере да ли је број дељив са 3, нема потребе да проверавате да ли је дељив са 9.
   • Функција флоор (к) заокружује к на најближи цео број мањи или једнак к.
2. 2 Сазнајте више о модуларној аритметици. Операција „к мод и“ (мод је скраћеница од латинске речи „модуло“, односно „модул“) значи „подели к са и и пронађе остатак“. Другим речима, у модуларној аритметици, по достизању одређене вредности, која се назива модул, бројеви се поново "окрећу" на нулу. На пример, сат одбројава са модулом 12: приказује 10, 11 и 12 сати, а затим се враћа на 1.
   • Многи калкулатори имају кључ за мод. На крају овог одељка приказано је како ручно израчунати ову функцију за велике бројеве.
3. 3 Сазнајте о замкама Ферматове мале теореме. Сви бројеви за које нису испуњени услови испитивања су сложени, али остали бројеви су само вероватно су једноставне. Ако желите да избегнете нетачне резултате, претражите н на листи "Цармицхаел бројеви" (сложени бројеви који задовољавају овај тест) и "Ферматови псеудоприме бројеви" (ови бројеви испуњавају услове испитивања само за неке вредности а).
4. 4 Ако је згодно, користите Миллер-Рабинов тест. Иако је ова метода прилично гломазна за ручне прорачуне, често се користи у рачунарским програмима. Омогућава прихватљиву брзину и мање грешака од Ферматове методе. Сложени број се неће узети као прост број ако се прорачуни изводе за више од ¼ вредности а... Ако насумично изаберете различите вредности а и за све њих тест ће дати позитиван резултат, са прилично високим степеном поуздања можемо претпоставити да н је прост број.
5. 5 За велике бројеве користите модуларну аритметику. Ако немате при руци калкулатор модова или калкулатор није дизајниран за руковање тако великим бројевима, употријебите својства напајања и модуларну аритметику како бисте олакшали прорачуне. Испод је пример за ${ дисплаистиле 3 ^ {50}}$ мод 50:
   • Препишите израз у прикладнији облик: ${ дисплаистиле (3 ^ {25} * 3 ^ {25})}$ мод 50. Ручни прорачуни могу захтевати додатна поједностављења.
   • ${ дисплаистиле (3 ^ {25} * 3 ^ {25})}$ мод 50 = ${ дисплаистиле (3 ^ {25}}$ мод 50 ${ дисплаистиле * 3 ^ {25}}$ мод 50) мод 50. Овде смо узели у обзир својство модуларног множења.
   • ${ дисплаистиле 3 ^ {25}}$ мод 50 = 43.
   • ${ дисплаистиле (3 ^ {25}}$ мод 50 ${ дисплаистиле * 3 ^ {25}}$ мод 50) мод 50 = ${ дисплаистиле (43 * 43)}$ мод 50.
   • ${ дисплаистиле = 1849}$ мод 50.
   • ${ дисплаистиле = 49}$.

3. део 3: Коришћење кинеске теореме остатака

1. 1 Одаберите два броја. Један од бројева мора бити састављен, а други мора бити управо онај који желите да тестирате ради једноставности.
   • Број1 = 35
   • Број2 = 97
2. 2 Изаберите две вредности које су веће од нуле, односно мање од бројева Нумбер1 и Нумбер2. Ове вредности не смеју бити исте.
   • Вредност1 = 1
   • Вредност2 = 2
3. 3 Израчунајте ММИ (математички мултипликативни инверз) за број 1 и број 2.
   • Израчунајте ММИ
     • ММИ1 = Број2 ^ -1 Мод Број1
     • ММИ2 = Број1 ^ -1 Мод Број2
   • Само за просте бројеве (ово ће дати број за сложене бројеве, али то неће бити његов ММИ):
     • ММИ1 = (Број2 ^ (Број 1-2))% Број1
     • ММИ2 = (Број1 ^ (Број2-2))% Број2
   • На пример:
     • ММИ1 = (97 ^ 33)% 35
     • ММИ2 = (35 ^ 95)% 97
4. 4 Направите табелу за сваки ММИ до лог2 модула:
   • За ММИ1
     • Ф (1) = Број2% Број1 = 97% 35 = 27
     • Ф (2) = Ф (1) * Ф (1)% Број1 = 27 * 27% 35 = 29
     • Ф (4) = Ф (2) * Ф (2)% Број1 = 29 * 29% 35 = 1
     • Ф (8) = Ф (4) * Ф (4)% Број1 = 1 * 1% 35 = 1
     • Ф (16) = Ф (8) * Ф (8)% Број1 = 1 * 1% 35 = 1
     • Ф (32) = Ф (16) * Ф (16)% Број1 = 1 * 1% 35 = 1
   • Израчунајте упарене бројеве 1 - 2
     • 35 -2 = 33 (10001) база 2
     • ММИ1 = Ф (33) = Ф (32) * Ф (1) мод 35
     • ММИ1 = Ф (33) = 1 * 27 мод 35
     • ММИ1 = 27
   • За ММИ2
     • Ф (1) = Број1% Број2 = 35% 97 = 35
     • Ф (2) = Ф (1) * Ф (1)% Број2 = 35 * 35 мод 97 = 61
     • Ф (4) = Ф (2) * Ф (2)% Број2 = 61 * 61 мод 97 = 35
     • Ф (8) = Ф (4) * Ф (4)% Број2 = 35 * 35 мод 97 = 61
     • Ф (16) = Ф (8) * Ф (8)% Број2 = 61 * 61 мод 97 = 35
     • Ф (32) = Ф (16) * Ф (16)% Број2 = 35 * 35 мод 97 = 61
     • Ф (64) = Ф (32) * Ф (32)% Број2 = 61 * 61 мод 97 = 35
     • Ф (128) = Ф (64) * Ф (64)% Број2 = 35 * 35 мод 97 = 61
   • Израчунајте упарени број 2 - 2
     • 97 - 2 = 95 = (1011111) база 2
     • ММИ2 = ((((Ф (64) * Ф (16)% 97) * Ф (8)% 97) * Ф (4)% 97) * Ф (2)% 97) * Ф (1)% 97)
     • ММИ2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • ММИ2 = 61
5. 5 Израчунај (вредност1 * број2 * ММИ1 + вредност2 * број1 * ММИ2)% (број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 прост. У овом случају, требали бисте добити 0 у корацима 6 и 7.
     • Користите различита значења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.
• Иако је тестирање грубе силе досадан тест при раду са великим бројевима, прилично је ефикасно за мале бројеве. Чак и у случају великих бројева, почните са тестирањем малих делитеља, а затим пређите на софистицираније методе за проверу једноставности бројева (ако се мали делитељи не нађу).

Шта ти треба

• Папир, оловка или рачунар