בתשובה לראובן, 02/08/06 13:09
 |
|
 |
||
|
||||
 |
אם N אינו ריבועי, אז [[צפיפות דיריכלה]] של קבוצת הראשוניים שעבורם N הוא [[שארית ריבועית]] היא חצי. אפשר להפוך את ההצהרה הזו לאלגוריתם הסתברותי, שיבדיל ריבועים משאינם ריבועים בזמן קבוע כפול logN, בסיכוי שיורד אקספוננציאלית עם הקבוע. אם יש לגישה הזו גירסה דטרמיניסטית, אני לא מאמין שהיא תהיה טובה יותר מהוצאת השורש, שצריכה להיות (בכל שיטה שהיא) בעלת סיבוכיות logN-בריבוע. |  |
 |
 |
|
|
|
||
|
||||
|
הראשוניים p כך ש-N איננו שארית ריבועית מודולו p מהווים "עדים" להיותו של N לא-ריבוע-שלם. אם N הוא כן ריבוע שלם, אין כאלה ראשוניים; אם הוא לא, יש הרבה כאלה ("בערך 50%" מכלל הראשוניים). | |
|
|
|
|
|
||
|
||||
|
אני הבנתי ששארית ריבועית היא פונקציה של שני דברים: מספר Mשמעלים אותו בריבוע, ומספר P שמחלקים בו את M^2 (בדרך כלל Pראשוני) הבנתי שאת הראשוני בוחרים אקראית (לפי התפלגות דיריכלה)מתוך הראשוניים, אבל לא הבנתי מיהו M. | |
|
|
|
|
|
||
|
||||
|
"N הוא שארית ריבועית מודולו p" אם יש מספר M כך ש-M^2 משאיר שארית N בחלוקה ל-p. בהינתן N ו-p, יש דרכים יעילות לבדוק אם N הוא כזה או לא (והן אינן כרוכות במציאת ה"שורש" M). אין לי טיפת זמן עכשיו אבל אשמח להרחיב אח"כ לגבי סימבול לז'נדר והדדיות ריבועית. | |
|
|
|
|
|
||
|
||||
|
אם הבנתי אותך, הרי שניסוח יותר ברור עבורי של המשפט הראשון בתגובה של עוזי הוא: אם N אינו ריבועי, אז [[צפיפות דיריכלה]] של קבוצת הראשוניים שעבורם N הוא [[שארית ריבועית]] עבור [[מחולק]] M *כלשהו* היא חצי. אני מוותר לך על ההרחבה, אבל *רק* בגלל שאתה כל כך עסוק :) |
|
|
|
|
|
|
||
|
||||
|
מה המשמעות של [[סוגריים מרובעים כפולים]]? | |
|
|
|
|
|
||
|
||||
|
"p הוא ראשוני שעבורו N הוא שארית ריבועית" = "N הוא שארית ריבועית מודולו p" = "קיים מספר x כך שהשארית של x^2 בחלוקה ל- p היא N". | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |