CalcOpenly
தமிழ்

பகாக் காரணிப்படுத்தல் கணிப்பான்

60 இலக்கங்கள் வரையிலான முழு எண்ணைப் பகா காரணிகளாகப் பிரியுங்கள். காரணி மரம், பகா அல்லது பகுபடு எண் முடிவு, வகுத்திகள், அருகிலுள்ள பகா எண்களும் கிடைக்கும்.

செயற்கை நுண்ணறிவு எழுத்துக் கருவிகளால் வரைவு உருவாக்கப்பட்டதுபுதுப்பிக்கப்பட்டது சரிபார்க்கப்பட்ட எடுத்துக்காட்டுகள்: 6

60 இலக்கங்கள் வரை. 2^67 − 1 போன்ற கோவைகளையும் பயன்படுத்தலாம்.
முயற்சிக்கவும்
பகா காரணி பிரிப்பு
2³ × 3² × 5
பகா காரணி பிரிப்பு: 2³ × 3² × 5
பகா எண்ணா, பகுபடு எண்ணா
பகுபடு எண்
வகுத்திகளின் எண்ணிக்கை
24
வகுத்திகளின் கூட்டுத்தொகை σ(n)
1,170
முந்தைய பகா எண்
359
அடுத்த பகா எண்
367

360 = 2³ × 3² × 5; எனவே இது பகுபடு எண். இதன் 24 வகுத்திகளின் கூட்டுத்தொகை 1170. அருகிலுள்ள பகா எண்கள் 359, 367.

காரணி மரம்

360218029024531535
வகுத்தி ஜோடிகள் வரிசைகள்: 12
வகுத்திஇணை வகுத்தி n ÷ d
1360
2180
3120
490
572
660
845
940
1036
1230
1524
1820
கணக்கிடும் முறை S

  1. சிறிய பகா எண்களால் சோதனை வகுத்தல்

    2, 3 ஆகியவற்றால் வகுபடும்.

    அடுத்த பகா எண்ணிற்குச் செல்வதற்கு முன், தற்போதைய பகா எண்ணால் முடிந்தவரை மீண்டும் மீண்டும் வகுக்கப்படுகிறது.

  2. பகா காரணி பிரிப்பு

    360=23×32×5360 = 2^{3} \times 3^{2} \times 5

  3. வகுத்திகளின் எண்ணிக்கை

    d(n)=(3+1)(2+1)(1+1)=24d(n) = (3 + 1)(2 + 1)(1 + 1) = 24

  4. வகுத்திகளின் கூட்டுத்தொகை

    σ(n)=24−12−1⋅33−13−1⋅52−15−1=1,170\sigma(n) = \frac{2^{4} - 1}{2 - 1} \cdot \frac{3^{3} - 1}{3 - 1} \cdot \frac{5^{2} - 1}{5 - 1} = 1{,}170

  5. அருகிலுள்ள பகா எண்கள்

    359<360<367359 < 360 < 367

    இதே Miller–Rabin சோதனையால் அடுத்தடுத்த எண்களும் சோதிக்கப்படுகின்றன.

பகாக் காரணிப்படுத்தல் கணிப்பான் பற்றி

அரித்மெடிக்கின் அடிப்படைத் தேற்றப்படி, 1-ஐ விடப் பெரிய ஒவ்வொரு முழு எண்ணையும் வரிசையைத் தவிர ஒரே விதத்தில் பகா எண்களின் பெருக்கற்பலனாக எழுதலாம்: 360 = 2³ × 3² × 5. கணிப்பான் முதலில் சோதனை வகுத்தலால் 10,000-க்குக் குறைவான பகா காரணிகளை நீக்குகிறது; பெரிய பகுபடு காரணிகளை Pollard rho முறையின் Brent வடிவத்தால் பிரிக்கிறது. பின்னர் முதல் 13 பகா அடிமானங்களில் Miller–Rabin சோதனையால் ஒவ்வொரு காரணியின் பகாத்தன்மையைச் சோதிக்கிறது; 3.3 × 10²⁴-க்குக் கீழே இது தீர்மானமானது (Sorenson மற்றும் Webster, 2015).

பின்னங்கள், மூலங்களைச் சுருக்குதல், பொதுப் பகுதிகளைக் காணுதல், எண் புதிர்கள் ஆகியவை காரணி பிரிப்பிலிருந்து தொடங்குகின்றன. அடுக்குகளைக் கொண்டு வகுத்திகளையும் எண்ணலாம்: 360-க்கு (3 + 1)(2 + 1)(1 + 1) = 24 வகுத்திகள் உள்ளன; அவற்றின் கூட்டுத்தொகை 1,170. அருகிலுள்ள பகா எண்கள் 359, 367.

2^67 − 1 போன்ற கோவைகள் உட்பட 60 இலக்கங்கள் வரையிலான எண்களை ஏற்கிறது. 3317044064679887385961981 அல்லது அதற்கு மேல் சோதனையில் தேரும் முடிவு ‘பகா எண்ணாக இருக்கக்கூடியது’ எனக் குறிக்கப்படும். இங்கு பயன்படுத்தும் 20 நிலையான அடிமானங்கள் ஒவ்வோர் உள்ளீட்டிற்குமான பிழை நிகழ்தகவு உறுதியைத் தருவதில்லை.

பகா காரணிகளாகப் பிரிப்பது

பகா எண்ணிற்கு 1, அதே எண் என இரண்டு நேர்ம வகுத்திகள் மட்டுமே இருக்கும். 1-ஐ விடப் பெரிய ஒவ்வொரு முழு எண்ணையும் பகா எண்களின் பெருக்கற்பலனாக எழுதலாம். 360-ஐப் படிப்படியாக 2, 2, 2, 3, 3, 5 ஆகியவற்றால் வகுத்தால் 1 கிடைக்கும்; சுருக்கமாக 360 = 2³ × 3² × 5. காரணிகளின் வரிசை மாறினாலும் இந்த அமைப்பு மாறாது.

ஒரு நேர்ம முழு எண்ணை உள்ளிடவும். 360, தமிழ் இலக்கங்களில் ௩௬௦, அல்லது 2^67-1 போன்ற கோவையைப் பயன்படுத்தலாம். அதிகபட்சம் 60 இலக்கங்கள்; 10⁶⁰ ஏற்கப்படாது. தசமங்கள், பூச்சியம், எதிர்ம எண்களுக்கு இந்தப் பிரிப்பு செய்யப்படாது.

உள்ளீடுபகா காரணி வடிவம்வகுத்திகளின் எண்ணிக்கைவகுத்திகளின் கூட்டுத்தொகை
1பகா காரணிகள் இல்லை11
122² × 3628
9797298
3602³ × 3² × 5241170
10242¹⁰112047

1 பகா எண்ணும் அல்ல, பகுபடு எண்ணும் அல்ல. அதன் ஒரே நேர்ம வகுத்தி 1. 97 ஒரு பகா எண்; அதற்கு முந்தைய பகா எண் 89, அடுத்தது 101. அருகிலுள்ள பகா எண் வெளியீடுகள் உள்ளீட்டிற்கு கண்டிப்பாகக் கீழும் மேலும் உள்ள எண்களைக் காட்டும்.

வகுத்திகளின் எண்ணிக்கையும் கூட்டுத்தொகையும்

n = p₁^e₁ × p₂^e₂ × … எனில், ஒவ்வொரு வகுத்திக்கும் ஒவ்வோர் அடுக்கையும் பூச்சியம் முதல் e வரை தேர்ந்தெடுக்கலாம். எனவே எண்ணிக்கை (e₁ + 1)(e₂ + 1)… . 360-க்கு (3 + 1)(2 + 1)(1 + 1) = 24. அதன் கூட்டுத்தொகை (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 × 13 × 6 = 1170.

வகுத்தி ஜோடிகளில் ஒவ்வொரு வரியின் இரு எண்களையும் பெருக்கினால் அசல் எண் கிடைக்க வேண்டும். 360-க்கு 12 × 30 = 360; ஒரு முழு வர்க்கத்தில் நடு ஜோடியின் இரு எண்களும் ஒன்றாக இருக்கும். வகுத்திகளின் எண்ணிக்கை அதிகமாக இருந்தால் முழுப் பட்டியல் காட்டப்படாது. காரணி மரமும் இடவசதிக்காகச் சுருக்கப்படலாம்; அது மட்டும் கணக்கு முழுமையற்றது என்பதைக் குறிக்காது.

பெரிய எண்களின் முடிவை வாசிப்பது

முதலில் 10,000-க்குக் குறைவான பகா எண்களால் சோதனை வகுத்தல் நடக்கும். பெரிய இணைக் காரணிகளுக்கு Brent-இன் Pollard rho முறை பயன்படுத்தப்படுகிறது. ஒரு பெரிய பகுபடு காரணியை நேர வரம்பிற்குள் பிரிக்க முடியாவிட்டால் அது தனியாகக் குறிக்கப்படும்; வகுத்திகளின் எண்ணிக்கையும் கூட்டுத்தொகையும் காட்டப்படாது. 60 இலக்கங்கள் ஏற்கப்படுவது, அந்த அளவிலுள்ள ஒவ்வோர் எண்ணும் முழுமையாகப் பிரிக்கப்படும் என்ற உறுதி அல்ல.

முதல் 13 பகா அடிமானங்களைக் கொண்ட Miller–Rabin சோதனை, 3317044064679887385961981-க்குக் கீழே தீர்மானமானது; இந்த எல்லை Sorenson–Webster ஆய்வில் தரப்படுகிறது. அந்த எல்லையில் அல்லது அதற்கு மேல் இந்தக் கருவி 20 நிலையான அடிமானங்களைச் சோதிக்கிறது. தேரும் முடிவு பகா எண்ணாக இருக்கக்கூடியது; பகாத்தன்மையின் நிரூபணம் அல்ல. பெரிய காரணிகள், அருகிலுள்ள பகா எண்கள், அவற்றைச் சார்ந்த வகுத்திக் கணக்குகளையும் இந்த வரம்புடன் வாசிக்கவும்.

சீரற்ற அடிமானங்களுக்கான பிழை நிகழ்தகவு வரம்பை இங்குள்ள நிலையான அடிமானங்களுக்கு அப்படியே பயன்படுத்த முடியாது; Applied Cryptography நூலின் சோதனை விளக்கம் இந்த வேறுபாட்டை விவரிக்கிறது. பகா காரணிகளைக் கொண்டு பொதுக் காரணிகள், பொதுமடங்குகளைக் காண GCD/LCM கணிப்பான், மூலங்களைச் சுருக்க அடுக்குகள் மற்றும் மூலங்கள் உதவும்.

தீர்க்கப்பட்ட எடுத்துக்காட்டுகள்

360

முழு எண்
360
பகா காரணி பிரிப்பு
2³ × 3² × 5
பகா எண்ணா, பகுபடு எண்ணா
பகுபடு எண்
வகுத்திகளின் எண்ணிக்கை
24
வகுத்திகளின் கூட்டுத்தொகை σ(n)
1,170
முந்தைய பகா எண்
359
அடுத்த பகா எண்
367

சரிபார்ப்பின் மூலம்: சுயாதீன கணக்கீடு

Project Euler பயிற்சி 3

முழு எண்
600851475143
பகா காரணி பிரிப்பு
71 × 839 × 1471 × 6857
வகுத்திகளின் எண்ணிக்கை
16

சரிபார்ப்பின் மூலம்: எடுத்துக்காட்டு சரிபார்ப்பு: Project Euler #3-இன் மிகப்பெரிய பகா காரணி 6857

Cole-இன் 2^67 − 1 காரணி பிரிப்பு

முழு எண்
2^67-1
பகா காரணி பிரிப்பு
193707721 × 761838257287
பகா எண்ணா, பகுபடு எண்ணா
பகுபடு எண்
வகுத்திகளின் எண்ணிக்கை
4

சரிபார்ப்பின் மூலம்: எடுத்துக்காட்டு சரிபார்ப்பு: F. N. Cole, 1903 (Bull. AMS 10:134); இரு காரணிகளின் பெருக்கற்பலனும் பகாத்தன்மையும் சோதனை வகுத்தலால் சரிபார்க்கப்பட்டன

97 ஒரு பகா எண்

முழு எண்
97
பகா காரணி பிரிப்பு
97
பகா எண்ணா, பகுபடு எண்ணா
பகா எண்
வகுத்திகளின் எண்ணிக்கை
2
வகுத்திகளின் கூட்டுத்தொகை σ(n)
98
முந்தைய பகா எண்
89
அடுத்த பகா எண்
101

சரிபார்ப்பின் மூலம்: எடுத்துக்காட்டு சரிபார்ப்பு: பகா எண் பட்டியல் (OEIS A000040): 89, 97, 101

கேள்விகள்

ஓர் எண்ணைப் பகா காரணிகளாக எப்படிப் பிரிப்பது?

மீதியின்றி வகுக்கும் மிகச்சிறிய பகா எண்ணால் வகுத்து, ஈவு 1 ஆகும் வரை தொடரவும். 360-க்கு: 360 ÷ 2 = 180, ÷ 2 = 90, ÷ 2 = 45, ÷ 3 = 15, ÷ 3 = 5. மேலும் 5 பகா எண்; எனவே 360 = 2³ × 3² × 5. மீதமுள்ள எண்ணின் வர்க்கமூலம் வரையிலான பகா எண்களை மட்டும் சோதித்தால் போதும்; எதுவும் வகுக்காவிட்டால் மீதி ஒரு பகா எண்.

1 ஒரு பகா எண்ணா?

இல்லை. பகா எண்ணிற்கு 1, அதே எண் எனத் துல்லியமாக இரண்டு வகுத்திகள் இருக்கும்; 1-க்கு ஒன்று மட்டுமே உள்ளது. 1-ஐ விலக்குவதால் காரணி பிரிப்பு தனித்துவமாகிறது: 1-ஐப் பகா எண்ணாகக் கொண்டால், 6-ஐ 2 × 3, 1 × 2 × 3, 1 × 1 × 2 × 3 என எழுதலாம். 1 பகா எண்ணும் அல்ல, பகுபடு எண்ணும் அல்ல; 2 மிகச்சிறிய பகா எண், ஒரே இரட்டைப் பகா எண்ணும் அதுவே.

பகா காரணிகளிலிருந்து வகுத்திகளின் எண்ணிக்கையை எப்படிக் காண்பது?

ஒவ்வோர் அடுக்குடனும் 1-ஐக் கூட்டிப் பெருக்கவும். 360 = 2³ × 3² × 5¹ என்பதால் (3 + 1)(2 + 1)(1 + 1) = 24 வகுத்திகள் உள்ளன. ஒவ்வொரு வகுத்தியிலும் 0 முதல் 3 வரை இரண்டுகள், 0 முதல் 2 வரை மூன்றுகள், 0 அல்லது 1 ஐந்து அமையலாம். வகுத்திகளின் கூட்டுத்தொகையும் இதே போன்ற பெருக்கற்பலன்: σ(360) = (2⁴ − 1)/1 × (3³ − 1)/2 × (5² − 1)/4 = 15 × 13 × 6 = 1,170.

ஒரு பெரிய எண் பகா எண்ணா என்பதை எப்படிக் கண்டறிவது?

20 இலக்க எண்களுக்கு √n வரை சோதனை வகுத்தல் மிகவும் மெதுவாக இருக்கும்; எனவே Miller–Rabin சோதனை சில அடிமானங்களைச் சோதிக்கிறது. 3.3 × 10²⁴-க்குக் கீழே முதல் 13 பகா எண்களை (2 முதல் 41 வரை) அடிமானங்களாகக் கொண்டு தேர்வது பகாத்தன்மையை நிரூபிக்கும் (Sorenson மற்றும் Webster, 2015). 2⁶¹ − 1 = 2,305,843,009,213,693,951 தேர்கிறது; அது பகா எண். 2⁶⁷ − 1 தோற்கிறது; அது 193,707,721 × 761,838,257,287.

மறையாக்கத்தில் பகா காரணி பிரிப்பு ஏன் பயன்படுகிறது?

இரு பெரிய பகா எண்களைப் பெருக்குவது விரைவாகவும் அவற்றின் பெருக்கற்பலனைக் காரணிகளாகப் பிரிப்பது நடைமுறையில் மிகவும் மெதுவாகவும் இருப்பதை RSA மறையாக்கம் பயன்படுத்துகிறது. NIST SP 800-57-இல் சுமார் 617 தசம இலக்கங்கள் கொண்ட 2048-பிட் RSA மாடுலஸின் பாதுகாப்பு 112 பிட்கள் என மதிப்பிடப்படுகிறது. அது இங்குள்ள 60-இலக்க வரம்பைப் போலப் பத்து மடங்கு நீளம். இந்த வரம்பிற்குள்ளும் ஒரு காரணி ஒப்பீட்டளவில் சிறியதாக இருந்தால்தான் Pollard rho விரைவாகப் பிரிக்கும்.

இந்தக் கணிப்பான் பற்றி

n=p1e1p2e2⋯pkekd(n)=∏(ei+1)σ(n)=∏piei+1−1pi−1\begin{gathered} n = p_1^{e_1} p_2^{e_2}\cdots p_k^{e_k} \\[6pt] d(n) = \prod (e_i + 1) \\[6pt] \sigma(n) = \prod \frac{p_i^{e_i+1} - 1}{p_i - 1} \end{gathered}

ஆதாரங்கள்

  1. Hardy & Wright, An Introduction to the Theory of Numbers, §2.10 and §16.7 (divisor functions)
  2. Sorenson & Webster (2015), Strong pseudoprimes to twelve prime bases
  3. Brent (1980), An improved Monte Carlo factorization algorithm

ஆதாரங்களுடன் சரிபார்க்கப்பட்டது

இந்தக் கணிப்பானில் சுயாதீன ஆதாரங்களிலிருந்து பதில்கள் பெறப்பட்ட 6 தீர்க்கப்பட்ட எடுத்துக்காட்டுகள் உள்ளன. இவை சோதனைத் தொகுப்பில் இயங்குகின்றன; இங்கேயும் அவற்றை இயக்கலாம்.

இந்தக் கணிப்பானை உங்கள் தளத்தில் சேர்த்துக்கொள்ளுங்கள்

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

உயரம்
உட்பொதிப்பின் முன்னோட்டத்தைப் பார்

நன்றிக் குறிப்பை அப்படியே வைத்திருங்கள். இது ஒன்றே நிபந்தனை, இதுவே இந்தக் கணிப்பான்களை இலவசமாக வைத்திருக்கிறது.

தொடர்புடைய கணிப்பான்கள்