בתשובה להאייל האלמוני, 19/01/08 23:00
468623
טרחנות זו בטח לא, והגישה שלך דווקא סיקרנה אותי.
468746
הרעיון היה לנצל את העובדה שמספר בן A סיביות נמצא בטווח מספרים בן שתים בחזקת A סיביות. כלומר אם תהיה לי שאלה שאפשר לוודא את הנכונות שלה בזמן פולינומי(NP), אבל אין דרך למצא את הפתרון שלה (כמובן הכל בשלמים, או לכל הפחות בקבוצה לא צפופה, אם כי גם כאן בטח יש הסתייגויות שאני לא מכיר), אני אוכל באמצעות הקלט להגדיר טווח מספרים גדול מספיק כדי שזמן מציאת הפתרון יהיה אקספוננציאלי(לא בP). הידע שלי במתמטיקה הוא סימלי לכל היותר, לכן לא היו לי יותר מדי בעיות לבחור מהן. עבור משוואות דיופונטיות ידעתי שיש משוואות שלא ידוע האם יש להן פתרון. אם היתה הוכחה שחיפוש הפתרון באמת מצריך מעבר כל כל המספרים בטווח, יכול להיות שההוכחה היתה עובדת. לרגע גם טעיתי לחשוב שאם החיפוש (של הפתרון) הוא ביעילות כל שהיא (שכמובן חייבת להיות תלויה בn, המספר המקסימלי בטווח שמחפשים בו), אני אוכל לבנות פונקציה שתרחיב את הטווח כך שזמן החיפוש עדיין יהיה אקספוננציאלי. אני באמת יכול לעשות את זה, אבל אז הפתרון גדל כל כך שאני כבר לא יכול לוודא את נכונותו בזמן פולינומי בA.
468748
הגישה שלך בכלל לא מופרכת. בפרט, היא פחות או יותר הבסיס לקריפטוגרפיה המודרנית; למשל, בעיית הפירוק לגורמים, שהיא ‏1 מה שעומד מאחורי RSA סובלת מקושי שכזה. הרעיון הוא שאפשר לייצג די בקלות מספרים גדולים, בני מאות ספרות (כי צריך רק מאות ביטים בשביל זה), וגם די קל לעבוד איתם - חיבור וכפל, למשל, הם פולינומיים במספר הביטים, וגם העלאה בחזקה מודולו משהו היא פולינומית במספר הביטים אם משתמשים באלגוריתם פשוט אך לא נאיבי; אבל פירוק לגורמים נאיבי דורש בדיקה של כל המספרים הקטנים ממה שרוצים לפרק ‏2 וכאלו יש במספר שהוא אקספוננציאלי במספר הספרות. כמובן, כבר ידועים אלגוריתמיים יותר מתוחכמים לפירוק לגורמים, אבל גם הם עדיין אקספוננציאליים, אם אין לך מחשב קוואנטי פועל בהישג יד.

------------
1 לא בדיוק; אם פותרים פירוק לגורמים הלך על RSA, אבל אולי אפשר לחסל את RSA בלי לפתור את בעיית הפירוק לגורמים.

2 טוב, "עד השורש" הידוע.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים