שאלה

[קפטן ברני]

שאלה

האם עבור a,b טבעיים נתונים יש דרך למצוא פתרון כלשהו ל-x, שעבורו b מתחלק בביטוי:

a^x-1​

בלי לפרק את b לגורמים?

 

[ChipsMan]

בוודאי שיש ../images/Emo3.gif

לא צריך לפרק את b לגורמים. מספיק למצוא מחלק אחד ל-b. נניח והמחלק הזה הוא p. אז כל מה שעליך לעשות זה להציב:

x = log_a(p+1)​

ויש לך פתרון. אלא אם כן התכוונת גם בלי למצוא ל-b מחלקים בכלל

 

[rainbow16]

המממ... אולי..

אפשר לעשות ככה... כדי שהביטוי:

b/(a^x-1)​

יחזיר ערך טבעי כלשהו n, אז b צריך להיות מהצורה:

b=n(a^x-1) b/n+1=a^x ln(b/n+1)=xlna x=ln(b/n+1)/ln(a)=loga[(b/n)+1]​

כאשר a זה הבסיס... ועכשיו מה שנותר זה להציב ערכים וזהו....

 

[ChipsMan]

המספרים b/n

הם החלקים של b, כך שמה שאמרת זהה למה שאני אמרתי

 

[קפטן ברני]

ואם נניח

של-b יש רק שני גורמים ראשוניים, אבל הם מאוד מאוד גדולים? (בעצם מה שמעניין אותי זה פתרון רק למקרה הפרטי הזה)

 

[hitchkok]

במקרה הזה, אתה פשוט מאוד פותר

את שיטת ההצפנה rsa, מה שבינתיים אף מתמטיקאי לא הצליח לעשות, ומתעשר מאוד

 

[קפטן ברני]

צודק

פשוט תהיתי כמה זמן יקח עד שמישהו יעלה על זה... בגלל זה ניסחתי מקרה כללי יותר בהתחלה. הסבר: בשיטת ההצפנה הזו a יהיה המסר שאנחנו רוצים לפתח ו-b יהיה חלק מהמפתח הציבורי. החלק השני של המפתח ייקרא e. אם אנחנו היינו מוצאים את x - היינו יכולים למצוא גם את ההופכי הכפלי המודולרי של e בבסיס x (זה לא קשה, בזכות גרסה של האלגוריתם של אוקלידס) - וזה היה המפתח הפרטי. כלומר פיצחנו את ההצפנה. אני מצרף גם ערך מויקיפדיה בנושא RSA. (את החלק של המתמטיקה אני כתבתי...

)