פורסם: 28/10/2004 - 21:06
נושא ההודעה: מציאת אלגוריתם למספרים ראשוניים
|
כעת קראתי באתר על אלגוריתם למציאת מספרים
ועלתה בראשי שאלה האם יש אתר כלשהו למציאת אלגוריתמים
ואם אין זה יכול להיות אתר מדהים.
וכעת בחזרה לנושא ההאם מישהו מכיר אלגוריתם טוב למציאת מספרים ראשוניים?
בתודה מראש
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 21:12
נושא ההודעה:
|
אני עכשיו כותב את זה אז נא לשפר 
התכנית- עוברת מספר מספר
- בודקת כמה ספרות יש
- לפי מספר הספרות עושים Mod ובודקים אם המספר חלקי 1000 או 100 וכו..
במידה והספר שווה 2 4 6 8 0 5 9 אז עוברים למספר הבא
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 21:32
נושא ההודעה:
|
|
מישהו פה מעשן קראק ?
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 21:40
נושא ההודעה: Re: מציאת אלגוריתם למספרים ראשוניים
|
הדרך הכי טובה ( שאני מכיר ) היא... למצוא שורש ריבוע למספר.. במידה ואין שורש שלם
למצוא את הכי קרוב ולהוסיף לו אחד.. ועכשיו תחלק את המספר שאתה רוצה לבדוק אם הוא ראשוני מ-1 עד לשורש הריבועי שלו.
אם אף אחת מהתוצאות לא נותנת לך מספר שלם אז המספר ראשוני, אם נותנת אז המספר לא ראשוני.
אם מישהו מכיר דרך יותר יעילה, בבקשה תגידו 
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 22:35
נושא ההודעה:
|
|
רק שלהוציא שורש היא פעולה מורכבת. אתה יכול להתחיל לעשות אותה ממספר 100000 ואז זה יתחיל להשתלם לך.
למספרים קטנים, עדיף לשים את המספרים המחסנית ולהתחיל לבדוק חלוקה בכל אחד מהם.
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 22:54
נושא ההודעה:
|
| elcuco : | רק שלהוציא שורש היא פעולה מורכבת. אתה יכול להתחיל לעשות אותה ממספר 100000 ואז זה יתחיל להשתלם לך.
למספרים קטנים, עדיף לשים את המספרים המחסנית ולהתחיל לבדוק חלוקה בכל אחד מהם. |
המחבר לא כתב על איזה סדרי גודל מדובר, ואני מתייחס למקרה הכי גרוע.
כאשר ה- n שווה למספר מאוד גדול.
( השפעות של יעילות בכיתה יב  )
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 23:11
נושא ההודעה:
|
תאמין לי זה כלום לעומת יעילות ב"מבנה נתונים"...
אם אתה תשתשמש באלגוריטם הזה, אתה לא תגיע למספרים הגבוהים בקלות...
מוזר איך לא חשבתי על הרעיון שלך, הארי אני מכיר אותו...
צריך לחשב גם את הערך הקריטי שבו עדיף להחליף אלגוריטמים (בדיקת מספרים במחסנית מול בדיקת שורשים).
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 23:30
נושא ההודעה:
|
|
הדרך הכי יעילה למצוא את כל המספרים הראשוניים עד ל- n היא ללא ספק:
1. להכניס למערך את הערך 2.
2. לעבור על כל המספרים מ- 3 על ל- n
3. עבור כל מספר האם מתחלק במספרים שבמערך ללא שארית. אם כן לעבור למספר הבא. אם לא להכניס את המספר לתא הבא במערך.
4. כשמגיעים ל- n להדפיס את כל המספרים במערך.
הגודל של המערך הוא בערך עשירית מ- n אבל זה בטוח יותר יעיל מאשר לבדוק את כל המספרים עד לשורש n.
אבל אם רוצים לבדוק האם מספר מסוים הוא ראשוני אין ברירה אלא לבדוק את כל המספרים עד לשורש הריבועי + 1 שלו.
אסף.
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 23:36
נושא ההודעה:
|
|
אם עושים סריקה מ0 עד x אז אפשר להתחיל מ2 ולבדוק אם הוא מתחלק באחד מהמספרים שסומנו קודם לכן כראשוניים, ולסמן אותו כראשוני אם לא (בשביל 2 לא יהיו ממתחלק מספרים כאלו, ולפיכך הוא יהיה ראשוני, אז התוכנה תבדוק אם 3 מתחלק ב2 ותוסיף אותו לרשימה בגלל שהוא לא. לאחר מכן התוכנה תדלג על 4 בגלל שהוא מתחלק ב2 (שכבר נמצא ברשימה) וכו')
|
|
|
| חזרה לתוכן הדיון |
פורסם: 28/10/2004 - 23:43
נושא ההודעה:
|
|
אגב, כדי למזער את הנזק, אל תשכח שאתה צריך לבדוק רק לכל המספרים האי זוגיים ו-2.
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 00:10
נושא ההודעה:
|
|
אכן אפשר להתחיל מ- 2 ולבדוק גם אותו מול המערך הריק אם כי מיותר לדעתי ועלול לגרום בעיות בכתיבה (למשל לבדוק 0 מספרים במערך וכו').
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 00:15
נושא ההודעה:
|
|
אם מדובר בתוכנה לשימוש חוזר שסורקת את כל המספרים כמו שתואר קודם כדאי גם לשמור מספרים שכבר מופו בקובץ כדי להאיץ את החיפוש בשימוש חוזר ולהתחיל מאיפה שהפסקת.
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 00:28
נושא ההודעה:
|
|
לגבי בדיקה עד השורש, הרי שלא צריך להוציא את השורש של המספר על-מנת לבצע את הבדיקה הזו. מספיק לבדוק האם קיימת חלוקה, עד אשר תוצאת החלוקה קטנה מהמחלק.
למשל, עבור המספר 17, מספיק לבדוק עד הערך 5, שכן 17 לחלק בארבע, עדיין גדול מ - 4, ואילו 17 לחלק בחמש כבר קטן מחמש. זה כמובן נובע מכך ששורש ריבועי הוא המספר שאם תחלק בו, התוצאה תהיה שווה לו.
דרך יעילה יותר לבדוק את זה, היא כמובן לחלק רק במספרים ראשוניים הקטנים או שווים לשורש המספר, ולא בכל מספר ומספר עד השורש. הבעיה היא, איך אנחנו יודעים מהם אותם מספרים. למציאת כל המספרים הראשוניים עד N, ניתן להשתמש בשיטה הזו, עם מערך. לא ברור לי אם מה שתואר מעלי זאת הכוונה, אבל באופן עקרוני, שמים בתא הראשון את הערך 2. מתחילים למלא את שאר התאים באופן הבא: כל מספר מ - 3 עד N נבדק. עבור כל מספר כזה n, מחלקים אותו בכל הערכים במערך מהתא הראשון ומעלה, עד אשר התוצאה קטנה מהמחלק. אם באיזשהו שלב החלוקה היא שלמה, אין טעם להמשיך לחלק, המספר אינו ראשוני, וניתן להמשיך למספר הבא (n + 1). אם לא היתה קיימת חלוקה כזו, המספר ראשוני, מציבים אותו בתא הריק הבא במערך ועוברים שני מספרים קדימה (n + 2).
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 01:47
נושא ההודעה:
|
הכל תלוי בעניין שלך במספרים ראשוניים.
לדוגמא, אם אתה רוצה ליצור מפתח RSA (למטרת PGP, SSL), אז תרצה לחפש 2 מספרים ראשוניים גדולים מאוד. במקרה כזה, הפתרונות שנכתבו פה לא יתנו פתרון יעיל.
פתרון יעיל יחסית לבעיה כזו הוא שימוש באלגוריתם הסתברותי עם טעות חד-צדדית. למי שלא מכיר, אני אתן הסבר קצרצר: לאלגוריתם הסתברותי 2 תשובות: כן ולא. אם המספר הוא ראשוני, אז האלגוריתם יענה "כן" בכל מקרה, אבל אם המספר פריק, אז הוא יכול להגיד כן או לא (כלומר, לטעות).
כלומר, לאחר הרצת האלגוריתם על המספר, אם הוא פריק, יש סיכוי טוב שנגלה את זה, ואז נזרוק את המספר לפח. אם לא גילינו, יש סיכוי טוב שהוא מספר ראשוני, ונבדוק את זה ע"י שיטה סטנדרטית - חלוקה בכל המספרים על לשורש.
אולי יותר בלבלתי מאשר עזרתי...
מילמן.
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 09:31
נושא ההודעה:
|
מילמן: גם עזרת וגם בילבלת.
א. נכון שלבדיקת ראשוניות של מספרים גדולים (למפתחות RSA מדובר על סדר גודל של לפחות 128 ביט, כלומר, מספר קצת יותר גדול מ-12^1000), האלגוריתמים שהוזכרו לעיל הם לא יעילים, ויש אלגוריתמים הסתברותיים יעילים.
ב. ההסבר שלך על אלגוריתמים הסתברותיים לא לגמרי ממצה; חשוב להוסיף שבאלגוריתם הסתברותי, כאשר מדובר בשגיאה, הרצות שונות על אותו קלט יכולות להחזיר תוצאות שונות (אני לא רוצה להיכנס בפורום להסבר טכני מדי, אבל אחרת אפשר להציע אלגוריתמים מופרכים לגמרי).
ג. הרעיון לבדוק את התוצאה ע"י חלוקה עד השורש הוא מופרך לחלוטין למספרים גדולים. לדוגמה, על מספר גדול צנוע של 128 ביט, השורש יהיה באזור 6^1000. המחשב הכי חזק בעולם, מהשבוע האחרון, עושה 4^1000*42.7 פעולות בשניה, מה שאומר שייקח לו כמה עשרות-אלפי שניות (סדר גודל של יום) לעבור על כל המספרים עד השורש. תגדיל את הראשוני שאתה בודק ל-256 ביט, והשמש תכבה לפני שהחישוב יסתיים.
ד. הרעיון לעבור על כל המספרים, לנפות מהם את הפריקים, ולבדוק כל מספר חדש רק על הראשוניים שמצאנו כבר, נקרא "נפת ארתוסטנס", על שם היווני העתיק שהמציא אותו.
ה. לפני כמה שנים הוצג אלגוריתם דטרמיניסטי (לא הסתברותי) לבדיקת ראשוניות בזמן פולינומי (כלומר, באופן יעיל). המעוניינים בפרטים הטכניים מופנים ל- http://www.cse.iitk.ac.in/news/primality.html (אין לזה השפעה על הצפנות, בגלל שבדיקת ראשוניות עוד לא נותנת פירוק לראשוניים, ובגלל שבדיקת ראשוניות יעילה -- אם כי הסתברותית -- היתה קיימת עוד קודם).
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 10:56
נושא ההודעה:
|
אתה יכול לנסות ע"י מבחן פרמה: בוחרים 100 מספרים רנדומיים שקטנים מהמספר שברצונך לבדוק. נניח n הוא המספר שברצונך לבדוק, ו a הוא המספר הרנדומי שלך. עלייך לבדוק האם:
מספר ראשוני אמור לקיים זאת עבור כל a. אחרי מאה נסיונות, הסיכוי לשגיאה הוא פחות מהסיכוי שברק יפגע לך במחשב תוך כדי הריצה, פרט למספרים מיוחדים שנקראים מספרי קארמייקל, שמתחזים לראשוניים במבחן פרמה, אבל השכיחות שלהם קטנה מאוד.
אם תייעל את ההעלאה בחזקה ע"י אלגוריתם שיעלה בריבוע ויחלק את המעריך ב 2, ובכל צעד תבצע את המודולו, תקבל זמן ריצה לא רע.
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 11:39
נושא ההודעה:
|
_________________ Sure linux is user-friendly, it's just picky about who its friends are
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 14:28
נושא ההודעה:
|
תודה רבה על הקישור מאוד נהניתי לקרוא אותו
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 14:36
נושא ההודעה:
|
הנה טיפ או התחלה למישהו שרוצה אלגוריתם לזה
!) מספר ראשוני מעל עשר אינו יכול להסתיים בספרה זוגית מאחר וכל מספר זוגי מתחלק בשתיים
!) " " " " " " " " 5 ו0 מאחר וכל מספר כזה מתחלק ב5
הנה חסכתי לאלגוריתם 60 אחוז מהזמן
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 14:44
נושא ההודעה:
|
|
אם נרחיב את זה, כל מספר ראשוני שהוא לא 2, הוא לא זוגי (אגב, מסתיים בסיפרה זוגית משמעו זוגי).
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 15:11
נושא ההודעה:
|
|
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 20:23
נושא ההודעה:
|
| DudeShemesh : | אתה יכול לנסות ע"י מבחן פרמה: בוחרים 100 מספרים רנדומיים שקטנים מהמספר שברצונך לבדוק. נניח n הוא המספר שברצונך לבדוק, ו a הוא המספר הרנדומי שלך. עלייך לבדוק האם:
מספר ראשוני אמור לקיים זאת עבור כל a. אחרי מאה נסיונות, הסיכוי לשגיאה הוא פחות מהסיכוי שברק יפגע לך במחשב תוך כדי הריצה, פרט למספרים מיוחדים שנקראים מספרי קארמייקל, שמתחזים לראשוניים במבחן פרמה, אבל השכיחות שלהם קטנה מאוד.
אם תייעל את ההעלאה בחזקה ע"י אלגוריתם שיעלה בריבוע ויחלק את המעריך ב 2, ובכל צעד תבצע את המודולו, תקבל זמן ריצה לא רע. |
זה שטויות האלגוריתם אינו נכון עבור כל n>2 וa=1
n>2 כמעט תמיד מתקיים והסיכוי שיוגרל 1 לא כזה נמוך
1 בחזקת n שווה 1
והשארית חלוקה של 1 ב.n היא 1.
|
|
|
| חזרה לתוכן הדיון |
פורסם: 29/10/2004 - 21:52
נושא ההודעה:
|
| nolim : | | DudeShemesh : | אתה יכול לנסות ע"י מבחן פרמה: בוחרים 100 מספרים רנדומיים שקטנים מהמספר שברצונך לבדוק. נניח n הוא המספר שברצונך לבדוק, ו a הוא המספר הרנדומי שלך. עלייך לבדוק האם:
מספר ראשוני אמור לקיים זאת עבור כל a. אחרי מאה נסיונות, הסיכוי לשגיאה הוא פחות מהסיכוי שברק יפגע לך במחשב תוך כדי הריצה, פרט למספרים מיוחדים שנקראים מספרי קארמייקל, שמתחזים לראשוניים במבחן פרמה, אבל השכיחות שלהם קטנה מאוד.
אם תייעל את ההעלאה בחזקה ע"י אלגוריתם שיעלה בריבוע ויחלק את המעריך ב 2, ובכל צעד תבצע את המודולו, תקבל זמן ריצה לא רע. |
זה שטויות האלגוריתם אינו נכון עבור כל n>2 וa=1
n>2 כמעט תמיד מתקיים והסיכוי שיוגרל 1 לא כזה נמוך
1 בחזקת n שווה 1
והשארית חלוקה של 1 ב.n היא 1. |
בגלל זה בודקים 100 מספרים ולא רק אחד. נא לקרוא לפני שמגיבים. בכל זאת, האלגוריתם הזה עובד כבר מאות שנים.
|
|
|
| חזרה לתוכן הדיון |
פורסם: 30/10/2004 - 02:04
נושא ההודעה:
|
|
אההה אתה עושה השוואה בשדה מודולו n ואז זה תמיד יוצא נכון
השדה מודולו n כאשר n ראשוני תמיד מקיים את התנאי ועבור מספרים פריקים זה בכלל לא שדה... לכן לרוב לא מתקיים.
(מתוך אלגברה לינארית)
|
|
|
| חזרה לתוכן הדיון |
פורסם: 30/10/2004 - 02:22
נושא ההודעה:
|
למספרים ראשונייםיש חשיבות לא מעטה בקריפטולוגיה. לדוגמה, בשביל ליצור מפתח RSA, יוצר המפתח צריך "לחשוב על" מספר ראשוני גדול מאוד.
לכן בתשובה ישירה לשאלה המקורית: הבעיה ידועה, מוכרת, ובוודאי תמצא לפחות מימוש אחד שלה על מחשבך, ותוכל למצוא בקלות יחסית את קוד המקור שלו.
ובקשר לשאלה השניה שלך: http://primes.utm.edu/curios/page.php?rank=1832 , למרות שהם "מרמים" .
|
|
|
| חזרה לתוכן הדיון |
פורסם: 30/10/2004 - 10:52
נושא ההודעה:
|
| nolim : | אההה אתה עושה השוואה בשדה מודולו n ואז זה תמיד יוצא נכון
השדה מודולו n כאשר n ראשוני תמיד מקיים את התנאי ועבור מספרים פריקים זה בכלל לא שדה... לכן לרוב לא מתקיים.
(מתוך אלגברה לינארית) |
לא כל כך הבנתי אם עכשיו אתה מסכים איתי או לא, בכל מקרה, הנה הפרשנות שלי:
כמו שאמרת, Zp הוא שדה כאשר p ראשוני. במקרה כזה, לפי משפט פרמה הקטן, עבור כל a מהשדה a^(p-1) = 1. נכפיל ב a את שני האגפים ונקבל a^p = a. מכיוון שאנחנו עובדים ב Zp הרי שכל הפעולות הן מודולו p.
בחזרה לאלגוריתם, אם n ראשוני, הרי שזה אמור להתקיים עבור כל a שקטן ממנו, כי הוא שייך לשדה, לכן לא יתכן ש"נפספס" מספר ראשוני. מצד שני, יש מספרים מיוחדים (קראמייקל), שמתחזים לראשונים בבדיקה הזאת, אבל הם לא שכיחים במיוחד. בבדיקה של מספר שאינו מתחזה, ייתכן מאוד שהבדיקה תצליח עבור a-ים מסויימים, אבל לאחר 100 a-ים, הסיכוי לשגיאה קטן מאוד (משהו כמו שתיים בחזקת מינוס מאה אם אני זוכר נכון).
|
|
|
| חזרה לתוכן הדיון |
פורסם: 30/10/2004 - 12:01
נושא ההודעה:
|
| DudeShemesh : | | nolim : | אההה אתה עושה השוואה בשדה מודולו n ואז זה תמיד יוצא נכון
השדה מודולו n כאשר n ראשוני תמיד מקיים את התנאי ועבור מספרים פריקים זה בכלל לא שדה... לכן לרוב לא מתקיים.
(מתוך אלגברה לינארית) |
לא כל כך הבנתי אם עכשיו אתה מסכים איתי או לא, בכל מקרה, הנה הפרשנות שלי:
כמו שאמרת, Zp הוא שדה כאשר p ראשוני. במקרה כזה, לפי משפט פרמה הקטן, עבור כל a מהשדה a^(p-1) = 1. נכפיל ב a את שני האגפים ונקבל a^p = a. מכיוון שאנחנו עובדים ב Zp הרי שכל הפעולות הן מודולו p.
בחזרה לאלגוריתם, אם n ראשוני, הרי שזה אמור להתקיים עבור כל a שקטן ממנו, כי הוא שייך לשדה, לכן לא יתכן ש"נפספס" מספר ראשוני. מצד שני, יש מספרים מיוחדים (קראמייקל), שמתחזים לראשונים בבדיקה הזאת, אבל הם לא שכיחים במיוחד. בבדיקה של מספר שאינו מתחזה, ייתכן מאוד שהבדיקה תצליח עבור a-ים מסויימים, אבל לאחר 100 a-ים, הסיכוי לשגיאה קטן מאוד (משהו כמו שתיים בחזקת מינוס מאה אם אני זוכר נכון). |
הבנתי אותך...פשוט הסתבכתי עם הניסוח
|
|
|
| חזרה לתוכן הדיון |
פורסם: 30/10/2004 - 12:04
נושא ההודעה:
|
| DudeShemesh : | | nolim : | אההה אתה עושה השוואה בשדה מודולו n ואז זה תמיד יוצא נכון
השדה מודולו n כאשר n ראשוני תמיד מקיים את התנאי ועבור מספרים פריקים זה בכלל לא שדה... לכן לרוב לא מתקיים.
(מתוך אלגברה לינארית) |
לא כל כך הבנתי אם עכשיו אתה מסכים איתי או לא, בכל מקרה, הנה הפרשנות שלי:
כמו שאמרת, Zp הוא שדה כאשר p ראשוני. במקרה כזה, לפי משפט פרמה הקטן, עבור כל a מהשדה a^(p-1) = 1. נכפיל ב a את שני האגפים ונקבל a^p = a. מכיוון שאנחנו עובדים ב Zp הרי שכל הפעולות הן מודולו p.
בחזרה לאלגוריתם, אם n ראשוני, הרי שזה אמור להתקיים עבור כל a שקטן ממנו, כי הוא שייך לשדה, לכן לא יתכן ש"נפספס" מספר ראשוני. מצד שני, יש מספרים מיוחדים (קראמייקל), שמתחזים לראשונים בבדיקה הזאת, אבל הם לא שכיחים במיוחד. בבדיקה של מספר שאינו מתחזה, ייתכן מאוד שהבדיקה תצליח עבור a-ים מסויימים, אבל לאחר 100 a-ים, הסיכוי לשגיאה קטן מאוד (משהו כמו שתיים בחזקת מינוס מאה אם אני זוכר נכון). |
הבנתי אותך...פשוט הסתבכתי עם הניסוח
|
|
|
| חזרה לתוכן הדיון |
פורסם: 30/10/2004 - 18:27
נושא ההודעה:
|
| צפריר : | למספרים ראשונייםיש חשיבות לא מעטה בקריפטולוגיה. לדוגמה, בשביל ליצור מפתח RSA, יוצר המפתח צריך "לחשוב על" מספר ראשוני גדול מאוד.
לכן בתשובה ישירה לשאלה המקורית: הבעיה ידועה, מוכרת, ובוודאי תמצא לפחות מימוש אחד שלה על מחשבך, ותוכל למצוא בקלות יחסית את קוד המקור שלו.
ובקשר לשאלה השניה שלך: http://primes.utm.edu/curios/page.php?rank=1832 , למרות שהם "מרמים" . |
thank you for the link
במה הם מרמים?
|
|
|
| חזרה לתוכן הדיון |
פורסם: 30/10/2004 - 18:34
נושא ההודעה:
|
|
אגב, החבילה bsdgames כוללת תוכנית בשם primes .
|
|
|
| חזרה לתוכן הדיון |
|
|
ת.הצטרפות: 04/05/2003
·
הודעות: 1399
·
