שאלה

[טיקטי1]

שאלה

איך הגיעו לזה שהסיבוכיות של אלגוריתם שיכול לפצח קוד שהוצפן בשיטת rsa הוא שתיים בחזקת n (לפחות עד עכשיו)?

 

[דפנה ר]

אני חושבת...

אפילו אלגוריתם נאיבי יצליח למצוא האם מספר ראשוני בסבוכיות זמן פולינומיאלית בערך המספר תחת O. למשל לעבור על כל המספרים האי-זוגיים עבור מספר גדול משתיים, עד לשורש המספר. אבל הסבוכיות לאורך המספר הופכת להיות מעריכית אחרי שמציבים את אורך המספר.

 

[דפנה ר]

אה ושכחתי, נכון עד לפיתוח האלגוריתם

על ידי שלושת ההודים

 

[טיקטי1]

תודה רבה, התכוונתי לסיבוכיות שלוקחת

בחשבון את כמות הספרות במספר אני אשמח לתשובה עים התחשבות באורך המספר ד"א האלגוריתם שלהם לא התגלה כטעות?

 

[1ca1]

קודם כל האלגוריתם של ההודים טוב

הבעיה הוא שהוא מקבל מספר, ומסוגל רק להחליט האם הוא ראשוני או לא, בשביל RSA, העבודה לא נגמרת כאן, אם הוא לא ראשוני יש לפקטר אותו, וכיום אין אלגוריתמים יעילים לכך, דרך אגב יש נראה אלגוריתמים אם סיבוכיות יותר נמוכה מ2 בחזקת n, אבל עדיין לא סבירה...

 

[טיקטי1]

תודה רבה, יש לך במקרה קישור

לפתרון של ההודים? ואיך מגיעים ל2 בחזקת n? תודה מראש

 

[psychedMux]

../images/Emo11.gif אני מכיר את s מ-rsa!

עדי שמיר, ישראלי למהדרין, רחובותי למהדרין, אבא למהדרין של חבר לתיכון. עכשיו אני מחלק חתימות. מי רוצה להכיר את האיש שמכיר את האיש ששם משפחתו מרכיב את rsa? ניפגש במתנ"ס.