Мундариҷа

• Қадамҳо
• Қисми 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 Санҷиши Миллер-Рабин. Огоҳӣ: баъзан, гарчанде ки кам аст, барои якчанд арзишҳои а, санҷиш бардурӯғ рақамҳои таркибиро ҳамчун ибтидоӣ муайян мекунад.
   • Миқдорҳои 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 тақсим мешавад.
   • Функсияи фарш (x) x -ро ба ададҳои наздиктарин аз x баробар ё камтар аз он баробар мекунад.
2. 2 Дар бораи арифметикаи модулӣ маълумот гиред. Амали "x mod y" (mod ихтисораи калимаи лотинии "modulo" аст, яъне "модул") маънои "x -ро ба y тақсим кунед ва боқимондаро пайдо кунед." Ба ибораи дигар, дар арифметикаи модулӣ, ҳангоми расидан ба арзиши муайян, ки номида мешавад модул, рақамҳо дубора ба сифр "рӯй" мекунанд. Масалан, соат бо модули 12 ҳисоб карда мешавад: он 10, 11 ва 12 соатро нишон медиҳад ва баъд ба 1 бармегардад.
   • Бисёр калкуляторҳо калиди мод доранд. Дар охири ин бахш ба шумо нишон медиҳад, ки чӣ тавр ба таври дастӣ ҳисоб кардани ин функсия барои рақамҳои калон.
3. 3 Дар бораи хатогиҳои теоремаи хурди Ферма маълумот гиред. Ҳама рақамҳо, ки барои онҳо шартҳои санҷиш иҷро намешаванд, таркибӣ мебошанд, аммо рақамҳои боқимонда танҳо мебошанд эҳтимол оддӣ мебошанд. Агар шумо хоҳед, ки натиҷаҳои нодурустро пешгирӣ кунед, ҷустуҷӯ кунед Н. дар рӯйхати "рақамҳои Кармайкл" (рақамҳои таркибӣ, ки ин санҷишро қонеъ мекунанд) ва "рақамҳои псевдопримаи Ферма" (ин рақамҳо танҳо барои баъзе арзишҳо ба шароити санҷиш ҷавобгӯ мебошанд а).
4. 4 Агар мувофиқ бошад, санҷиши Миллер-Рабинро истифода баред. Гарчанде ки ин усул барои ҳисобҳои дастӣ хеле душвор аст, он одатан дар барномаҳои компютерӣ истифода мешавад. Он суръати қобили қабул ва хатогиҳои камтарро аз усули Ферма таъмин мекунад. Агар ҳисобҳо барои зиёда аз ¼ арзиш иҷро карда шаванд, рақами таркибӣ ҳамчун рақами асосӣ қабул карда намешавад а... Агар шумо тасодуфан арзишҳои гуногунро интихоб кунед а ва барои ҳамаи онҳо санҷиш натиҷаи мусбӣ хоҳад дод, мо метавонем бо боварии хеле баланд боварӣ ҳосил кунем, ки Н. рақами асосӣ аст.
5. 5 Барои рақамҳои калон, арифметикаи модулиро истифода баред. Агар шумо ҳисобкунаки mod надошта бошед ё калкулятор барои идора кардани чунин рақамҳои калон пешбинӣ нашуда бошад, барои осон кардани ҳисобҳо хосиятҳои барқ ​​ва арифметикаи модулиро истифода баред. Дар зер намуна барои ${ 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 (баръакси мултипликативии математикӣ) -ро барои Number1 ва Number2 ҳисоб кунед.
   • Ҳисоб кардани MMI
     • MMI1 = Number2 ^ -1 Number Number1
     • MMI2 = Number1 ^ -1 Number Number2
   • Танҳо барои рақамҳои оддӣ (ин рақамро барои рақамҳои таркибӣ медиҳад, аммо ин MMI -и ӯ нахоҳад буд):
     • MMI1 = (Number2 ^ (Number1-2))% Number1
     • MMI2 = (Number1 ^ (Number2-2))% Number2
   • Барои намуна:
     • 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)% Number1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Number1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Number1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Number1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Number1 = 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)% Number2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Number2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Number2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Number2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Number2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Number2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Number2 = 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 * ММИ2)% (Рақам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 Санҷед, ки Number2 сарвазир аст.
   • Ҳисоб кунед (Ҷавоб - Арзиш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 тақсимкунандаи Number1 бошад. Усули тавсифшуда дар ҳама ҳолатҳо кор мекунад, вақте ки ҳарду рақам оддӣ мебошанд.
   • Сабаби такрори қадамҳои 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.
• Гарчанде ки озмоиши қувваи бераҳмона ҳангоми кор бо рақамҳои зиёд озмоиши дилгиркунанда аст, он барои рақамҳои хурд хеле самаранок аст. Ҳатто дар сурати шумораи зиёд, аз санҷиши тақсимкунандагони хурд оғоз кунед ва сипас ба усулҳои мураккаби санҷиши соддагии рақамҳо гузаред (агар тақсимкунандагони хурд пайдо нашаванд).

Ба шумо чӣ лозим

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