תורת המספרים

[student47]

תורת המספרים

כמה שאלות:

1. איך בודקים האם מספר הוא ראשוני?
2. בהינתן מספר פריק, כיצד ניתן לפרק אותו לגורמים?
3. מדוע אין מספרים שלמים בין 0 ל-1?

לגבי שאלה 3, המרצה כתב בקצרה:

אם היה מספר שלם a בין 0 ל-1, אז N לא מסודר היטב (כלומר קיימת תת קבוצה של N שאין בה איבר מנימלי).
למה? לא ברור לי איך מכך שיש מספר שלם בין 0 ל-1, אפשר להסיק שקיימת תת קבוצה של N שאין בה איבר מינימלי. מי זו התת קבוצה הזו?

תודה מראש.

 

[עעעערררר]

רמז: הטבעיים סגורים לכפל.

 

[פאח9]

1. ו-2. הם די קשים אנסה בכל זאת לענות ל-1.

משפט: יהי מספר a
" "a=b+c כאשר b ו-c שלמים ו-b,c=\0 כאשר \= אומר לא-שווה" גורר b זר ל-c" אז "a ראשוני"
הוכחה : נניח בשלילה ש-a פריק כלומר " "a=b+c כאשר b ו-c שלמים ו-b,c=\0 כאשר \= אומר לא-שווה" גורר b זר ל-c" וקימים d ו-e שלמים שלא שווים ל-1 כך ש-d*e=a מזה נובע
d*(e-1)+d=d*e=a
שזה סתירה

 

[1ca1]

תשובות

אם אני אגלה לך את 1 ו-2 אני אצטרך להרוג אותך

.
סתם, בקיצור אלו בעיות לא פתירות, תחפש קצת בויקי על משהו שנקרא מילר רבין והצפנת RSA.
ספציפית לשאלה 1 יש תשובה טובה, שנקראת אלגוריתם AKS, והיא נתגלתה רק לפני כ-15 שנה, אבל די מפתיע שהיא לא עוזרת לשאלה 2, כלומר אני אגיד לך שמספר איננו ראשוני אבל לא אצליח לפרק אותו.
&nbsp
לגבי 3, הכיוון שהציע ערר הוא די מוזר, בהתחשב בעובדה שלא צריך לדון כאן על השלמים אלא רק על הטבעיים.
הטבעיים מוגדרים דרך מערכת אקסיומות שנקראת מערכת אקסיומות פיאנו. שם יש פעולה של "עוקב", ו-1 מוגדר להיות העוקב של אפס (יש כאלו שלא מגדירים את האפס בטבעיים), או להיפך, זה פשוט נובע מהבנייה של N דרך תורת הקבוצות.
בקיצור, זה מיידי מהבנייה של N.

 

[אורי769]

הערה

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

 

[student47]

אורי

אם אני רוצה לבדוק שמספר k הוא ראשוני, אני יכול פשוט לבדוק שכל מספר בין 2 ל-k/2 לא מחלק את k?
למה הסיבוכיות כאן היא לא לינארית? זו לולאה שרצה מ-2 עד k-2...אני מדבר שטויות?

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


ותודה על התשובות.

 

[אורי769]

אתה לא מדבר שטויות

המושג סיבוכיות מתייחס ליחס שבין זמן הריצה לגודל הקלט. אלה שני מושגים שכביכול מאד ברור מה משמעותם. אבל אם חושבים על זה עוד כמה שניות, אז מתברר שהם בכלל לא ברורים. בהקשר של זמן ריצה, נשאלת השאלה, איזו פעולה נחשבת ל"אטומית" כלומר שלוקחת יחידת זמן אחת, או מספר חסום של יחידות זמן. לדוגמא, השוואה בין שני מספרים - האם זו פעולה אטומית או האם היא תלויה בגודל המספרים?
בהקשר של גודל הקלט, שזה בעצם הנקודה כאן, כאשר הקלט שלך הוא מספר בודד, מה הוא גודל הקלט? התשובה היא שגודל הקלט היא מספר הספרות בייצוג של המספר (לדוגמא בייצוג בינארי). אם k=1000, אז צריך 10 ספרות בינאריות. אם k=1,000,000 אז צריך 20 ספרות בינאריות. בקיצור, כדי לייצג את k צריך (log2(k ספרות. כלומר אם n הוא אורך הקלט אז (n=log2(k. לכן אם רצים מ-2 עד k/2 זה ייקח T=2^n איטרציות. כלומר סיבוכיות מעריכית.

אגב, מספיק לרוץ מ-2 עד k√.

אלגוריתם נאיבי לפירוק יכול לעבוד על אותו העיקרון באופן רקורסיבי. תריץ t מ-2 עד k√. אם t מחלק את k אז תריץ באופן רקורסיבי את האלגוריתם לפירוק של t. אם לא מצאת מחלק סימן ש-k הוא ראשוני - כלומר הפירוק שלו כולל את עצמו בלבד.