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

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

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

فرض کنیم گروه حلقوی 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_۱۷) لگاریتم گسستهٔ عدد ۱۳ در مبنای ۳ برابر با ۴ می‌باشد. توجه داشته باشید که لگاریتم گسسته دارای جواب واحد نیست ، به طور مثال 3 به توان 20 به پیمانه ی 17 به عدد 13 می رسد و لذا یک جواب دیگر می تواند عدد 20 باشد (این نوشته چندان معتبر نمی باشد و بایستی به کتب معتبر ریاضی برای تایید آن مراجعه نمایید)

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

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

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

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

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

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

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

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

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

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

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

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

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

منابع

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