שאלה לגבי אלגוריתם RSA

[theuser1]

שאלה לגבי אלגוריתם RSA

שלום שוב! יש לי תרגיל שבו שואלים אותי להוכיח משהו, ואני קצת תקוע, אשמח כמו פעם שעברה לקצת עידוד בכיוון הנכון. נתון לי שני מספרים ראשונים, Q,P ונגדיר prod=Q * P נגדיר (r= (q-1) * (p-1 הוכח ש R הוא מספר המספרים שבין 1 ל - PROD הזרים ל-PROD אז חשבתי בכיוון שכל המספרים שהם קטנים ממש מQ וקטנים ממש מP (הקטן מביניהם) הם בוודאי זרים ל PROD (כי הם ראשונים). אח"כ גם כל המספרים הראשונים בין Q או P לבין PROD הם זרים. אבל איך אני מגיע מזה לסכום R? תודה!

 

[yossiea]

אני הייתי אומר...

לפי אויילר, עובדה: עבור p ראשוני כלשהו, כל המספרים מ-1 עד p-1 הם זרים ל-p. אז הדברים נכונים גם לגבי הכפולות של ראשוניים. (אני מניח שאתה לא צריך להוכיח את משפט אויילר). אני חושב שקל להוכיח שהקבוצה (q-1)*(p-1) זרה p*q. טוב אני לא יודע איך לנסח לך את זה, זה נשמע לי פשוט מאוד

. אם a זר ל-b אז גם כפולה של a זרה ל-b לא? מקווה שעזרתי.

 

[אמיתי ר]

גם אני מתלבט בשאלה!

מכיר את התרגיל... בכל מקרה הכיוון שלי דומה לזה של יוסי, כלומר כל מספר הקטן ממש מ P הוא בוודאי זר. כעת, גם אם תכפול את המספרים הללו בכל מספר אחר, קטן ממש מ Q תקבל מכפלה שהיא זרה ל PQ. לכן כמות המספרים שיש לך היא (p-1) * (q-1). כעת אתה צריך גם לראות את הכיוון השני, כלומר שאין עוד מספרים זרים. נניח ויש מספר שהוא זר ל PQ, הוא כמובן קטן מ PQ, והוא גדול מהמכסימלי בין P וQ (נניח לצורך הפשטות שהמכסימלי הוא P). נקרא לו U. במה נכפיל אותו כדי לקבל את PQ? כמובן במספר שהוא קטן מ P, אבל הרי קודם כבר התחשבנו בכל המספרים שהם קטנים ממש מP, ולכן כבר התחשבנו במספר הזר "הנוסף" הזה. מה שכן, אני מתלבט איך כותבים את הנ"ל כתשובה לשאלה שמבקשים "הוכח כי מתקיים...", כלומר משהו פורמלי.

 

[theuser1]

תודה לשניכם

אבל אני עדיין קצת תקוע. ניסיתי את שתי הדרכים ועדיין לא הצלחתי להוכיח כמו שצריך.

 

[vinney]

מה ז"א כמו שצריך?

או שהצלחת להוכיח, או שלא

תעלה את מה שכתבת, אולי אנשים יוכלו לשים לב לאיזו דקות שפיספסת או משהו כזה

 

[theuser1]

בכתב

למעשה הרעיון שכתב טוב ממני איתי: על מנת להוכיח את הטענה אראה כי מספר המספרים הזרים ל-PROD הוא לכל הפחות R, ומהכיוון השני, הוא לא גדול מ-R. כיוון ראשון: נניח בלי הגבלת הכלליות, שP קטן מ-Q. כל המספרים מאחד ועד P-1 זרים ל R. (מאחר ש P ו Q ראשוניים). לכן, גם אם נכפול אותם בכל מספר, קטן ממש מ-Q הם ישארו זרים ל R=PQ. מספר המספרים הללו הוא כמכפלתם כלומר: (p-1) * (q-1) כיוון שני: נכתב קודם על ידי איתי. משום מה זה לא נראה לי "כמו שצריך". זו לא הוכחה מתמטית.

 

[vinney]

הוכחה מתמטית

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

 

[yossiea]

הוא רוצה ניסוח קצת יותר פורמלי...

ראיתי באיזה מקום דרך להוכיח את זה באופן קצת שונה כאמור ההוכחה תקפה גם לגבי m, n שאינם ראשוניים ואז קבוצת הזרים תהיה קטנה יותר כמובן: הוכחת משפט אויילר: נניח ש-t=mn כאשר m, n זרים זה לזה. מפשט השאריות הסיני אומר ש-(a,t)=1 אם ורק אם (a,m)=1 וכן (a,n)=1 כלומר זרים זה לזה. במילים אחרות ישנה חד-חד ערכיות בין הקבוצה {a : a =1 (mod t)} לבין {a:a=1(modm) and a=1(mod n)} כעת מספר השלמים החיוביים שאינם גדולים מ-t וזרים ל-t הם בעצם גם מספר הזוגות (u,v) כאשר u<m וזר ל-m וכן v<n וזר ל-n, מכאן שקבוצת המספרים הזרים ל-m כפול קבוצת הזרים ל-n שווה לקבוצת המספרים הזרים של mn.

 

[אולף]

לא מדויק

לא מדויק... כשאתה אומר: "לכן, גם אם נכפול אותם בכל מספר, קטן ממש מ-Q הם ישארו זרים ל R=PQ" זה לא מדויק. מאחר ו-P קטן מ-Q, אתה יכול להכפיל את P-1 ב-P ואז תקבל מספר שאינו זר ל-R אם P הרבה יותר קטן מ-Q אתה יכול להכפיל את P-1 בכל מיני כפולות של P, וזה לא זר ל-R.

 

[yuvalmadar]

תקן אות אם אני טועה

אתה אומר שאם p,q ראשוניים אז pq ו(p-1)(q-1) זרים? מה עם

p = 2 q = 3 pq = 6 (p-1)(q-1) = 1 * 2 = 2​

אבל

(2,6) = 2​

 

[yuvalmadar]

בעצם אמרת...

שהקבוצה (q-1)*(p-1) זרה p*q. אז אני חושב שלא הבנתי למה התכוונת...

 

[אמיתי ר]

אתה טועה ../images/Emo13.gif

P ו Q מספרים ראשוניים. אתה נתת דוגמה בה P הוא לא ראשוני...

 

[yuvalmadar]

עכשיו ממש לא הבנתי ../images/Emo9.gif

קבעתי p=2, נכון? אז איפה הבעיה?

 

[אמיתי ר]

כי P מספר ראשוני, ושתיים לא ראשוני

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

 

[ahab]

2 לא ראשוני? ממתי?

2 מאוד ראשוני.

 

[johnny d]

2 ראשוני מאוד מיוחד

כי הוא 2 וכל השאר מספרים ראשוניים אי-זוגיים

 

[איתן333]

כשחושבים על זה, התכונה המיוחדת

שלו היא רק בראש שלנו: מספר זוגי מוגדר כמספר שמתחלק ב2, ולכן שום מספר זוגי הוא לא ראשוני. באותה מידה 17 הוא גם מיוחד, כי הוא המספר הראשוני היחיד שמתחלק ב17.

 

[johnny d]

זה לא נכון המספר 2 מקיים

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

 

[inbal76]

../images/Emo45.gif יפה אמרת!

 

[ron369]

וזה גם לא המקרה היחיד

3 ו- 13, למשל, מקיימים ש: gcd(3*13,2*12)=3 ושניהם לא מכילים את 2, או מניחים ש-2 ראשוני (לפחות לא ישירות).