மில்லர்-ரபின் பகா எண் சோதனைக் கணிப்பான்

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

மில்லர்-ரபின் சோதனை, n − 1 ஐ 2ˢ·d என (d ஒற்றைப்படை) எழுதி, ஒரு சாட்சி அடிப்படை a ஆனது ஏதேனும் r < s க்கு aᵈ ≡ 1 (mod n) அல்லது a^(2ʳ·d) ≡ −1 (mod n) ஐ நிறைவு செய்கிறதா என்று பார்த்து பகா எண் தன்மையைச் சோதிக்கிறது. ஒரு சாட்சி மட்டும் நிகழ்தகவு அடிப்படையிலான முடிவையே தரும்; ஆனால் நிரூபிக்கப்பட்ட சிறிய நிலையான சாட்சி அடிப்படைகளின் தொகுப்புக்கு (எடுத்துக்காட்டாக 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) எதிராகச் சோதிப்பது, ஏறத்தாழ 3.18 × 10²³ க்குக் கீழுள்ள ஒவ்வொரு முழு எண்ணுக்கும் சோதனையை உறுதியானதாக ஆக்குகிறது — பெரும்பாலான பயன்பாடுகளுக்குத் தேவையானதை விட மிக அதிகம்.

குறியாக்கவியலாளர்களும் மென்பொருள் உருவாக்குநர்களும் RSA அல்லது Diffie-Hellman விசைகளுக்கான பெரிய பகா எண் வேட்பாளர்களை உருவாக்கும்போது இதே வகைச் சோதனையைப் பயன்படுத்துகின்றனர்; கணினி அறிவியல் மாணவர்கள் ஒரு பெரிய முழு எண் பகா எண்ணா என்று பார்க்க, வகுத்துச் சோதிக்கும் முறையைவிட மில்லர்-ரபின் ஏன் மிகச் சிறப்பாக அளவுகோலுக்கு ஏற்ப இயங்குகிறது என்பதை நிஜ எண்களில் பார்க்க இதைப் பயன்படுத்துகின்றனர்.