کارگاه علمی تجزیه اعداد صحیح

Workshop on Integer Factorization

کارگاه علمی تجزیه اعداد صحیح

شاخه دانشجويي انجمن رمز ايران در دانشگاه صنعتي شريف کارگاه علمی تحت عنوان تجزیه اعداد صحیح (Integer Factorization) را با مدیریت فرشید فرحت رئیس شاخه و همکاری اعضای خود در دانشکده ریاضی در روز 6 خرداد ماه سال جاري در سالن کهرباي دانشکده مهندسي برق دانشگاه صنعتي شريف برگزار کرد. هدف از برگزاري اين کارگاه علمی آموزشي آشناکردن پژوهشگران شاغل در دانشگاه و صنعت با مفاهيم تجزیه اعداد بود که در ادامه موضوعات مورد بحث در کارگاه به تفصيل بيان شده است.

مسابقه تجزیه اعداد

به 3 نفر از برگزیدگانی که عدد 103 رقمی زیر را تجزیه کنند، جوایزی از طرف انجمن رمز ایران اهدا خواهد شد.

248961597133671436654819868443345749095434319307711171205566690 4025046627241207850771410070555734313594220859

لطفا پاسخ های خود را به همراه توضیحی مختصر از نحوه تجزیه، حداکثر تا تاریخ 1388/3/31 به آدرس sharif at isc.org.ir ارسال نمایید.

برنامه زمان بندی کارگاه علمی

9-9:10 تلاوت آیاتی چند از کلام الله مجید

9:10-9:15 پخش سرود ملی جمهوری اسلامی ایران

9:15-9:35 سخنرانی افتتاحیه

9:35-9:45 سخنرانی فرشید فرحت رئیس شاخه دانشجویی (دانشجوی دکتری شریف)

9:45-11 سمینار مساله تجزیه اعداد و گواهی دیجیتال (آقای بهزاد خزایی، کارشناسی ارشد شریف)

11-11:15 زمان تنفس و استراحت

11:15-12 سمینار مبانی ریاضی و روشهای کلاسیک در تجزیه اعداد (خانم نادرخانی، کارشناسی)

12-13:30 وقت نماز و ناهار

13:30-14:30سمینار GNFS (آقای پویان فرزاد، کارشناسی ارشد شریف)

14:30-15:30سمینار SNFS (آقای طالبی زاده، کارشناسی شریف)

15:30-16 طرح ستار (آقای بهزاد خزایی، کارشناسی ارشد شریف)

16-16:20 سخنرانی اختتامیه

همانطور كه مي دانيم بسياري از روش هاي رمزنگاري متداول، خصوصا در سيستم هاي رمز با كليد رمزگذاري عمومي (RSA و ... )، امنيت وابسته به پيچيدگي مساله تجزيه اعداد صحيح به عوامل اول است. براي اين مساله با پيشينه تاريخي بيش از 2500 ساله، الگوريتم هاي مختلفي از جمله ‍CFRAC، SQUFOF، QS، MPQS، SNFS، GNFS، روش هاي كوانتومي، خم هاي بيضوي و .... پيشنهاد شده است. اگر چه بعضي از اين روش ها در حالات خاص كارايي خوبي دارند اما در حالت كلي،‌ مساله تجزيه اعداد صحيح كماكان تنها در زمان نمايي نسبت به عدد، ممكن است. بنابراين حفظ سلامت تبادلات اطلاعات كشور، در گرو توان آن براي تجزيه اعداد چند صد رقمي است؛ كه علاوه بر توسعه امكانات سخت افزاري لازم، نيازمند تحقيقاتي جدي در زمينه الگوريتم هاي تجزيه اعداد است.

بر اين اساس پیشنهاد می شود که برگزاری یک كارگاه يك روزه در تجزيه اعداد در شاخه دانشجویی انجمن رمز ايران در دانشگاه صنعتی شریف، با محتوای زیر لحاظ شود:

1. معرفی کلاس های پیچیدگی محاسبه P، NP و بیان اهمیت مسائل NP-complete در رمزنگاری و جایگاه مساله تجزیه اعداد در این رده بندی. مرور بعضي روش هاي رمزنگاري كه امنيت در آنها بر پيچيدگي تجزيه اعداد به عوامل اول، استوار است. دراین بخش با مروری اجمالی بر سیستم رمز با کلید عمومی به معرفی سیستم RSA و ... به تاریخچه تجزیه اعداد RSA-129 و RSA- 130 و ... خواهیم پرداخت.

2. مباني رياضي از نظريه اعداد شامل قضیه کوچک فرما، قضیه باقیمانده درجه 2 به هنگ عدد اول p، اعداد شبه اول، میدان های متناهی، لگاریتم لگاریتم گسسسته، خم هاي بيضوي و ... كه در تجزيه اعداد مورد كاربرد قرار مي گيرند. بر اساس فصل 1-4 مرجع [1]

3. روش های کلاسیک در تجزيه اعداد از جمله غربال درجه 2 (QS)، خم های بیضوی، M-B، و مقایسه پیچیدگی آنها. بر اساس فصل 4و5 مرجع [1] و مرجع [2]

4. معرفی غربال مبتنی بر میدان اعداد (GNFS و SNFS) و تعیین پیچیدگی محاسبه آنها. بر اساس مرجع [3]

5. معرفي محك هاي جديد چند جمله اي در تعيين اول يا مركب بودن اعداد كه مساله اي به مراتب ساده تر از تجزيه به عوامل اول است. بر اساس مرجع [4]

6. مسائل پیاده سازی الگوریتم های تجزیه در حالت offline و online و استفاده از کامپیوتر های کوانتومی برای تجزیه اعداد

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

اين كارگاه براي دانشجويان سال هاي آخر كارشناسي و كارشناسي ارشد كه با مفاهيم بنيادين رمزشناسي آشنا هستند،‌ طراحي شده و سعي مي شود مقدمات اساسي بحث در كارگاه يادآوري شود. همچنين فایل ارائه ها و مقالات مهم در زمينه تجزيه اعداد در اختیار شركت كندگان در كارگاه قرار خواهد گرفت.

[1] Koblitz N. , A Course in Number Theory and Cryptography, Springer-Verla

[2] A. K. Lensra, Integer Factoring, Design, Codes and Cryptography, 19, 101-128 (2000)

[3] A. K. Lenstra, H. W. lenstra, Jr., The development of the Number Field Sieve, Lecture notes in Math., Springer-Verlag (1993)

[4] M. Agrawal, N. Kayal, N. Saxena, Primes is in P, Annals of Mathematics, 160 (2004), 781-793.