Ինչպես ստուգել, արդյոք թիվը պարզ է

Բովանդակություն

Քայլեր
3 -րդ մաս 1. Պարզության թեստեր
3 -րդ մաս 2. Ինչպես են գործում պարզության թեստերը
3 -րդ մաս 3 -ից. Օգտագործելով չինական մնացորդային թեորեմը
Խորհուրդներ
Ինչ է պետք

Պարզ թվերն այն թվերն են, որոնք բաժանվում են միայն իրենց և 1 -ի վրա: Մնացած թվերը կոչվում են կոմպոզիտային թվեր: Կան բազմաթիվ եղանակներ որոշելու, թե արդյոք թիվը պարզ է, և նրանք բոլորն ունեն իրենց առավելություններն ու թերությունները: Մի կողմից, որոշ մեթոդներ շատ ճշգրիտ են, բայց դրանք բավականին բարդ են, եթե գործ ունեք մեծ թվերի հետ: Մյուս կողմից, կան շատ ավելի արագ եղանակներ, բայց դրանք կարող են հանգեցնել սխալ արդյունքների: Համապատասխան մեթոդի ընտրությունը կախված է նրանից, թե որքան մեծ թվեր եք աշխատում:

Քայլեր

3 -րդ մաս 1. Պարզության թեստեր

Նշում: բոլոր բանաձեւերում n նշանակում է ստուգվող թիվը:

1 Բաժանարարների թվարկում: Բավական է բաժանել n բոլոր պարզ թվերին `2 -ից մինչև կլորացված արժեք ( ${ displaystyle { sqrt {n}}}$ ).
2 Ֆերմանի փոքր թեորեմը: Arnգուշացում. Երբեմն թեստը կեղծ թվերը կճանաչի որպես պարզ, նույնիսկ a- ի բոլոր արժեքների համար:
- Եկեք ընտրենք մի ամբողջ թիվ աայնպես, որ 2 ≤ a ≤ n - 1:
- Եթե a (mod n) = a (mod n), ապա թիվը հավանաբար պարզ է: Եթե հավասարությունը չի բավարարվում, ապա n թիվը կազմված է:
- Ստուգված տրված հավասարությունը բազմակի արժեքների համար ամեծացնելու հավանականությունը, որ փորձարկվող թիվը իսկապես պարզ է:
3 Միլեր-Ռաբինի թեստ: Sometimesգուշացում. Երբեմն, չնայած հազվադեպ, 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 Բաժանարարների թվարկում: Ըստ սահմանման ՝ թիվը n պարզ է միայն այն դեպքում, եթե այն չի բաժանվում 2 -ի և այլ ամբողջ թվերի, բացի 1 -ից և իրենից: Վերոնշյալ բանաձևը թույլ է տալիս հեռացնել անհարկի քայլերը և խնայել ժամանակը. Օրինակ ՝ ստուգելուց հետո, եթե թիվը բաժանվում է 3 -ի, կարիք չկա ստուգելու, թե արդյոք այն բաժանվում է 9 -ի:
- Հատակ (x) ֆունկցիան x- ը կլորացնում է x- ից փոքր կամ հավասար ամբողջ թվին:
2 Իմացեք մոդուլային թվաբանության մասին: «X mod y» գործողությունը (mod- ը լատիներեն «modulo» բառի հապավում է, այսինքն ՝ «module») նշանակում է «x- ը բաժանեք y- ի և գտեք մնացորդը»: Այլ կերպ ասած, մոդուլային թվաբանության մեջ, որոշակի արժեքի հասնելուն պես, որը կոչվում է մոդուլ, թվերը նորից «դառնում են» զրոյի: Օրինակ, ժամացույցը հետ է հաշվում 12 մոդուլով. Այն ցույց է տալիս 10, 11 և 12 ժամ, իսկ հետո վերադառնում է 1:
- Շատ հաշվիչներ ունեն ռեժիմի բանալին: Այս բաժնի վերջը ցույց է տալիս, թե ինչպես ձեռքով հաշվարկել այս գործառույթը մեծ թվերի համար:
3 Իմացեք Ֆերմանի փոքր թեորեմի որոգայթների մասին: Բոլոր թվերը, որոնց համար թեստի պայմանները չեն համապատասխանում, կազմված են, բայց մնացած թվերը միայն են հավանաբար պարզ են. Եթե ցանկանում եք խուսափել սխալ արդյունքներից, որոնեք n «Կարմայքելի համարներ» (այս թեստը բավարարող կոմպոզիտային թվեր) և «Ֆերմայի կեղծ հանցագործության թվերի» ցանկում (այս թվերը բավարարում են թեստի պայմանները միայն որոշ արժեքների համար ա).
4 Հարմարության դեպքում օգտագործեք Miller-Rabin թեստը: Թեև այս մեթոդը բավականին ծանր է ձեռքով հաշվարկների համար, այն հաճախ օգտագործվում է համակարգչային ծրագրերում: Այն ապահովում է ընդունելի արագություն և ավելի քիչ սխալներ, քան Ֆերմանի մեթոդը: Կոմպոզիտային թիվը չի ընդունվի որպես հիմնական թիվ, եթե հաշվարկները կատարվում են ավելի քան ¼ արժեքների համար ա... Եթե դուք պատահականորեն ընտրեք տարբեր արժեքներ ա և բոլորի համար թեստը կտա դրական արդյունք, մենք կարող ենք բավականին բարձր աստիճանի վստահությամբ ենթադրել, որ n պարզ թիվ է:
5 Մեծ թվերի դեպքում օգտագործեք մոդուլային թվաբանություն: Եթե ձեռքի տակ չունեք մոդուլային հաշվիչ, կամ հաշվիչը նախատեսված չէ նման մեծ թվերի հետ աշխատելու համար, օգտագործեք էներգիայի հատկություններ և մոդուլային թվաբանություն `հաշվարկներն ավելի դյուրին դարձնելու համար: Ստորև բերված է օրինակ 350{ displaystyle 3 ^ {50}} ռեժիմ 50:
- Վերաշարադրեք արտահայտությունը ավելի հարմար ձևով. ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ եղանակ 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 = ${ ցուցադրման ոճ (43 * 43)}$ մոդ 50.
- ${ displaystyle = 1849}$ մոդ 50.
- ${ displaystyle = 49}$ .

3 -րդ մաս 3 -ից. Օգտագործելով չինական մնացորդային թեորեմը

1 Ընտրեք երկու համար: Թվերից մեկը պետք է լինի կոմպոզիտային, իսկ մյուսը պետք է լինի այն, ինչ ցանկանում եք ստուգել պարզության համար:
- Թիվ 1 = 35
- Թիվ 2 = 97
2 Ընտրեք երկու արժեք, որոնք մեծ են զրոյից և, համապատասխանաբար, ավելի փոքր են, քան Number1 և Number2 համարները: Այս արժեքները չպետք է նույնը լինեն:
- Արժեք 1 = 1
- Արժեք 2 = 2
3 Թիվ 1 -ի և Թվի 2 -ի համար հաշվարկեք MMI- ը (Մաթեմատիկական բազմապատկիչ հակադարձ):
- Հաշվեք MMI- ը
  - MMI1 = Number2 ^ -1 Mod Number1
  - MMI2 = Number1 ^ -1 Mod Number2
- Միայն պարզ թվերի համար (սա մի շարք կտա բարդ թվերի համար, բայց դա չի լինի նրա MMI- ը).
  - MMI1 = (Number2 ^ (Number1-2))% Number1
  - MMI2 = (Number1 ^ (Number2-2))% Number2
- Օրինակ:
  - 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
- Հաշվիր զույգ թվեր 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
- Հաշվարկեք iredուգտկված թիվը 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 Հաշվել (Արժեք 1 * Թիվ 2 * MMI1 + Արժեք 2 * Թիվ 1 * MMI2)% (Թիվ 1 * Թիվ 2)
- Պատասխան = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
- Պատասխան = (2619 + 4270)% 3395
- Պատասխան = 99
6 Ստուգեք, որ թիվ 1 -ը պարզ չէ
- Հաշվել (պատասխան - արժեք 1)% համար 1
- 99 – 1 % 35 = 28
- Քանի որ 28 -ը 0 -ից մեծ է, 35 -ը պարզ թիվ չէ:
7 Ստուգեք, որ Number2- ը պարզ է:
- Հաշվել (Պատասխան - Արժեք 2)% Թիվ 2
- 99 – 2 % 97 = 0
- Քանի որ 0 -ը 0 է, 97 -ը, ամենայն հավանականությամբ, պարզ թիվ է:
8 Կրկնեք 1 -ից 7 -րդ քայլերը առնվազն ևս երկու անգամ:
- Եթե 7 -րդ քայլում ստանում եք 0.
  - Օգտագործեք այլ Number1, եթե Number1- ը պարզ չէ:
  - Օգտագործեք մեկ այլ Number1, եթե Number1- ը պարզ է: Այս դեպքում 6 -րդ և 7 -րդ քայլերում դուք պետք է ստանաք 0:
  - Օգտագործեք տարբեր նշանակություն 1 և իմաստ 2:
- Եթե 7 -րդ քայլում դուք հետևողականորեն ստանում եք 0, ապա թիվ 2 -ը, ամենայն հավանականությամբ, կլինի առաջինը:
- 1 -ից 7 -րդ քայլերը կարող են հանգեցնել սխալի, եթե Number1- ը պարզ չէ, իսկ Number2- ը ՝ Number1- ի բաժանարար: Նկարագրված մեթոդը գործում է բոլոր այն դեպքերում, երբ երկու թվերն էլ պարզ են:
- Պատճառը, որի համար անհրաժեշտ է կրկնել 1 -ից 7 -րդ քայլերը, այն է, որ որոշ դեպքերում, նույնիսկ եթե Թիվ 1 -ը և Թիվ 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, 421, 431, 433, 439, 443, 449, 459, 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, 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:
Չնայած կոպիտ ուժի փորձարկումը հոգնեցուցիչ է մեծ թվերի հետ աշխատելիս, այն փոքր թվերի համար բավականին արդյունավետ է: Նույնիսկ մեծ թվերի դեպքում սկսեք փոքր բաժանարարների փորձարկումից, այնուհետև անցեք թվերի պարզությունը ստուգելու ավելի բարդ մեթոդների (եթե փոքր բաժանարարներ չգտնվեն):