Discrete Log Problem

ডিসক্রিট লগ সমস্যা

g, p, আর y = g^x mod p দেওয়া থাকলে x বের করা কঠিন — অথচ x জানা থাকলে y গণনা করা তুচ্ছ; এই এক-দিকে-সহজ, উল্টো-দিকে-কঠিন অসাম্যই Diffie-Hellman ও ElGamal-এর trapdoor।

also: dlp, discrete logarithm, discrete logarithm problem

forward (সহজ):   x, g, p জানা  ->  y = g^x mod p     -- fast modular exponentiation
backward (কঠিন): y, g, p জানা  ->  x = ?              -- কোনো known efficient classical algorithm নেই

Forward গণনা square-and-multiply দিয়ে p-এর বিট-সংখ্যায় লগারিদমিক সময়ে হয়
Backward (discrete log বের করা) brute-force-এ p-এর সমানুপাতিক সময় লাগে — সেরা classical algorithm-ও sub-exponential
p যথেষ্ট বড় (আজকের DH-এ ~২০৪৮+ বিট) হলে backward দিক ব্যবহারিকভাবে অসম্ভব — এটাই trapdoor function-এর সংজ্ঞা
Elliptic-curve সংস্করণে (ECDLP) একই অসাম্য অনেক ছোট key-তেই পাওয়া যায় — আধুনিক ECC-এর ভিত্তি