உள்ளடக்கம்

• படிகள்
• பகுதி 1 இல் 3: எளிமைக்கான சோதனைகள்
• 3 இன் பகுதி 2: எளிமை சோதனைகள் எவ்வாறு செயல்படுகின்றன
• 3 இன் பகுதி 3: சீன எச்ச தேற்றத்தைப் பயன்படுத்துதல்
• குறிப்புகள்
• உனக்கு என்ன வேண்டும்

பிரைம் எண்கள் தங்களால் மற்றும் 1 ஆல் மட்டுமே வகுக்கப்படும் எண்கள். மற்ற அனைத்து எண்களும் கூட்டு எண்கள் என்று அழைக்கப்படுகின்றன. ஒரு எண் முதன்மையானதா என்பதைத் தீர்மானிக்க பல வழிகள் உள்ளன, அவை அனைத்திற்கும் அவற்றின் சொந்த நன்மைகள் மற்றும் தீமைகள் உள்ளன. ஒருபுறம், சில முறைகள் மிகவும் துல்லியமானவை, ஆனால் நீங்கள் பெரிய எண்களைக் கையாளுகிறீர்கள் என்றால் அவை மிகவும் சிக்கலானவை. மறுபுறம், மிக விரைவான வழிகள் உள்ளன, ஆனால் அவை தவறான முடிவுகளுக்கு வழிவகுக்கும். பொருத்தமான முறையின் தேர்வு நீங்கள் எவ்வளவு பெரிய எண்களுடன் வேலை செய்கிறீர்கள் என்பதைப் பொறுத்தது.

படிகள்

பகுதி 1 இல் 3: எளிமைக்கான சோதனைகள்

குறிப்பு: அனைத்து சூத்திரங்களிலும் என் சரிபார்க்க வேண்டிய எண்ணைக் குறிக்கிறது.

1. 1 வகுப்பிகளின் எண்ணிக்கை. பிரித்தால் போதும் என் 2 முதல் வட்டமான மதிப்பு வரை அனைத்து முக்கிய எண்களுக்கும் (${ displaystyle { sqrt {n}}}$).
2. 2 ஃபெர்மட்டின் சிறிய தேற்றம். எச்சரிக்கை: சில சமயங்களில், சோதனை எண்களின் அனைத்து மதிப்புகளுக்கும் கூட கூட்டு எண்களை முதன்மையாக தவறாக அடையாளம் காணும்.
   • ஒரு முழு எண்ணைத் தேர்ந்தெடுப்போம் ஒரு2 ≤ a ≤ n - 1.
   • ஒரு (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 அநேகமாக முதன்மையானது. இந்த வழக்கில், சோதனை முடிவுக்குச் செல்லவும். சமத்துவம் நிலைக்கவில்லை என்றால், அடுத்த படிக்கு செல்லுங்கள்.
   • உங்கள் பதிலை சதுரமாக்குங்கள் (${ காட்சி உடை a ^ {2d}}$) உங்களுக்கு -1 (mod n) கிடைத்தால், n என்பது ஒரு முதன்மை எண். இந்த வழக்கில், சோதனை முடிவுக்குச் செல்லவும். சமத்துவம் தோல்வியடைந்தால், மீண்டும் செய்யவும் (${ காட்சி உடை a ^ {4d}}$ மற்றும் பல) வரை ${ காட்சி உடை a ^ {2 ^ {s-1} d}}$.
   • வேறு ஒரு எண்ணை சதுரப்படுத்திய பிறகு சில கட்டங்களில் ${ காட்சி உடை pm 1}$ (mod n), உங்களுக்கு +1 (mod n) கிடைத்தது, எனவே n என்பது ஒரு கூட்டு எண். என்றால் ${ காட்சி நடை a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), பிறகு n என்பது முதன்மையானது அல்ல.
   • சோதனை முடிவு: n தேர்வில் தேர்ச்சி பெற்றால், மற்ற மதிப்புகளுக்கு அதை மீண்டும் செய்யவும் ஒருநம்பிக்கையை அதிகரிக்க.

3 இன் பகுதி 2: எளிமை சோதனைகள் எவ்வாறு செயல்படுகின்றன

1. 1 வகுப்பிகளின் எண்ணிக்கை. வரையறையின்படி, எண் என் இது 2 மற்றும் 1 மற்றும் தன்னைத் தவிர மற்ற முழு எண்களால் வகுக்கப்படாவிட்டால் மட்டுமே எளிது. மேலே உள்ள சூத்திரம் தேவையற்ற படிகளை நீக்கி நேரத்தை மிச்சப்படுத்துகிறது: உதாரணமாக, ஒரு எண்ணை 3 ஆல் வகுபடுகிறதா என்று சோதித்த பிறகு, அது 9 ஆல் வகுபடுகிறதா என்று சரிபார்க்க வேண்டிய அவசியமில்லை.
   • தரை (x) செயல்பாடு x ஐ விட மிக அருகில் அல்லது முழு எண்கோணத்திற்குச் சுற்றுகிறது.
2. 2 மட்டு எண்கணிதத்தைப் பற்றி அறிக. செயல்பாடு "x mod y" (mod என்பது லத்தீன் வார்த்தையான "modulo" என்பதன் சுருக்கமாகும், அதாவது "தொகுதி") "x ஐ y ஆல் வகுத்து எஞ்சியதைக் கண்டறியவும்." வேறு வார்த்தைகளில் கூறுவதானால், மட்டு எண்கணிதத்தில், ஒரு குறிப்பிட்ட மதிப்பை அடைந்தவுடன், இது அழைக்கப்படுகிறது தொகுதி, எண்கள் மீண்டும் "பூஜ்ஜியமாக" மாறும். எடுத்துக்காட்டாக, தொகுதி 12 உடன் கடிகாரம் கணக்கிடப்படுகிறது: இது 10, 11 மற்றும் 12 மணிநேரங்களைக் காட்டுகிறது, பின்னர் 1 க்குத் திரும்பும்.
   • பல கால்குலேட்டர்களில் மோட் கீ உள்ளது. பெரிய எண்களுக்கு இந்த செயல்பாட்டை எப்படி கைமுறையாக கணக்கிடுவது என்பதை இந்த பிரிவின் இறுதியில் காட்டுகிறது.
3. 3 ஃபெர்மாட்டின் சிறிய தேற்றத்தின் ஆபத்துகள் பற்றி அறியவும். சோதனை நிபந்தனைகள் பூர்த்தி செய்யப்படாத அனைத்து எண்களும் ஒருங்கிணைந்தவை, ஆனால் மீதமுள்ள எண்கள் மட்டுமே அநேகமாக எளிமையானவை. தவறான முடிவுகளைத் தவிர்க்க விரும்பினால், தேடுங்கள் என் "கார்மைக்கேல் எண்கள்" (இந்த சோதனையை பூர்த்தி செய்யும் கலப்பு எண்கள்) மற்றும் "ஃபெர்மாட் சூடோப்ரைம் எண்கள்" (இந்த எண்கள் சில மதிப்புகளுக்கு மட்டுமே சோதனை நிலைமைகளை சந்திக்கின்றன) ஒரு).
4. 4 வசதியாக இருந்தால், மில்லர்-ராபின் சோதனையைப் பயன்படுத்தவும். கையேடு கணக்கீடுகளுக்கு இந்த முறை சிக்கலானதாக இருந்தாலும், இது பெரும்பாலும் கணினி நிரல்களில் பயன்படுத்தப்படுகிறது. இது ஃபெர்மட்டின் முறையை விட ஏற்றுக்கொள்ளக்கூடிய வேகத்தையும் குறைவான பிழைகளையும் வழங்குகிறது. Number மதிப்புகளுக்கு மேல் கணக்கீடுகள் செய்யப்பட்டால் ஒரு கூட்டு எண் ஒரு முதன்மை எண்ணாக எடுக்கப்படாது ஒரு... நீங்கள் தோராயமாக வெவ்வேறு மதிப்புகளைத் தேர்ந்தெடுத்தால் ஒரு அவர்கள் அனைவருக்கும் சோதனை நேர்மறையான முடிவை அளிக்கும், நாம் அதிக அளவு நம்பிக்கையுடன் கருதலாம் என் ஒரு முதன்மை எண்.
5. 5 பெரிய எண்களுக்கு, மட்டு எண்கணிதத்தைப் பயன்படுத்தவும். உங்களிடம் மாட் கால்குலேட்டர் இல்லை என்றால் அல்லது கால்குலேட்டர் இவ்வளவு பெரிய எண்களைக் கையாள வடிவமைக்கப்படவில்லை என்றால், கணக்கீடுகளை எளிதாக்க சக்தி பண்புகள் மற்றும் மட்டு எண்கணிதத்தைப் பயன்படுத்தவும். கீழே ஒரு உதாரணம் ${ காட்சி நடை 3 ^ {50}}$ மோட் 50:
   • வெளிப்பாட்டை மிகவும் வசதியான வடிவத்தில் மீண்டும் எழுதவும்: ${ காட்சி வடிவம் (3 ^ {25} * 3 ^ {25})}$ mod 50. கையேடு கணக்கீடுகளுக்கு மேலும் எளிமைப்படுத்தல்கள் தேவைப்படலாம்.
   • ${ காட்சி வடிவம் (3 ^ {25} * 3 ^ {25})}$ மோட் 50 = ${ காட்சி உடை (3 ^ {25}}$ மோட் 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. இங்கு நாம் மட்டு பெருக்கத்தின் சொத்தை கணக்கில் எடுத்துக்கொண்டோம்.
   • ${ காட்சி நடை 3 ^ {25}}$ மோட் 50 = 43.
   • ${ காட்சி உடை (3 ^ {25}}$ மோட் 50 ${ displaystyle * 3 ^ {25}}$ மோட் 50) மோட் 50 = ${ காட்சி உடை (43 * 43)}$ மோட் 50.
   • ${ displaystyle = 1849}$ மோட் 50.
   • ${ displaystyle = 49}$.

3 இன் பகுதி 3: சீன எச்ச தேற்றத்தைப் பயன்படுத்துதல்

1. 1 இரண்டு எண்களைத் தேர்ந்தெடுக்கவும். எண்களில் ஒன்று கூட்டாக இருக்க வேண்டும், மற்றொன்று நீங்கள் எளிமைக்காக சோதிக்க விரும்பும் எண்ணாக இருக்க வேண்டும்.
   • எண் 1 = 35
   • எண் 2 = 97
2. 2 பூஜ்ஜியத்தை விடவும், எண் 1 மற்றும் எண் 2 ஐ விட குறைவாகவும் இருக்கும் இரண்டு மதிப்புகளைத் தேர்ந்தெடுக்கவும். இந்த மதிப்புகள் ஒரே மாதிரியாக இருக்கக்கூடாது.
   • மதிப்பு 1 = 1
   • மதிப்பு 2 = 2
3. 3 எண் 1 மற்றும் எண் 2 க்கான MMI (கணித பெருக்கல் தலைகீழ்) கணக்கிடுங்கள்.
   • எம்எம்ஐ கணக்கிடுங்கள்
     • எம்எம்ஐ 1 = எண் 2 ^ -1 மோட் எண் 1
     • எம்எம்ஐ 2 = எண் 1 ^ -1 மோட் எண் 2
   • பிரைம் எண்களுக்கு மட்டும் (இது கலப்பு எண்களுக்கு ஒரு எண்ணைக் கொடுக்கும், ஆனால் அது அவரது எம்எம்ஐ ஆகாது):
     • MMI1 = (எண் 2 ^ (எண் 1-2))% எண் 1
     • எம்எம்ஐ 2 = (எண் 1 ^ (எண் 2-2))% எண் 2
   • உதாரணத்திற்கு:
     • MMI1 = (97 ^ 33)% 35
     • எம்எம்ஐ 2 = (35 ^ 95)% 97
4. 4 Log2 தொகுதிகளுக்கு ஒவ்வொரு MMI க்கும் ஒரு அட்டவணையை உருவாக்கவும்:
   • MMI1 க்கு
     • எஃப் (1) = எண் 2% எண் 1 = 97% 35 = 27
     • எஃப் (2) = எஃப் (1) * எஃப் (1)% எண் 1 = 27 * 27% 35 = 29
     • எஃப் (4) = எஃப் (2) * எஃப் (2)% எண் 1 = 29 * 29% 35 = 1
     • எஃப் (8) = எஃப் (4) * எஃப் (4)% எண் 1 = 1 * 1% 35 = 1
     • எஃப் (16) = எஃப் (8) * எஃப் (8)% எண் 1 = 1 * 1% 35 = 1
     • எஃப் (32) = எஃப் (16) * எஃப் (16)% எண் 1 = 1 * 1% 35 = 1
   • ஜோடி எண்களைக் கணக்கிடுங்கள் 1 - 2
     • 35 -2 = 33 (10001) அடிப்படை 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • எம்எம்ஐ 1 = எஃப் (33) = 1 * 27 மோட் 35
     • எம்எம்ஐ 1 = 27
   • MMI2 க்கு
     • எஃப் (1) = எண் 1% எண் 2 = 35% 97 = 35
     • எஃப் (2) = எஃப் (1) * எஃப் (1)% எண் 2 = 35 * 35 மோட் 97 = 61
     • எஃப் (4) = எஃப் (2) * எஃப் (2)% எண் 2 = 61 * 61 மோட் 97 = 35
     • எஃப் (8) = எஃப் (4) * எஃப் (4)% எண் 2 = 35 * 35 மோட் 97 = 61
     • எஃப் (16) = எஃப் (8) * எஃப் (8)% எண் 2 = 61 * 61 மோட் 97 = 35
     • எஃப் (32) = எஃப் (16) * எஃப் (16)% எண் 2 = 35 * 35 மோட் 97 = 61
     • எஃப் (64) = எஃப் (32) * எஃப் (32)% எண் 2 = 61 * 61 மோட் 97 = 35
     • எஃப் (128) = எஃப் (64) * எஃப் (64)% எண் 2 = 35 * 35 மோட் 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)
     • எம்எம்ஐ 2 = 61
5. 5 கணக்கிடு (மதிப்பு 1 * எண் 2 * எம்எம்ஐ 1 + மதிப்பு 2 * எண் 1 * எம்எம்ஐ 2)% (எண் 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 படிகளை குறைந்தது இரண்டு முறையாவது செய்யவும்.
   • படி 7 இல் 0 கிடைத்தால்:
     • எண் 1 பிரதானமாக இல்லாவிட்டால் வேறு எண் 1 ஐப் பயன்படுத்தவும்.
     • எண் 1 பிரதானமாக இருந்தால் மற்றொரு எண்ணைப் பயன்படுத்தவும். இந்த வழக்கில், நீங்கள் 6 மற்றும் 7 படிகளில் 0 ஐப் பெற வேண்டும்.
     • வெவ்வேறு பொருள் 1 மற்றும் பொருள் 2 ஐப் பயன்படுத்தவும்.
   • படி 7 இல் நீங்கள் தொடர்ந்து 0 ஐப் பெற்றால், எண் 2 மிக முக்கியமானதாக இருக்கும்.
   • எண் 1 முதன்மை இல்லை மற்றும் எண் 2 எண் 1 இன் வகுப்பாளராக இருந்தால் 1 முதல் 7 வரையிலான படிகள் பிழையை ஏற்படுத்தலாம். இரண்டு எண்களும் பிரதானமாக இருக்கும்போது விவரிக்கப்பட்ட முறை எல்லா நிகழ்வுகளிலும் வேலை செய்கிறது.
   • நீங்கள் 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.
• பெரிய எண்களுடன் பணிபுரியும் போது முரட்டு சக்தி சோதனை ஒரு கடினமான சோதனை என்றாலும், சிறிய எண்களுக்கு இது மிகவும் திறமையானது. பெரிய எண்களின் விஷயத்தில் கூட, சிறிய வகுப்பிகளைச் சோதிப்பதன் மூலம் தொடங்கவும், பின்னர் எண்களின் எளிமையைச் சரிபார்க்க மிகவும் சிக்கலான முறைகளுக்கு செல்லவும் (சிறிய வகுப்பிகள் காணப்படவில்லை என்றால்).

உனக்கு என்ன வேண்டும்

• காகிதம், பேனா அல்லது கணினி