Мазмұны

• Қадамдар
• 3 -тің 1 -бөлігі: Қарапайымдылық тесттері
• 3 бөліктің 2 бөлігі: Қарапайымдылық тестілері қалай жұмыс істейді
• 3 -тің 3 -бөлігі: Қытайдың қалдық теоремасын қолдану
• Кеңестер
• Саған не қажет

Жай сандар - тек өздеріне және 1 -ге бөлінетін сандар. Барлық қалған сандар құрама сандар деп аталады. Санның қарапайым екенін анықтаудың көптеген әдістері бар және олардың әрқайсысының өзіндік артықшылықтары мен кемшіліктері бар. Бір жағынан, кейбір әдістер өте дәл, бірақ егер сіз үлкен сандармен айналысатын болсаңыз, олар өте күрделі. Екінші жағынан, әлдеқайда жылдам әдістер бар, бірақ олар қате нәтижеге әкелуі мүмкін. Сәйкес әдісті таңдау сіз жұмыс істейтін сандарға байланысты.

Қадамдар

3 -тің 1 -бөлігі: Қарапайымдылық тесттері

Ескерту: барлық формулаларда n тексерілетін нөмірді білдіреді.

1. 1 Бөлгіштерді санау. Бөлу жеткілікті n 2 -ден дөңгелектенген мәнге дейінгі барлық жай сандарға (${ Displaystyle { sqrt {n}}}$).
2. 2 Ферма теоремасы. Ескерту: кейде тест жалған а санының барлық мәндері үшін құрама сандарды жай ретінде анықтайды.
   • Бүтін санды таңдайық а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 сынақтан өтсе, оны басқа мәндер үшін қайталаңыз асенімділігін арттыру үшін.

3 бөліктің 2 бөлігі: Қарапайымдылық тестілері қалай жұмыс істейді

1. 1 Бөлгіштерді санау. Анықтама бойынша, сан n егер ол 2 -ге және 1 -ден басқа бүтін сандарға бөлінбесе ғана қарапайым. Жоғарыдағы формула қажет емес қадамдарды алып тастауға және уақытты үнемдеуге мүмкіндік береді: мысалы, санның 3 -ке бөлінетінін тексергеннен кейін оның 9 -ға бөлінетінін тексерудің қажеті жоқ.
   • Еден (x) функциясы х -ты x -тен кіші немесе оған тең бүтін санға дейін дөңгелектейді.
2. 2 Модульдік арифметика туралы біліңіз. «X mod y» операциясы (mod - латынның «модуло» сөзінің қысқартылуы, яғни «модуль») «х -ты у -ге бөліп, қалғанын табу» дегенді білдіреді. Басқаша айтқанда, модульдік арифметикада белгілі бір мәнге жеткенде модуль, сандар қайтадан нөлге «бұрылады». Мысалы, сағат 12 -модульмен есептеледі: ол 10, 11 және 12 сағатты көрсетеді, содан кейін 1 -ге оралады.
   • Көптеген калькуляторларда модуль кілті бар. Бұл бөлімнің соңы үлкен функциялар үшін бұл функцияны қолмен қалай есептеу керектігін көрсетеді.
3. 3 Ферматтың кіші теоремасының тұзақтары туралы біліңіз. Тексеру шарттары орындалмаған барлық сандар құрама, ал қалған сандар тек қана мүмкін қарапайым. Егер сіз қате нәтижеден аулақ болғыңыз келсе, іздеңіз n «Кармайкл сандары» (осы тестке сәйкес келетін құрама сандар) және «Ферма жалған сандар сандары» тізімінде (бұл сандар тек кейбір мәндер үшін тест шарттарына сәйкес келеді) а).
4. 4 Егер ыңғайлы болса, Миллер-Рабин тестін қолданыңыз. Бұл әдіс қолмен есептеуге қиын болғанымен, ол көбінесе компьютерлік бағдарламаларда қолданылады. Ол қолайлы жылдамдықты қамтамасыз етеді және Ферма әдісіне қарағанда қателіктерді азайтады. Егер есептеулер ¼ мәнінен артық орындалса, құрама сан жай сан ретінде қабылданбайды а... Егер сіз кездейсоқ түрлі мәндерді таңдасаңыз а және олардың барлығы үшін тест оң нәтиже береді, біз сенімділіктің жоғары дәрежесінде деп есептей аламыз n жай сан болып табылады.
5. 5 Үлкен сандар үшін модульдік арифметиканы қолданыңыз. Егер сізде ыңғайлы калькулятор болмаса немесе калькулятор мұндай үлкен сандарды өңдеуге арналмаған болса, есептеулерді жеңілдету үшін қуат қасиеттері мен модульдік арифметиканы қолданыңыз. Төменде мысал келтірілген ${ Displaystyle 3 ^ {50}}$ 50 режимі:
   • Өрнекті неғұрлым ыңғайлы түрде қайта жазыңыз: ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ 50 -режим. Қолмен есептеулер одан әрі жеңілдетуді қажет етуі мүмкін.
   • ${ Displaystyle (3 ^ {25} * 3 ^ {25})}$ режим 50 = ${ Displaystyle (3 ^ {25}}$ режим 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. Мұнда біз модульдік көбейту қасиетін ескердік.
   • ${ Displaystyle 3 ^ {25}}$ режим 50 = 43.
   • ${ Displaystyle (3 ^ {25}}$ режим 50 ${ displaystyle * 3 ^ {25}}$ 50 режимі) 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 (Mathematical Multiplicative Inverse) санын 1 және 2 санына есептеңіз.
   • MMI есептеңіз
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • Тек жай сандар үшін (бұл құрама сандар үшін сан береді, бірақ бұл оның MMI болмайды):
     • MMI1 = (Number2 ^ (Number1-2))% Number1
     • MMI2 = (Сан1 ^ (Сан2-2))% Сан2
   • Мысалға:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Log2 модульдерінің әр MMI үшін кесте жасаңыз:
   • 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) режим 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
   • Жұптасқан санды есептеңіз - 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 Number1 негізгі емес екенін тексеріңіз
   • Есептеңіз (Жауабы - Мән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 алсаңыз:
     • Егер Number1 қарапайым болмаса, басқа Number1 пайдаланыңыз.
     • Егер Number1 қарапайым болса, басқа Number1 пайдаланыңыз. Бұл жағдайда сіз 6 және 7 қадамдарда 0 алуыңыз керек.
     • Әр түрлі Мағынаны1 және Мағынаны2 қолданыңыз.
   • Егер 7 -қадамда сіз үнемі 0 -ді алсаңыз, онда 2 -ші нөмір өте жақсы болуы мүмкін.
   • Егер 1 -ден 7 -ге дейінгі қадамдар қате әкелуі мүмкін, егер Number1 қарапайым емес, ал Number2 - Санның 1 -ге бөлінуі болса. Сипатталған әдіс екі сан да қарапайым болған жағдайда жұмыс істейді.
   • 1 -ден 7 -ге дейінгі қадамдарды қайталауыңыздың себебі, кейбір жағдайларда, егер Number1 мен Number 2 қарапайым болмаса да, 7 -қадамда сіз 0 (бір немесе екі сан үшін) аласыз. Бұл сирек кездеседі.Басқа Number1 (құрама) таңдаңыз, ал егер Number2 жай емес болса, онда Number2 7 -қадамда нөлге тең болмайды (Number1 Number2 -дің бөлгіші болған жағдайды қоспағанда - мұнда 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.
• Дөрекі күштерді сынау үлкен сандармен жұмыс жасауда жалықтыратын сынақ болғанымен, ол аз сандар үшін өте тиімді. Тіпті үлкен сандар болған жағдайда, кішкене бөлгіштерді тексеруден бастаңыз, содан кейін сандардың қарапайымдылығын тексерудің күрделі әдістеріне көшіңіз (егер кіші бөлгіштер табылмаса).

Саған не қажет

• Қағаз, қалам немесе компьютер