یکی از سوالایی که چند سال قبل برام پیش اومد، محاسبه فاکتوریل اعداد خیلی بزرگ بود. مثلا !1000 چند می‌شه؟ یا لااقل چند رقمیه؟ تحقیقاتی کردم که نتیجه رو از طریق وب‌سایت برنامه‌نویسی و طراحی الگوریتم منتشر کرده بودم و اینجا دوباره می‌نویسم.

قضیه‌ای وجود داره که نشون می‌ده برای nهای بزرگ این رابطه برقراره:

این تقریب با بزرگتر شدن n به مقدار واقعی نزدیکتر و نزدیکتر می‌شه. مثلا برای n = 1000:

اما محاسبه‌ی این عبارت دست کمی از محاسبه‌ی خود فاکتوریل نداره. محاسبه‌ی این عبارت مثل محاسبه‌ی مستقیم فاکتوریل نیاز به کار با اعداد خیلی بزرگ داره و هر ماشین محاسبه‌گری قادر به محاسبه‌ی اون نیست. چنین عبارتی بیشتر در محاسبات حدی و به عنوان عبارت هم‌ارز !n استفاده می‌شه.

این عبارت رو با کمی تغییر می‌شه راحت‌تر محاسبه کرد. با توجه به خواص لگاریتم اعداد، لگاریتم در مبنای ده عبارت سمت راست رو در توان ده نشون می‌دم، که به ابن صورت خلاصه می‌شه:

محاسبه‌ی توان عدد ده در این حالت ساده‌تره، و از نظر عددی خیلی بزرگ نیست:

اگه قسمت صحیح و اعشاری توان رو از هم جدا کنیم:

در کل مشکل این روش اینه که هم‌ارزی بالا فقط برای nهای بزرگ برقراره، و در اون حالت هم فقط تقریبی از !n رو می‌ده.

من روش دیگه‌ای رو امتحان کردم که هم دقت بیشتری داره، و هم برای هر مقداری از n کاربرد داره.

تعریف !n به این ترتیبه:

مثل حالت قبل طرف راست رو به صورت توانی از عدد 10 می‌نویسم و از خاصیت ضرب به جمع لگاریتم استفاده می‌کنم:

پس می‌شه گفت:

این عبارت فاکتوریل عدد n رو به صورت توانی از عدد ده نشون می‌ده. محاسبه‌ هم از حاصلضرب اعداد یک تا n، به مجموع لگاریتم در مبنای ده این اعداد تبدیل می‌شه که به مراتب ساده‌تر و کوچکتر هستن. برای مثال:

این عدد تقریب خیلی بهتری نسبت به حالت اول تولید می‌کنه. هرچقدر میزان دقت محاسبات لگاریتم و مجموع اونا بیشتر باشه، عدد به دست اومده به مقدار واقعی !n نزدیکتر و نزدیکتر می‌شه.

با استفاده از این روش محاسبه می‌تونیم تعداد ارقام !n رو به دست بیاریم:

که منظور از [ ] جزء صحیح (کف) عبارت داخلشه.

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

و اما روش محاسبه:

1. قبل از هر چیز، بخاطر بیارید که در طول هفته چند بار شکلات می‌خورید. این عدد باید بزرگتر یا مساوی یک و کمتر از ده باشه! اگه بیشتر از ده تا می‌خورید، فعلا همون نه بار رو در نظر بگیرید.

2. این عدد رو در دو ضرب کنید.

3. حاصل ضرب رو با پنج جمع بزنید.

4. عدد به دست اومده رو در پنجاه ضرب کنید.

5. اگه در سال میلادی جاری، روز تولدتون رو رد کردید، حاصل مرحله قبل رو با عدد 1760، و در غیر این صورت با عدد 1759 جمع بزنید.

6. از عدد به دست اومده سال تولد میلادی خودتون رو کم کنید.

7. به یه عدد سه رقمی رسیدید. اولین رقم از سمت چپ تعداد شکلاتای مصرفی شما در هفته، و دو رقم سمت راست سن شما رو نشون می‌دن!

اما چرا اینطور شده؟

تعداد شکلاتای مصرفی در هفته رو با n و سال تولد رو با b نشون می‌دم و مراحل رو دوباره از اول طی می‌کنیم:

1. n

2. 2n

3. 2n + 5

4. 50(2n + 5) = 100n + 250

5. 100n + 250 + 1760 = 100n + 2010

6. 100n + (2010 - b)

عبارت داخل پرانتز همون سن شماست، که از کم کردن سال تولد میلادی از سال جاری میلادی به دست اومده. با فرض اینکه شما کمتر از صد سال سن دارید، این عدد دو رقمی خواهد بود. عدد n در صد ضرب شده، که باعث می‌شه دخالتی در رقمای یکان و دهگان حاصل نهایی نداشته باشه. در نتیجه دو رقم سمت راست عدد نهایی سن شما رو نشون می‌ده؛ و بالاخره، با توجه به اینکه عدد n تک رقمی انتخاب شد، رقم صدگان یا همون اولین رقم از سمت چپ، تعداد شکلاتای مصرفی شما در هفته خواهد بود.

به این ترتیب با ترفندای محاسباتی ساده، سن شما از روی تعداد شکلاتای مصرفی هفته به دست اومد.

بد نیست بدونید که:

1- نیازی نیست تعداد شکلاتایی که در هفته می‌خورید کمتر از ده تا باشه. داخل عدد نهایی به دست اومده، دو رقم سمت راست (به اصطلاح ریاضی، دو رقم کم ارزش) سن شماست، و بقیه‌ی ارقام تعداد شکلاتایی هستن که در طول هفته می‌خورید.

2- اگه قصد دارید محاسبه رو برای کسی انجام بدید که صد سال به بالا سن داره، باید مراحل چهار و پنج رو طوری تغییر بدید که در آخر، عدد n در هزار ضرب شده باشه.

3- این الگوریتم فقط برای سال جاری میلادی (2010) جواب می‌ده. برای سال‌های دیگه باید اعداد مرحله پنج رو تغییر بدید. مثلا برای سال 2011، حاصل مرحله چهار باید به ترتیب با عدد 1761 یا 1760 جمع بشه.

4- می‌شه این الگوریتم رو بومی‌سازی کرد. یعنی طوری تغییر داد که به جای سال میلادی از سال شمسی استفاده کرد.

5- شما در یکی از مراحل تاریخ تولد خودتون رو وارد محاسبه می‌کنید. پس این روش برای محاسبه سن به تاریخ تولد نیاز داره. توضیحاتی هم که دادم نشون می‌دن، تعداد شکلاتای مصرفی هیچ تاثیری در محاسبه سن نداره. پس می‌شه گفت کلاه سرمون رفته! محاسبه سن اصلا ربطی به شکلات نداشته.

همه می‌گویند: گل باشی و عمر گل نداشته باشی.

و من می‌گویم: گالوا باشی و عمر گالوا نداشته باشی.

اواریست گالوا (Évariste Galois) ریاضیدان نابغه‌ی فرانسوی، بیست سال و هفت ماه و شش روز از تولدش گذشته بود که در یک دوئل کشته شد.

یادش گرامی ...

امروز به سرم زد ایمیل‌های قدیمی خودم رو چک کنم و ببینم چی واسه کی فرستادم؟ به یه ایمیل با متن اجغ وجغ برخوردم که طبق معمول رفتم سراغ تغییر Encoding صفحه، تا شاید متنش خوانا شه. اما فایده نداشت.

وقتی شروع نامه و آخرش رو خوندم حس کردم هر حرف فارسی با یه نشان از زبان دیگه جایگزین شده. اولین کلمه‌ی نامه "ÓáÇã" بود که حدس زدم باید "سلام" باشه. و همینطور از خداحافظی آخر نامه هم چند حرف رو بیرون کشیدم. بعدش کلماتی وجود داشتن که فقط یه حرفشون نامشخص بود و می‌شد حدس زد اون یه حرف چیه؟ با همین حدس زدنا پیش رفتم و حدود نیم ساعت بعد متن فارسی کامل رو در کمال افتخار به دست آوردم!

استفاده از رمزنگاری در متون مهم و حساس قدمت زیادی داره. در یونان قدیم به روش خیلی جالبی متن نامه رو به رمز می‌نوشتن. سزار روم هم روشی برای رمزنگاری استفاده می‌کرده که امروزه به روش رمزنگاری سزار مشهور شده. به این ترتیب که به جای هر حرف از متن اصلی، سومین حرف بعد از این حرف در الفبای زبانشون رو جایگزین می‌کرده. مثلا در زبان انگلیسی به جای A از D و به جای Y از B استفاده می‌شده. وقتی هم که قرار بوده نامه خونده بشه عکس این عمل رو انجام می‌دادن.

شکستن این کدها اصلا کار سختی نیست. مخصوصا امروزه با پیشرفت علوم و بالا رفتن سرعت محاسبات، شکستن چنین رمزایی وقت چندانی نمی‌بره. همونطور که من خودم به صورت دستی در کمتر از یه ساعت متنی رو که به روش جایگزینی رمز شده بود رمزگشایی کردم. در روش جایگزینی هر حرف با حرف دیگه‌ای از همون زبان یا یه علامت عوض می‌شه. بزرگترین مشکل این روش اینه که با توجه به زیاد بودن تعداد حروف زبان‌های رایج، هر دو طرف باید کل اطلاعات مربوط به اینکه هر حرف با چه حرف یا علامتی جایگزین شده رو همراه خودشون داشته باشن. خیلی کم پیش می‌یاد کسی بتونه همه‌ی این اطلاعات رو در ذهن خودش داشته باشه و مطمئن هم باشه که هرگز فراموش نمی‌کنه. مثل این می‌مونه که شماره‌ی رمز کارت بانکی خودتون رو روی کاغذی کنار خود کارت نگه دارید! در این صورت اگه مفقود یا دزیده بشه، یابنده یا دزد می‌تونه به حساب شما دسترسی داشته باشه. با همه‌ی این تفاسیر امروزه از این روشای ابتدایی برای رمز کردن اطلاعات استفاده نمی‌شن.

تمامی روشهای رمزنگاری برای انجام عملیات خودشون از کلید رمز استفاده می‌کنن. با تغییر این کلید، متن رمز شده تغییر پیدا می‌کنه. پس می‌شه گفت این کلید رمز نقش مهمی در سری باقی موندن متن رمز شده ایفا می‌کنه. مثلا کلید رمز روش سزاری عدد 3 بود. اگه قرار بذاریم که به جای سومین حرف، دهمین حرف بعدی رو جایگزین حروف متن اصلی بکنیم، در اون صورت کلید رمز ما عدد 10 خواهد بود. هر کس که از این عدد خبر نداشته باشه، نمی‌تونه متن رمز شده رو به متن اصلی برگردونه. مگه اینکه بخواد به روش آزمون و خطا همه‌ی حالت‌ها رو امتحان کنه، که در روشای رمزنگاری امروزی اصلا جوابگو نیست. کلید رمزهای امروزی دامنه‌ی بسیار بزرگی رو شامل می‌شن که قوی‌ترین ابررایانه‌ها هم به این سادگی‌ها از پسشون بر نمی‌یان. در ضمن ممکنه به صورت اتفاقی رمزگشایی با یه کلید رمز اشتباه، متنی رو تولید کنه که از نظر مفهومی (مثلا دستور زبان) کاملا درست به نظر ییاد. یا اینکه مثلا فرض کنید متن اصلی یه شماره‌ی حسابه که رمز شده. این متن رمز شده با هر کلیدی باز بشه تبدیل به یه عدد می‌شه که طبیعتا نمی‌شه تشخیص داد کدوم یکی شماره‌ی حساب واقعیه.

در کل دو روش اساسی برای رمز کردن اطلاعات وجود داره.

رمزنگاری متقارن: در این روش کلید رمز کردن متن و کلید گشایش رمز یکی هستن. به عبارت دیگه با همون کلیدی که متن رمز شده، همون کلید هم متن رو از رمز بیرون می‌یاره. مثل در اتاق که برای باز و بسته کردن اون از یه کلید استفاده می‌کنیم. روش‌های DES، 3-DES، AES از این دست روش‌ها هستن.

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

اصول کرکهف:

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

1- سیستم رمزنگاری اگرنه به لحاظ تئوری که در عمل باید غیرقابل شکست باشد.

2- اصل اساسی کرکهف: سیستم رمزنگار باید هیچ نکته‌ی پنهان و محرمانه‌ای نداشته باشد. بلکه تنها چیزی که باید سری نگاه داشته شود، کلید رمز است. طراح سیستم رمزنگار نباید جزئیات سیستم خود را حتی از دشمنان مخفی نگاه دارد.

3- کلید رمز باید به گونه‌ای قابل انتخاب باشد که اولا بتوان براحتی آنرا عوض کرد و ثانیا بتوان آنرا به خاطر سپرد و نیازی به یادداشت کردن کلید رمز نباشد.

4- متون رمزنگاری شده باید از طریق خطوط تلگراف قابل مخابره باشند.

5- دستگاه رمزنگاری یا اسناد رمزشده باید توسط یک نفر قابل حمل باشد.

6- سیستم رمزنگاری باید به سهولت قابل راه‌اندازی و کاربردی باشد. چنین سیستمی نباید به آموزش‌های مفصل و رعایت فهرست بزرگی از قواعد و دستورالعمل‌ها نیاز داشته باشد.

از بین این اصول، اصل دوم به اصل اساسی کرکهف مشهوره که معمولا رعایت می‌شه. به این ترتیب هیچ روش رمزنگاری معتبر و استاندارد عمومی وجود نداره که روش رمزنگاری یا رمزگشایی اون از کسی مخفی باشه. بزرگترین رقابت هم زمانی پیش می‌یاد که سعی می‌شه با در دست داشتن این روش‌ها راه‌هایی برای نفوذ در اونا یا شکستن ساده‌تر متون رمزشده توسط اونا پیدا کرد.

بحث در این مورد بسیار مفصله و کتابا و مقالات زیادی هم در موردش نوشته شده. فعلا به همین مقدار بسنده می‌کنم. خود من هم روی یه روش رمزنگاری کار می‌کنم که فعلا به طور کامل به نتیجه نرسیده.

پی‌نوشت: بعد از تلاشی که برای تبدیل متن اجغ وجغ به متن فارسی کردم، تازه متوجه شدم که ایمیل دیگه‌ای اصل متن فارسی رو داشته!

اوایل آشنایی من با نشریه همراه با ریاضی بود که برای اولین بار (و البته آخرین بار!) با جناب احمد خان پیشرو اصل در محل دفتر نشریه دیداری داشتم. این گل پسر از نویسندگان فعال و پرکار اون دوران نشریه بود و سال اول ورودش به دانشگاه. در همون دیدار، مساله‌ای رو که دانشگاه در موردش بحث کرده بودن مطرح کرد. ظاهرا استادشون حل الگوریتمی مساله رو (نوشتن کد برنامه‌نویسی) از دانشجوها خواسته بود. اما برای احمد این سوال مطرح بود که آیا راه حل مستقیم ریاضی هم وجود داره؟ و اینگونه بود که من روی حل مساله کار کردم و خیلی زود به جواب رسیدم!

هتلی رو با 100 اتاق در بسته در نظر بگیرید که با شماره‌های 1 تا 100 مشخص شدن. قراره از این هتل 100 نفر با شماره‌های 1 تا 100 بازدید کنن. به این ترتیب که هر کس با وارد شدن به ساختمان هتل، تمام در اتاقایی رو که شماره‌ی اونا مضرب صحیحی از شماره‌ی خودش باشه تغییر وضعیت می‌ده. یعنی اگه در بسته باشه، باز می‌کنه و اگه باز باشه، می‌بنده. به عنوان مثال نفر شماره‎ی 3 در اتاقای شماره‌ی 3، 6، 9 و مضارب بعدی 3 رو که کوچکتر یا مساوی 100 هستن تغییر وضعیت می‌ده. سوال اینه که بعد از تموم شدن بازدید همه‌ی افراد، چه تعداد در باز وجود خواهد داشت؟

برای رسیدن به جواب مساله، به جای 100 عدد n را فرض می‌گیریم. در صورتی که بتونیم به نتیجه مطلوب برسیم، مساله نه تنها برای 100، که برای تمام اعداد طبیعی حل خواهد شد.

حل این مساله را با طرح یک سوال شروع می‌کنم:

سوال 1- هر کدوم از درها در چه شرایطی تغییر وضعیت می‌دن؟

پاسخ به این سوال چندان هم سخت نیست. بر اساس صورت مساله، هر شخص فقط درهایی رو تغییر وضعیت می‌ده که شماره‌ی اتاق مضرب صحیحی از شماره‌ی خودش باشه. پس هر در توسط افرادی تغییر وضعیت داده می‌شه که شماره‌ی اتاق بر شماره‌ی اونا قابل قسمت باشه. این عبارت در عالم ریاضیات معادل اینه که شماره‌ی شخص مقسوم‌علیه شماره‌ی اتاق باشه.

نتیجه‌ی 1- هر در به تعداد مقسوم‌علیه‌های شماره‌ی اتاق تغییر وضعیت می‌ده.

حالا سوال بعدی:

سوال 2- چه دری در پایان بازدیدها باز می‌مونه؟

هر در تنها دو وضعیت باز یا بسته رو داره. همچنین همه‌ی درها در ابتدا بسته هستن. تغییر وضعیت هم به صورت متناوب بین دو حالت انجام می‌شه. پس اگه به طور مثال دو بار تغییر وضعیت بدیم، در مجددا بسته می‌شه. با یه حساب سر انگشتی نتیجه می‌گیریم:

نتیجه‌ی 2- درهایی باز می‌مونن که به تعداد فرد بار تغییر وضعیت داده باشن.

با ترکیب نتایج 1 و 2 به نتیجه‌ی زیر می‌رسیم:

نتیجه‌ی 3- درهایی در پایان بازدید باز می مونن که تعداد مقسوم‌علیه‌های شماره‌ی اتاقشون عدد فردی باشه.

راه زیادی تا حل مساله باقی نمونده!

سوال 3- کدوم اعداد طبیعی تعداد مقسوم‌علیه‌هاشون فرده؟

برای پاسخ به این سوال کمی باید به اطلاعات قبلی خودمون مراجعه کنیم.

می‌دونیم که هر عدد طبیعی دلخواه i رو می‌شه به صورت

نوشت، که p_jها اعداد اول هستن. چنین نمایشی - صرف نظر از ترتیب p_jها - برای هر عدد طبیعی منحصر به فرده.

به لم‌های زیر توجه کنید:

لم 1- فرض کنید عدد n به صورت فوق نمایش داده شده باشد. در این صورت تعداد مقسوم علیه‌های آن برابر است با:

لم 2- فرض کنید a و b دو عدد صحیح باشند. در اینصورت حاصلضرب ab فرد است، اگر و فقط اگر هر دو عدد فرد باشند.

اثبات این دو لم کتابای مختلف اومده و من ازشون صرف نظر می‌کنم. البته چیز چندان پیچیده‌ای هم نیست. کمی زمان و حوصله می‌خواد.

از نتیجه‌ی 3 فهمیدیم که باید سراغ اعدادی بریم که تعداد مقسوم‌علیه‌های اونا فرد هستن. لم 1 در پاسخ سوال 3 نشون می‌ده که تعداد مقسوم‌علیه‌های یه عدد طبیعی - اگه به صورت تجزیه اون به اعداد اول نوشته بشه - از رابطه‌ی زیر محاسبه می‌شه:

پس ما دنبال اعدادی هستیم که برای اونا حاصلضرب بالا عدد فردی باشه. لم 2 این کار را برای ما انجام داده: تنها زمانی عبارت فوق فرد خواهد بود که تک تک عبارتای داخل پرانتز فرد باشن؛ و این یعنی اینکه تک تک α_jها باید زوج باشن.

پس:

پس عدد n باید مربع کامل باشه.

در صورتی که مساله را به صورت دستی حل کنید، می‌بینید که درهای 1، 4، 9، 16 و ... تنها درهایی هستن که در پایان بازدید باز می‌مونن. تعداد چنین اعدادی در بازه 1 تا n برابره با: (چرا؟؟؟)

که منظور از [ ] علامت جزء صحیحه.