Workshop on Integer Factorization

Workshop on Integer FactorizationWorkshop 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-Verlag

[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.

Comments

Post a Comment

Popular posts from this blog

System and methods for UICC-based secure communication

ABSTRACT A system that incorporates the subject disclosure may include, for example, instructions which when executed cause a device processor to perform operations comprising sending a service request to a remote management server; receiving from the management server an authentication management function and an encryption key generator for execution by a secure element and an encryption engine for execution by a secure device processor, sending a request to establish a communication session with a remote device; and communicating with the remote device via a channel established using an application server. The secure element and the secure device processor authenticate each other using a mutual authentication keyset. The secure element, the secure device processor and the device processor each have a security level associated therewith; the security level associated with the secure device processor is intermediate between that of the secure element and that of the device processor....
Read more

Computer Vision Keywords

2D attacks 2D Face 2D Face Authentication 3D blood flow estimation 3D Face 3D Face Localisation 3D face model 3D face recognition 3D localization 3D Masks 3D model base indexing 3D object recognition abnormality detection accelerated exact k-means Accent Identification Accented speech Accentual mismatch accessible games acoustic frequency Acoustic model adaptation acoustic modeling Acoustic reverberation sparsity models Acoustic reverberation structures Acoustic signal processing acoustic stream acquisition ACT metric activation function active shape model activity Actor–critic Ad hoc array calibration Ad hoc microphone array calibration Adaboost adalaine adaptive exploration/exploitation trade-off adaptive learning rate adaptive resonance theory adaptive steepness Addressee estimation Adequacy of diffuseness Ad-hoc microphone array Adhoc microphone array calibration Ad-hoc microphone array calibration Ad-hoc microphone calibration AFC A...
Read more