שאלות קריפטולוגיה ואלגברה מודרנית.

[shirbi]

שאלות קריפטולוגיה ואלגברה מודרנית.

אני מקווה שהפורום הזה הוא המקום המתאים לכך. אני מתאמן למבחן בקריפטולוגיה ונתקלתי בשאלה שלא הצלחתי לפתור: בהינתן P ראשוני, צריך למצוא את המספרים שהעלתם בחזקת 3 במודולו P יתנו 1. לא ידוע הפירוק של P-1 לגורמים. האם קיים אלגוריתם יעיל שעושה זאת? אם הבנתי נכון, אז אם 3 לא מחלק את P-1, אז יש ל 1 רק שורש שלישי אחד, והוא 1 עצמו. אם 3 כן מחלק את P-1 אז יש לו שלושה שורשים: אם g הוא היוצר של החבורה הכפלית במודולו P-1, אז השורשים הם: 1, g בחזקת (P-1 חלקי 3) ו g בחזקת (2 כפול (P-1 חלקי 3)). הבעיה היא איך שלמצוא את היוצר כאשר הפירוק של P-1 לא ידוע, זה דבר שאין לי מושג איך לעשות אותו. האם יש דרך אחרת יותר יעילה? תודה מראש.

 

[vinney]

איפה כל המתמטיקאים?

דווקא הייתי אמור לדעת את זה אבל אני זורק

הקורמן לא לידי ואני לא זוכר את זה בעל פה... אם מצאת פתרון, אשמח אם תשתף אותי גם

 

[yossiea]

מצטרף...

גם אני הייתי שמח לשמוע על פתרון כזה אם ישנו. א. בספר של קורמן לא ראיתי התייחסות לזה מלבד כמה מילים הייתי שמח, ויני אם תוכל להפנות אותי לעמוד שבו יש התייחסות מפורטת אצל קורמן לעניין הזה. ב. בכל מקום שנתקלתי בזה, הדרכים הכי יעילות שהיו עבדו עם הגורמים של p-1ויש כמה אלגוריתמים ידועים וטובים. אז מה הבעיה פשוט לפרק את p-1?. מלבד זאת בקריפטוגרפיה נמנעים מזה, פשוט על ידי בחירה מראש של ראשוני כזה כאשר p-1 ידוע ואפשר למצוא יוצר מסדר גבוה ביתר קלות. אני מנסה לחשוב על רעיון אם מספר היוצרים גבוה אולי באלגוריתם הסתברותי אפשר לעשות את זה מהר יותר מאפשר לפרק את p-1. נניח לחפש a אקראי שעונה על התנאי האמור. אני כמעט בטוח שאני טועה. אחרת בוודאי שהייתי מוצא התייחסות כלשהי לזה. צריך לחשוב על זה...

 

[shirbi]

זוהי שאלה ממבחן

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

 

[The Albatross]

אתה לומד בטכניון?

 

[shirbi]

כן.

 

[johnny d]

אני חושב שהפתרון ממש פשוט

אלא אם כרגיל לא הבנתי את השאלה. נתון ש p ראשוני, ומספר b המקיים את המשוואה: a = b^3 mod p ואתה צריך למצוא את a. b הוא יוצר של החבורה הכפלית: Z_p מכיוון ש p ראשוני ולכן ניתן למצוא את ההפכי בעזרת אלגוריתם אוקלידס המורחב. אם זה שאלה ממבחן, בטח התכוונו שתפתרו את זה ביד. אני שונא אלגברה (ביד) למה המציאו מחשבים.

 

[johnny d]

אופס,להתעלם לחלוטין מהשטויות שכתבתי

מעבר לבלאגן השלם שכתבתי על חומר שרחוק ממני זה כרגיל בכלל לא הייתה השאלה. השאלה אם כן היא האם ניתן לכתוב אלגוריתם יעיל לפתרון הבעיה. התשובה היא כמובן לא. שכן ישנם שני מקרים, האם p-1 מתחלק ב3 או לא, ואת זה ניתן לבדוק בנקל בזמן ליניארי. העניין הוא במקרה בו p-1 מתחלק ב3 ולכן קבוצה זו מכילה יותר מהמסר 1 עצמו. במקרה זה ניתן להוכיח אם איני טועה כי גודל הקבוצה הוא לפחות p-1 / 3 , משמעות העניין היא שפלט האלגוריתם הוא אקספוננציאלי לגודל הקלט ולכן לא קיים אלגוריתם יעיל לפתרון הבעיה.