لگاریتم گسسته

توابع لگاریتم گسسته در ریاضیات و جبر، دسته‌ای از توابع هستند که مشابه با تابع لگاریتم معمولی و روی گروه‌های عددی تعریف می‌شوند.

تعریف ریاضی این توابع به شکل ساده به صورت زیر است:

فرض کنیم گروه حلقوی G با n عضو عدد صحیح، بر مبنای عمل ضرب دارای مولدی مانند b باشد. با این فرض می‌توان هر عضو g از گروه G را به صورت g = b^k نوشت که در این رابطه k عددی صحیح است و برای هر g و b مشخص، مقادیر مختلفی برای k وجود دارد که همگی اعضای یک کلاس همنهشتی به پیمانهٔ n می‌باشند.

بر این اساس تابع لگاریتم گسسته در مبنای b، تابعی است از G به Z_n (حلقهٔ اعداد صحیح به پیمانهٔ n) که به هر عضو g از مجموعهٔ G، کلاس همنهشتی k به پیمانهٔ n را نسبت می‌دهد:

$\log _{b}:\ G\ \rightarrow \ \mathbf {Z} _{n}$

$\forall g\in G\ \exists k\in \mathbf {Z} _{n},\log _{b}(g)=[[k]]_{n},b^{k}\equiv g{\pmod {n}}$

مثال عددی

برای مثال مجموعهٔ Z_۱۷ را در نظر می‌گیریم. این مجموعه به صورت {۱۶،...،۰،۱،۲} می‌باشد که مجموعهٔ باقیمانده‌ها در تقسیم به عدد اول ۱۷ = p هستند.

ابتدا در این مجموعه عمل توان گسسته را در نظر می‌گیریم. برای محاسبهٔ ۳^۴ در این مجموعه، کافی است نخست ۸۱ = ۳^۴ را محاسبه نموده و سپس باقیماندهٔ تقسیم حاصل به ۱۷ = p را به دست آوریم: ۸۱mod ۱۷ = ۱۳

محاسبهٔ لگاریتم گسسته عکس این عمل خواهد بود، به این صورت که در همنهشتی به پیمانهٔ ۱۷ = p (یا به عبارت دیگر در مجموعهٔ Z_۱۷) لگاریتم گسسته‌ی عدد ۱۳ در مبنای ۳ برابر با ۴ می‌باشد. توجه داشته باشید که لگاریتم گسسته دارای جواب واحد نیست ، به‌طور مثال ۳ به توان ۲۰ به پیمانه‌ی ۱۷ به عدد ۱۳ می رسد و لذا یک جواب دیگر می‌تواند عدد 20 باشد .

مسئلهٔ لگاریتم گسسته

مسئلهٔ لگاریتم گسسته همان حل کردن معادلهٔ (a^x ≡ b (mod p برای مجهول x است و به دلیل کاربردی که در ریاضیات و به خصوص در رمزنگاری پیدا کرده‌است به صورت یک اصطلاح درآمده‌است.

حل کردن مسئلهٔ لگاریتم گسسته (محاسبهٔ لگاریتم گسسته) از دیدگاه ریاضی معادل با حل کردن مسئلهٔ تجزیهٔ اعداد صحیح در نظر گرفته می‌شود و وجوه اشتراکی بین آن دو وجود دارد:

• هر دو مسئله جزو مسائل دشوار ریاضی هستند، به این معنی که روش سریعی برای حل کردن آن‌ها پیدا نشده است.
• هر الگوریتم مرتبط با یکی از این دو مسئله، قابل تبدیل به الگوریتم مشابهی در ارتباط با مسئلهٔ دیگر می‌باشد.
• از دشوار بودن حل هر دو مسئله، برای طراحی و ایجاد سیستم‌های رمزنگاری مختلفی استفاده شده‌است.

الگوریتم‌های محاسبه

هنوز هیچ الگوریتم سریعی برای محاسبهٔ لگاریتم گسسته در حالت کلی یافته نشده است. ساده‌ترین الگوریتمی که برای حل مسئلهٔ (a^x ≡ b (mod p می‌توان فرض کرد، این است که مقدار a را به توانِ اعدادِ صحیحِ متوالی از ۱ به بالا برسانیم تا جایی که مقدار b حاصل شود و به این ترتیب مقدار x مورد نظر را بیابیم. این روش حل، به صورت سعی و خطا می‌باشد و مدت زمان لازم برای دستیابی به نتیجه در این روش بر حسب تعداد ارقام پیمانهٔ p به صورت نمایی خواهد بود.

به مرور زمان و عمدتاً در مشابهت با الگوریتم‌های مختلف تجزیهٔ اعداد صحیح، الگوریتم‌های مختلفی برای حل مسئلهٔ لگاریتم گسسته مطرح شده‌است که سریع‌تر از الگوریتم بالا می‌باشند:

• الگوریتم گام کوچک گام بزرگ
• الگوریتم رو پولارد
• الگوریتم لاندای پولارد
• الگوریتم پولیگ-هلمن
• الگوریتم جبر اندیسی
• الگوریتم غربال میدان عددی

کاربرد در رمزنگاری

مسئلهٔ لگاریتم گسسته یکی از مسائل دشوار ریاضی است و معکوس آن یعنی محاسبهٔ توان گسسته به سادگی قابل انجام است. این عدم تقارن در دشواری دو مسئلهٔ معکوس، برای تحقق سیستم‌های رمزنگاری مختلفی مورد استفاده قرار گرفته‌است که از آن جمله می‌توان به این موارد اشاره کرد:

• پروتکل تبادل کلید دیفی-هلمن
• الگوریتم امضای رقومی استاندارد
• الگوریتم رمز الجمل

جستارهای وابسته

• مسائل دشوار ریاضی
• لگاریتم
• گروه عددی

منابع

• ویکی‌پدیای انگلیسی