கீழ்நோக்கி முழுமைப்படுத்தல், பூச்சியத்தை நோக்கிச் சுருக்குதல், யூக்ளிட் வழக்கு ஆகியவற்றில் a mod n-ஐக் காணுங்கள். பெரிய எண்களின் a^b mod m, மாடுலர் தலைகீழி ஆகியவையும் படிகளுடன் கிடைக்கும்.
எழுதியவர்: Adminசெயற்கை நுண்ணறிவு எழுத்துக் கருவிகளால் வரைவு உருவாக்கப்பட்டதுபுதுப்பிக்கப்பட்டது சரிபார்க்கப்பட்ட எடுத்துக்காட்டுகள்: 10
−17 ÷ 5-இல் ஈவைக் கீழ்நோக்கி −4 ஆக்கினால் மீதி 3 (Python, Excel MOD); பூச்சியத்தை நோக்கி −3 எனச் சுருக்கினால் மீதி −2 (C, JavaScript %).
Python %, Excel MOD, பெரும்பாலான கணித நூல்கள் ஈவைக் கீழ்நோக்கி முழுமைப்படுத்துகின்றன.
C, Java, JavaScript ஆகியவற்றின் % ஈவைப் பூச்சியத்தை நோக்கிச் சுருக்கும்.
a-ஐ n-ஆல் வகுத்த மீதியை a mod n குறிக்கிறது. நேர்ம எண்களுக்கு எல்லா வழக்குகளும் ஒன்றே (17 mod 5 = 2). எதிர்ம எண்களுக்கு அவை வேறுபடுகின்றன: r = a − n⌊a/n⌋ என்ற கீழ்நோக்கி முழுமைப்படுத்திய மீதி வகுத்தியின் குறியை ஏற்கும்; ஈவைப் பூச்சியத்தை நோக்கிச் சுருக்கிய மீதி வகுபடும் எண்ணின் குறியை ஏற்கும்; யூக்ளிட் மீதி எதிர்மமாகாது. கணிப்பான் மூன்றையும் காட்டுகிறது. மாடுலர் அடுக்குகளுக்கு வர்க்கப்படுத்திப் பெருக்கும் முறையும் தலைகீழிக்கு நீட்டிக்கப்பட்ட யூக்ளிட் முறையும் பயன்படும்.
கடிகாரம், நாட்காட்டி, ஹாஷிங், சுழல் இடையகங்கள் ஆகியவற்றில் மீதிகள் பயன்படும்; மறையாக்கத்தில் மாடுலர் அடுக்குகள் பயன்படும். தொடக்கக் கணக்கு −17 mod 5-க்கு கீழ்நோக்கி முழுமைப்படுத்தலில் 3 (Python %, Excel MOD); பூச்சியத்தை நோக்கிச் சுருக்கினால் −2 (C, JavaScript %). பாடநூல் RSA எடுத்துக்காட்டில் 65 என்பது 65^17 mod 3233 = 2790 என மறையாக்கப்படுகிறது.
ஒவ்வொரு வர்க்கமும் mod m-ஆல் குறைக்கப்படுவதால் 10^18 போன்ற பெரிய அடுக்குகளுக்கும் மாடுலர் கணக்கு துல்லியமாக இருக்கும். gcd(a, m) = 1 ஆக இருந்தால் மட்டுமே a⁻¹ mod m தலைகீழி உண்டு.
மாடுலோ கணக்கில் a-ஐ n-ஆல் வகுத்து மீதியைக் காண்கிறோம். a = n·q + r என்ற சமன்பாட்டில் ஈவு q-ஐத் தேர்ந்தெடுக்கும் விதம், எதிர்ம எண்களுக்கு மீதியை மாற்றும். முதன்மை விடை கீழ்நோக்கி முழுமைப்படுத்திய மீதி; துணை விடைகளில் பூச்சியத்தை நோக்கிச் சுருக்கிய மீதியும் எதிர்மமற்ற யூக்ளிட் மீதியும் கிடைக்கும்.
| a | n | கீழ்நோக்கி முழுமைப்படுத்திய மீதி | சுருக்கிய மீதி | யூக்ளிட் மீதி |
|---|---|---|---|---|
| 17 | 5 | 2 | 2 | 2 |
| −17 | 5 | 3 | −2 | 3 |
| 17 | −5 | −3 | 2 | 2 |
| −17 | −5 | −2 | −2 | 3 |
| 7.5 | 2 | 1.5 | 1.5 | 1.5 |
| 12 | 3 | 0 | 0 | 0 |
கீழ்நோக்கி முறையில் q = ⌊a/n⌋. −17 ÷ 5 = −3.4 என்பதால் q = −4; மீதி −17 − 5·(−4) = 3. சுருக்கும் முறையில் q = −3; மீதி −2. யூக்ளிட் முறையில் எப்போதும் 0 ≤ r < |n|. மீதி பூச்சியமெனில் குறியைப் பற்றிய வேறுபாடு இல்லை.
Python %, Excel MOD கீழ்நோக்கி முறையைப் பயன்படுத்துகின்றன; JavaScript % பூச்சியத்தை நோக்கிச் சுருக்கும் மீதியைத் தருகிறது. Microsoft Research-இன் வகுத்தல் வரையறைகள் இந்த வழக்குகளை வேறுபடுத்துகின்றன. நிரல் முடிவுடன் ஒப்பிடும்போது அதே வழக்கைத் தேர்ந்தெடுக்கவும்.
முழு எண்கள், தசமங்கள், 1/3 போன்ற பின்னங்களை a, n புலங்களில் உள்ளிடலாம். தமிழ் இலக்கங்களில் −௧௭, ௫ கொடுத்தாலும் முதன்மை விடை 3. வகுத்தி பூச்சியமாகக் கூடாது. முடிவுறாத பின்னம் அல்லது நீண்ட முழு எண்ணிற்கு துல்லிய மதிப்புப் புலம் கூடுதலாக வரும். விகிதமுறா கோவைக்கு 50-இலக்கத் தசம அணுகுமதிப்பு பயன்படுத்தப்படுவதை எச்சரிக்கை குறிப்பிடும்.
அடுக்கு முறையில் அடிமானம் a, அடுக்கு b, மாடுலஸ் m ஆகியவை முழு எண்களாக இருக்க வேண்டும்; m நேர்மம். 4^13 mod 497 = 445. அடுக்கை இரும வடிவில் எழுதி ஒவ்வொரு பிட்டிலும் வர்க்கப்படுத்தி, தேவைப்பட்டால் பெருக்கி, mod m-ஆல் குறைக்கும் முறை பெரிய இடைநிலை எண்ணை முழுமையாக உருவாக்குவதைத் தவிர்க்கிறது.
2^(10^18) mod 1000000007 = 719476260. இங்கு ^ அடுக்கைக் குறிக்கிறது; 10^18 என்பது அடுக்குப் புலத்தில் இடப்படும் கோவை. கணிப்பான் அடுக்கின் தனிமதிப்பை 4096 பிட்களுக்கும் மாடுலஸை 2048 பிட்களுக்கும் வரையறுக்கிறது. மாடுலஸ் 1 எனில் விடை 0.
a·x ≡ 1 (mod m) ஆகும் x-ஐத் தலைகீழி முறை காணும். m குறைந்தது 2; gcd(a, m) = 1 ஆக இருக்க வேண்டும். 3-இன் mod 11 தலைகீழி 4; 3 × 4 = 12 = 11 + 1. 2-க்கு mod 10-இல் தலைகீழி இல்லை; பொதுக் காரணி 2 உள்ளது.
எதிர்ம அடுக்கு முறையும் தலைகீழியைப் பயன்படுத்தும்: 3^(−2) mod 11 = 5. அது சாதாரண தசமத் தலைகீழி அல்ல; 1/3-ஐ தசமமாக மாற்றி மீதி காண வேண்டாம். நீட்டிக்கப்பட்ட யூக்ளிட் படிகளைக் GCD/LCM கணிப்பானுடன் ஒப்பிடலாம். RSA போன்ற சிறிய எடுத்துக்காட்டுகள் கணிதப் பயிற்சிக்கானவை; இந்தக் கருவி மறையாக்கச் சாவிகளை உருவாக்குவதில்லை.
சரிபார்ப்பின் மூலம்: எடுத்துக்காட்டு சரிபார்ப்பு: பைதான் 3.8-இல் -17 % 5 = 3; சுருக்கிய மீதி (-17, 5) = -2.0; கீழ்நோக்கி வகுத்தல் -17 // 5 = -4
சரிபார்ப்பின் மூலம்: எடுத்துக்காட்டு சரிபார்ப்பு: பைதான் 3.8-இல் 17 % -5 = -3; சுருக்கிய மீதி (17, -5) = 2.0; யூக்ளிட் மீதி 17 − 5·⌊17/5⌋ = 2
சரிபார்ப்பின் மூலம்: எடுத்துக்காட்டு சரிபார்ப்பு: பைதான் 3.8-இல் 7.5 % 2 = 1.5
சரிபார்ப்பின் மூலம்: எடுத்துக்காட்டு சரிபார்ப்பு: Wikipedia மாடுலர் அடுக்கு எடுத்துக்காட்டு; தனிக் கணக்கில் (4, 13, 497) அளவுகளுக்கு விடை 445
வகுத்து, ஈவைக் கீழ்நோக்கி முழுமைப்படுத்திக் கழிக்கவும்: a mod n = a − n⌊a/n⌋. 17 mod 5-க்கு 17 ÷ 5 = 3.4; கீழ்நோக்கி 3; எனவே 17 − 5 × 3 = 2. −17 mod 5-க்கு −3.4 என்பது −4 ஆகும்; −17 − 5 × (−4) = 3. 12-மணி கடிகாரத்தில் 15:00 என்பது 15 mod 12 = 3 மணி.
அவை ஈவை வெவ்வேறு விதமாக முழுமைப்படுத்துகின்றன. Python %-இல் கீழ்நோக்கிச் செல்லுவதால் −17 % 5 = 3; மீதிக்கு வகுத்தியின் குறி. JavaScript, C, Java ஆகியவை பூச்சியத்தை நோக்கிச் சுருக்குவதால் −17 % 5 = −2; மீதிக்கு வகுபடும் எண்ணின் குறி. இரண்டிலும் a = n × q + r பொருந்தும். Excel MOD என்பது Python போலவே. JavaScript-இல் நேர்ம n-க்கு ((a % n) + n) % n கீழ்நோக்கி முழுமைப்படுத்திய விடையைத் தரும்.
வர்க்கப்படுத்திப் பெருக்கவும்: அடுக்கை இரும வடிவில் எழுதி மீண்டும் மீண்டும் வர்க்கப்படுத்தி, ஒவ்வொரு படியிலும் mod m-ஆல் குறைக்கவும்; அப்போது எண்கள் m²-ஐத் தாண்டாது. 4^13 mod 497-இல் 13-இன் இரும வடிவம் 1101; விடை 445. இது Python pow(4, 13, 497)-க்கும் சமம். முதலில் 4^13 = 67,108,864 எனக் கணக்கிடுவது இங்கு சாத்தியம்; 10^18 போன்ற அடுக்குகளுக்கு ஏற்றதல்ல.
a × x ≡ 1 (mod m) ஆகும் x, a-இன் மாடுலர் தலைகீழி. 3 × 4 = 12 = 11 + 1 என்பதால் 3⁻¹ mod 11 = 4. gcd(a, m) = 1 எனில் மட்டுமே இது உண்டு; எனவே mod 10-இல் 2-க்குத் தலைகீழி இல்லை. நீட்டிக்கப்பட்ட யூக்ளிட் முறை இதைக் காணும். பாடநூல் RSA எடுத்துக்காட்டில் 17 × 2753 = 46,801 = 15 × 3120 + 1 என்பதால் தனிச் சாவி 2753 என்பது mod 3120-இல் 17-இன் தலைகீழி.
நேர்ம எண்களுக்கு இரண்டும் ஒன்றே: 17-ஐ 5-ஆல் வகுத்த மீதி 2. எதிர்ம எண்களுக்கு C, JavaScript மீதி வகுபடும் எண்ணின் குறியை ஏற்கும் (−17 rem 5 = −2). கணித மாடுலோவின் ஒரு வழக்கில் வகுத்தியின் குறியும் மற்றொன்றில் எதிர்மமற்ற மீதியும் பயன்படுத்தப்படும் (−17 mod 5 = 3). வேறுபடும்போது இரு விடைகளுக்கும் உள்ள வித்தியாசம் துல்லியமாக |n|.
இந்தக் கணிப்பானில் சுயாதீன ஆதாரங்களிலிருந்து பதில்கள் பெறப்பட்ட 10 தீர்க்கப்பட்ட எடுத்துக்காட்டுகள் உள்ளன. இவை சோதனைத் தொகுப்பில் இயங்குகின்றன; இங்கேயும் அவற்றை இயக்கலாம்.