Съдържание

• Стъпки
• Част 1 от 3: Тестове за простота
• Част 2 от 3: Как работят тестовете за простота
• Част 3 от 3: Използване на китайската теорема за остатъци
• Съвети
• Какво ти е необходимо

Простите числа са числа, които се делят само на себе си и на 1. Всички останали числа се наричат ​​съставни числа. Има много начини да се определи дали дадено число е просто и всички те имат свои собствени предимства и недостатъци. От една страна, някои от методите са много точни, но са доста сложни, ако имате работа с големи числа. От друга страна, има много по -бързи начини, но те могат да доведат до неправилни резултати. Изборът на подходящ метод зависи от това с колко големи числа работите.

Стъпки

Част 1 от 3: Тестове за простота

Забележка: във всички формули н обозначава номера, който трябва да бъде проверен.

1. 1 Изброяване на делители. Достатъчно е да се раздели н към всички прости числа от 2 до закръглена стойност (${ displaystyle { sqrt {n}}}$).
2. 2 Малката теорема на Ферма. Предупреждение: понякога тестът погрешно ще идентифицира съставните числа като прости, дори за всички стойности на a.
   • Нека изберем цяло число атака че 2 ≤ a ≤ n - 1.
   • Ако a (mod n) = a (mod n), тогава числото вероятно е просто. Ако равенството не е изпълнено, числото n е съставно.
   • Проверете даденото равенство за множество стойности аза да се увеличи вероятността тестваното число наистина да е първостепенно.
3. 3 Тест на Милър-Рабин. Предупреждение: понякога, макар и рядко, за множество стойности на a, тестът погрешно ще идентифицира съставните числа като прости.
   • Намерете количествата s и d такива, че ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • Изберете цяло число а в диапазона 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 премине теста, повторете го за други стойности аза повишаване на доверието.

Част 2 от 3: Как работят тестовете за простота

1. 1 Изброяване на делители. По дефиниция числото н е просто само ако не се дели на 2 и други цели числа освен 1 и себе си. Горната формула ви позволява да премахнете ненужните стъпки и да спестите време: например, след като проверите дали дадено число се дели на 3, няма нужда да проверявате дали е делимо на 9.
   • Функцията floor (x) закръглява x до най -близкото цяло число, по -малко или равно на x.
2. 2 Научете за модулната аритметика. Операцията „x mod y“ (mod е съкращение от латинската дума „modulo“, тоест „модул“) означава „разделете x на y и намерете остатъка“. С други думи, в модулна аритметика, при достигане на определена стойност, която се нарича модул, числата отново "се обръщат" към нула. Например часовникът отброява с модул 12: той показва 10, 11 и 12 часа и след това се връща на 1.
   • Много калкулатори имат ключ за модификация. В края на този раздел ви показва как ръчно да изчислите тази функция за големи числа.
3. 3 Научете за клопките на Малката теорема на Ферма. Всички числа, за които условията на теста не са изпълнени, са съставни, но останалите числа са само вероятно са прости. Ако искате да избегнете неправилни резултати, потърсете н в списъка на „числата на Кармайкъл“ (съставни числа, които отговарят на този тест) и „числа на псевдо -първични числа на Ферма“ (тези числа отговарят на условията за изпитване само за някои стойности а).
4. 4 Ако е удобно, използвайте теста на Милър-Рабин. Въпреки че този метод е доста тромав за ръчни изчисления, той често се използва в компютърни програми. Той осигурява приемлива скорост и по -малко грешки от метода на Fermat. Съставено число няма да се приема като просто число, ако изчисленията се извършват за повече от ¼ стойности а... Ако случайно изберете различни стойности а и за всички тях тестът ще даде положителен резултат, можем да приемем с доста висока степен на увереност, че н е просто число.
5. 5 За големи числа използвайте модулна аритметика. Ако нямате удобен калкулатор на модове или калкулаторът не е проектиран да обработва такива големи числа, използвайте свойствата на мощността и модулната аритметика, за да улесните изчисленията. По -долу е даден пример за ${ displaystyle 3 ^ {50}}$ мод 50:
   • Препишете израза в по -удобна форма: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50. Ръчните изчисления може да изискват допълнителни опростявания.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ displaystyle (3 ^ {25}}$ мод 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Тук взехме предвид свойството на модулно умножение.
   • ${ displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ displaystyle (3 ^ {25}}$ мод 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50 = ${ displaystyle (43 * 43)}$ мод 50.
   • ${ displaystyle = 1849}$ мод 50.
   • ${ displaystyle = 49}$.

Част 3 от 3: Използване на китайската теорема за остатъци

1. 1 Изберете две числа. Едно от числата трябва да е съставно, а другото трябва да е точно това, което искате да тествате за простота.
   • Номер 1 = 35
   • Номер 2 = 97
2. 2 Изберете две стойности, които са по -големи от нула и съответно по -малки от числата Number1 и Number2. Тези стойности не трябва да са еднакви.
   • Стойност1 = 1
   • Стойност2 = 2
3. 3 Изчислете MMI (математически мултипликативен обратен) за число1 и число2.
   • Изчислете MMI
     • MMI1 = Номер2 ^ -1 Мод Номер1
     • MMI2 = Номер1 ^ -1 Мод номер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 поне още два пъти.
   • Ако получите 0 в стъпка 7:
     • Използвайте различно число1, ако число1 не е просто.
     • Използвайте друго число1, ако число1 е просто. В този случай трябва да получите 0 в стъпки 6 и 7.
     • Използвайте различно значение1 и значение2.
   • Ако в стъпка 7 постоянно получавате 0, тогава число 2 е много вероятно да бъде първостепенно.
   • Стъпки от 1 до 7 могат да доведат до грешка, ако Number1 не е просто и Number2 е делител на Number1. Описаният метод работи във всички случаи, когато и двете числа са прости.
   • Причината, поради която трябва да повторите стъпки от 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.
• Въпреки че тестването на груба сила е досаден тест при работа с големи числа, то е доста ефективно за малки числа. Дори в случай на големи числа, започнете с тестване на малки делители и след това преминете към по -сложни методи за проверка на простотата на числата (ако не са намерени малки делители).

Какво ти е необходимо

• Хартия, химикалка или компютър