Prime
মৌলিক সংখ্যা
ঠিক দুইটা ধনাত্মক ভাজক আছে এমন সংখ্যা (`1` আর নিজে)। Cryptography-র ভিত্তি, কারণ গুণ করা সহজ কিন্তু factor করা কঠিন।
also: prime number, primality
1 মৌলিক নয় — কারণ তাহলে unique factorisation ভেঙে পড়ত।
Fundamental theorem of arithmetic: প্রতিটা n > 1 কে
মৌলিকের গুণফল হিসেবে অনন্যভাবে লেখা যায়। (এই দাবিটা
strong induction দিয়ে প্রমাণিত।)
Primality testing:
| পদ্ধতি | জটিলতা | ধরন |
|---|---|---|
| Trial division | O(√n) | নিশ্চিত |
| Miller–Rabin | O(k log³n) | probabilistic |
| AKS | polynomial | নিশ্চিত, কিন্তু ধীর |
বাস্তবে Miller–Rabin ব্যবহার হয় — k রাউন্ডে ভুল হওয়ার
সম্ভাবনা ≤ 4⁻ᵏ। k = 40 মানে ত্রুটির সম্ভাবনা 10⁻²⁴,
hardware failure-এর চেয়েও কম। এটাই probability আর number
theory-র সংযোগ।
কেন cryptography মৌলিক ভালোবাসে: দুইটা ২০৪৮-bit মৌলিক গুণ করা মিলিসেকেন্ডের কাজ, কিন্তু ফলাফল factor করা বর্তমান জ্ঞানে অবাস্তব। এই asymmetry-ই [[rsa]]-র ভিত্তি।
সতর্কতা: Shor’s algorithm quantum computer-এ factoring polynomial সময়ে করে — তাই post-quantum cryptography নিয়ে কাজ চলছে।