Мазмун

• Кадамдар
• 3төн 1 бөлүк: Жөнөкөйлүк тесттери
• 3төн 2 бөлүк: Жөнөкөйлүк тесттери кантип иштейт
• 3 -жылдын 3 -бөлүгү: Кытайдын калган теоремасын колдонуу
• Кеңештер
• Сага эмне керек

Жөнөкөй сандар - бул өздөрүнө жана 1ге гана бөлүнүүчү сандар. Башка сандардын баары курама сандар деп аталат. Сандын негизги экенин аныктоонун көптөгөн жолдору бар жана алардын баарынын өзүнүн артыкчылыктары жана кемчиликтери бар. Бир жагынан алганда, кээ бир ыкмалар абдан так, бирок, эгерде сиз көп сандар менен алектенсеңиз, алар өтө татаал. Башка жагынан алганда, алда канча ылдамыраак жолдор бар, бирок алар туура эмес жыйынтыктарга алып келиши мүмкүн. Тийиштүү ыкманы тандоо сиз иштеп жаткан сандардын канчалык чоң экенине жараша болот.

Кадамдар

3төн 1 бөлүк: Жөнөкөйлүк тесттери

Эскертүү: бардык формулаларда п текшериле турган номерди билдирет.

1. 1 Бөлүүчүлөрдүн тизмеси. Бөлүү жетиштүү п 2ден тегеректелген мааниге чейинки бардык жөнөкөй сандарга (${ Displaystyle { sqrt {n}}}$).
2. 2 Ферманын кичинекей теоремасы. Эскертүү: кээде тест жалган адын бардык баалуулуктары үчүн да курама сандарды жөнөкөй деп аныктайт.
   • Келгиле, бүтүн санды тандап алалы аушундай 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 тесттен өтсө, аны башка баалуулуктар үчүн кайталаңыз аишенимди жогорулатуу.

3төн 2 бөлүк: Жөнөкөйлүк тесттери кантип иштейт

1. 1 Бөлүүчүлөрдүн тизмеси. Аныктама боюнча, сан п 2 жана башка бүтүн сандарга 1ге жана өзүнө бөлүнбөгөндө гана жөнөкөй. Жогорудагы формула керексиз кадамдарды алып салууга жана убакытты үнөмдөөгө мүмкүндүк берет: мисалы, сан 3кө бөлүнөөрүн текшергенден кийин, анын 9га бөлүнүшүн текшерүүнүн кажети жок.
   • Flood (x) функциясы xти xке барабар же андан аз бүтүн санга чейин тегеректейт.
2. 2 Модулдук арифметика жөнүндө билиңиз. "X mod y" операциясы (mod - латынча "modulo" деген сөздүн кыскартылышы, башкача айтканда "модуль") "x -ти y -ге бөлүп, калганын табуу" дегенди билдирет. Башкача айтканда, модулдук арифметикада белгилүү бир мааниге жеткенде модуль, сандар кайра нөлгө "бурулат". Мисалы, саат 12 модулу менен эсептелген: 10, 11 жана 12 саатты көрсөтөт, анан 1ге кайтат.
   • Көптөгөн эсептегичтерде мод баскычы бар. Бул бөлүмдүн аягында бул функцияны кол менен көп сандар үчүн кантип эсептөө керектиги көрсөтүлөт.
3. 3 Ферманын кичинекей теоремасынын тузактары жөнүндө билип алыңыз. Тест шарттары аткарылбаган бардык сандар курама, бирок калган сандар гана балким жөнөкөй Эгер туура эмес жыйынтыктардан качкыңыз келсе, издеңиз п "Кармайкл номерлери" тизмесинде (бул тестке жооп берген курама сандар) жана "Ферма псевдоприм сандары" (бул сандар кээ бир баалуулуктар үчүн гана тест шарттарына жооп берет а).
4. 4 Ыңгайлуу болсо, Миллер-Рабин тестин колдонуңуз. Бул ыкма кол менен эсептөө үчүн кыйла татаал болгону менен, көбүнчө компьютердик программаларда колдонулат. Бул алгылыктуу ылдамдыкты жана Ферманын ыкмасына караганда азыраак каталарды камсыз кылат. Эгерде эсептөөлөр ¼ мааниден ашык аткарылса, курама сан негизги сан катары кабыл алынбайт а... Эгерде сиз туш келди түрдө башка баалуулуктарды тандасаңыз а жана алардын бардыгы үчүн тест оң натыйжа берет, биз буга абдан ишенимдүү түрдө ишенсек болот п негизги сан болуп саналат.
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 Эки санды тандаңыз. Сандардын бири курама болушу керек, экинчиси жөнөкөйлүктү текшерүүнү каалаган так болушу керек.
   • Number1 = 35
   • Number2 = 97
2. 2 Нөлдөн чоң жана тиешелүүлүгүнө жараша Number1 жана Number2 сандарынан эки маанини тандаңыз. Бул баалуулуктар бирдей болбошу керек.
   • Value1 = 1
   • Мааниси2 = 2
3. 3 Number1 жана Number2 үчүн MMI (Mathematical Multiplicative Inverse) эсептеңиз.
   • 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)% 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)% саны2 = 35 * 35 мод 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)% саны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 Эсептөө (Value1 * Number2 * MMI1 + Value2 * Number1 * MMI2)% (Number1 * Number2)
   • Жооп = (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.
• Катуу күч сыноо көп сандар менен иштөөдө түйшүктүү сыноо болгону менен, кичине сандар үчүн абдан эффективдүү. Сандар көп болгон учурда да, кичине бөлгүчтөрдү текшерүүдөн баштаңыз, андан кийин сандардын жөнөкөйлүгүн текшерүүнүн татаал ыкмаларына өтүңүз (эгер кичине бөлгүчтөр табылбаса).

Сага эмне керек

• Кагаз, калем же компьютер