שאלה אקראית מ-SQuAD:
מתי התגלה שמספרים ראשוניים יכולים להחיל על יצירת אלגוריתמי הצפנה של מפתח ציבורי?
תשובה:
שנות ה-70
משפטים שאוחזרו:
- עם זאת, החזון הזה נופץ ב- 1970, כאשר הוכרז בפומבי כי מספרים ראשוניים יכולים לשמש כבסיס ליצירת אלגוריתמי הצפנה במפתח ציבורי.
- פריטים משמשים במספר שגרות בטכנולוגיית מידע, כגון קריפטוגרפיה של מפתח ציבורי, שעושה שימוש במאפיינים כגון הקושי לכלול מספרים גדולים לגורמים העיקריים שלהם.
- אלגוריתמים יעילים הרבה יותר מחלוקת ניסוי הומצאו כדי לבדוק את הראשוניות של מספרים גדולים.
- מספר אלגוריתמים להצפנה עם מפתח ציבורי, כגון RSA וחילופי המפתחות של דיפי-הלמן, מבוססים על מספרים ראשוניים גדולים (לדוגמה, מספרים ראשוניים של 512 סיביות משמשים לעתים קרובות עבור RSA ומספרים ראשוניים של 1024 סיביות אופייניים לדיפי-הלמן). .
- מספרים ראשוניים משמשים גם עבור טבלאות גיבוב ומחוללי מספרים פסאודו אקראיים.
- חלק מהראשונים הללו נמצאו באמצעות מחשוב מבוזר.
- במשך זמן רב, תורת המספרים בכלל, וחקר המספרים הראשוניים בפרט, נתפסה כדוגמה הקנונית למתמטיקה טהורה, ללא יישומים מחוץ לאינטרס העצמי של לימוד הנושא, למעט השימוש במספרים ראשוניים שיני ציוד לפיזור השחיקה באופן שווה.
- אלגוריתמים דטרמיניסטיים מספקים דרך לדעת בוודאות אם מספר נתון הוא ראשוני או לא.
- הביטוי "כל האלגוריתמים האפשריים" כולל לא רק את האלגוריתמים המוכרים היום, אלא כל אלגוריתם שעשוי להתגלות בעתיד.
- לדוגמה, חלוקת ניסוי היא אלגוריתם דטרמיניסטי מכיוון שאם מבוצעת נכון, היא תמיד תזהה מספר ראשוני כראשוני ומספר מורכב כמרוכב.
- מנוסחת כבעיית החלטה, היא הבעיה של להחליט אם לקלט יש פקטור קטן מ-k. לא ידוע אלגוריתם יעיל לחלוקת מספרים שלמים, ועובדה זו מהווה בסיס למספר מערכות קריפטוגרפיות מודרניות, כגון אלגוריתם RSA.
- לפני שהחל המחקר בפועל שהוקדש במפורש למורכבותן של בעיות אלגוריתמיות, הונחו יסודות רבים על ידי חוקרים שונים.
- עיקרון מקומי-גלובלי זה מדגיש שוב את חשיבותם של ראשוניים לתורת המספרים.
- אלגוריתמים הסתברותיים הם בדרך כלל מהירים יותר, אך אינם מוכיחים לחלוטין שמספר הוא ראשוני.
- עם זאת, האלגוריתם הקוונטי הידוע ביותר לבעיה זו, האלגוריתם של שור, אכן פועל בזמן פולינומי.
- המסננת של ארוטוסטנס, המיוחסת לארטוסטנס, היא שיטה פשוטה לחישוב ראשוניים, למרות שהראשונים הגדולים המצויים כיום במחשבים אינם נוצרים כך.
- בעיה נחשבת כקשה מטבעה אם הפתרון שלה דורש משאבים משמעותיים, יהיה אשר יהיה האלגוריתם בו נעשה שימוש.
- אלגוריתמים שמשתמשים בסיביות אקראיות נקראים אלגוריתמים אקראיים.
- מאמינים שאם ניתן לפתור בעיה באמצעות אלגוריתם, קיימת מכונת טיורינג שפותרת את הבעיה.
- עם זאת, מספרי קרמייקל נדירים יותר ממספרים ראשוניים, כך שבדיקה זו יכולה להיות שימושית למטרות מעשיות.
- לדוגמה, רשימת הראשוניים של דריק נורמן להמר עד 10,006,721, שהודפסה מחדש עד מאוחר ב-1956, התחילה עם 1 כראשון הראשון שלה.
- התזה של קובהם אומרת שניתן לפתור בעיה עם כמות משאבים אפשרית אם היא מודה באלגוריתם זמן פולינומי.
- אוקלידס גם הראה כיצד לבנות מספר מושלם ממספר ראשוני של מרסן.
- נכון לינואר 2016[עדכון], למספר הראשוני הידוע הגדול ביותר יש 22,338,618 ספרות עשרוניות.
- שאלות כאלה דרבנו את התפתחותם של ענפים שונים של תורת המספרים, תוך התמקדות בהיבטים אנליטיים או אלגבריים של מספרים.