השערת ריימן

[bwp2]

השערת ריימן

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

 

[Stinki Winki]

כנסי לקישור

http://www.wolfram.com/products/explorer/topics/riemann.html

 

[Stinki Winki]

מה הקשר לגנבים?

 

[Stinki Winki]

מה הקשר לגנבים?

 

[DoubleThinker]

ראשוניים זה שם המשחק

אני לא מבין גדול בהשערת רימן והשלכותיה או בהצפנות אבל לפי מה שהבנתי ההצפנות הטובות ביותר הנפוצות היום מסתמכות על העובדה שקשה לפרק מכפלה של שני ראשוניים גדולים

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

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

)

 

[1ca1]

לא מדוייק

האלגוריתם של הסיבוכיות הפולינומיאלית מסוגל רק להגיד האם מספר מסויים הוא פריק (composite) או ראשוני (prime) הוא לא מסוגל לפקטר בזמן "סביר"...

 

[galbin]

יש הבדל גדול...

בין בדיקת ראשוניות לפירוק מספר לגורמים ראשוניים. בדיקת ראשוניות היא תהליך יחסית פשוט, והאלגוריתם שהתגלה לא מזמן לבדיקת ראשוניות הוא בעיקר בעל ערך אקדמי. ידועים מזה זמן רב מבחני ראשוניות הסתברותיים (למשל מבחן מילר-רבין) אשר יכולים לוודא את הראשוניות של מספר בהסתברות כה גבוהה עד כי הסיכוי לשגיאה זניח. המבחנים האלה מהירים בהרבה מהמבחן הפולינומיאלי לראשוניות שהתגלה לא מזמן, ובפועל ממילא משתמשים בהם בד"כ. פירוק מספר לראשוניים לעומת זאת היא בעיה קשה בהרבה. לא ידוע אלגוריתם יעיל לפירוק מספר לגורמים ראשוניים, ולא ברור לי מדוע הוכחה של השערת רימן תשנה את המצב. כמו שאמרת, כבר עכשיו ניתן להניח שהשערת רימן נכונה לצרכים פרקטיים. ייתכן שמישהו מאמין שההוכחה עצמה תחשוף מידע עמוק יותר (מעבר להוכחת ההשערה עצמה) שיאפשר פירוק מהיר של מספר לגורמים ראשוניים - אבל בינתיים אין מידע כזה. כל העניין הזה מזכיר לי כתבה שהתפרסמה ב-"הידען" בזמן גילוי האלגוריתם הדטרמיניסטי לבדיקת ראשוניות, תחת הכותרת הפרובוקטיבית "המספרים הראשוניים יזוהו, הצופן יישבר". הנה קישור: http://www.hayadan.org.il/prime190802.html. שים לב שבסוף הכתבה מופיע מכתב שנשלח למערכת מד"ר למתימטיקה באוניברסיטת ת"א. המכתב אומר, בשפה מנומסת, שהמסקנות של הכתבה (בדבר הפיצוח של צופן RSA) הן קשקוש גמור. כתבים תמיד מחפשים סנסציות, אז אל תאמין לכל מה שאתה קורא בעיתון (למרות שאת הכתבה הספציפית שדובר עליה כאן לא ראיתי ולכן אני לא יכול לחוות דעה).

 

[neozigi]

משמעותי יותר אם..

במידה וייבנה מחשב קוואנטי נורמלי, ניתן להשתמש באלגוריתם יעיל לפיצוח המחלקים ( Shor's Algorithm ). אבל לדעתי ייקח כמה שנים עד שלכל פועל יהיה PQC Personal Quantum Computer ...

 

[anzas]

תמיד אפשר להשתמש במספרים

ראשוניים גדולים יותר... אני קראתי לא מזמן על הצפנה שמתבססת על eliptic curves ומאפשרת רמת אבטחה גבוהה יותר או באותה רמה כמו RSA עם מפתחות בגדלים קטנים יותר.

 

[דפנה ר]

עד כמה שאני זוכרת, במקרה הזה

הסבוכיות הופכת להיות פולינומיאלית, אז מספר גדול יותר לא עוזר

 

[noam31]

הסבר פשוט יחסית על הצפנה בעזרת

עקומים אליפטים . http://world.std.com/~dpj/elliptic.html