שיחה:נפה ריבועית

בשורה הראשונה: איזה Dixon? האם זה D.E.Dixon? עוזי ו. 21:20, 9 בינואר 2007 (IST)

אחרי נבירה בארכיונים שלי, אין לי מושג. זה לקוח מתוך המסמך הזה. שם מוזכר רק שם המשפחה. הציטוט המלא הוא:

The Quadratic Sieve, hereafter simply called the QS, was invented by Carl Pomerance in 1981, extending earlier ideas of Kraitchik and Dixon.

אני חוזר לישון. גדי ו. (שיחה) 03:04, 10 בינואר 2007 (IST)

לפי en:Dixon's factorization method, מדובר בקנדי ג'ון ד' דיקסון. ‏odedee • שיחה 04:01, 10 בינואר 2007 (IST)

כמה הערות

א. זה לא מדויק לומר "כל השיטות האחרות לפירוק של מספרים שלמים (למעט החיפוש הנאיבי אחרי גורמים קטנים)" דומות ל-QS. כלומר מציאת הזוג x,y שריבועיהם שקולים (וניפוי של יחסים). אפשר להגדיר זאת כמו שמקובל: הנפה הריבועית נמנית על משפחת אלגורתמים לפירוק לגורמים הנקראת "ריבוע אקראי" (בלעז Random square). במשפחה זו כמובן נמצא גם NFS ועוד כמה אלגוריתמים טובים. דוגמאות לאלגורתמים שאינם נמנים על משפחה זו אפשר לציין את האלגוריתמים של פולרד וכן שיטת העקום האליפטי של לנסטרה. ב. צריך לדייק בניסוח המשימה של האלגוריתם. האלגוריתם אמור למצוא זוג ערכים x ו-y אשר "אינם" שקולים זה לזה (גם לא הנגדיים שלהם) מודולו n ולעומת זאת ריבועיהם שקולים זה לזה. אפשר גם להוסיף שהעיקרון מבוסס על פרמה. הוא הציג את מה שנקרא difference of squares (לא יודע איך לתרגם את זה, אולי "הפרש ריבועים"). הרעיון שלו מבוסס על $\ a^{2}-b^{2}=(a-b)(a+b)$. אם יש לנו x ו-y כלשהם המקיימים $\ x^{2}\equiv y^{2}$ אזי $\ {\mbox{gcd}}(x\pm y,n)$ הוא גורם של n (בסבירות גבוהה כ-2/3). הרעיון הוא שאפשר לנצל את הפרש הריבועים כדי לפרק את n לגורמים למשל על ידי חיפוש מספר ריבועי הקרוב ביותר ל-n ואז לבדוק האם ההפרש הנו מספר ריבועי, אם כן אפשר לנצל את הטריק של פרמה לפירוק הפרש הריבועים כדי לפרק את n. מפה העסק התפתח במרוצת השנים תחילה על ידי דיקסון ואחריו פומרנץ שהוסיף את הניפוי וכו'. ג. אולי כדאי בנוסף להסבר התיאורתי לתת פירוט של האלגוריתם צעד אחר צעד כנהוג בדרך כלל. --יוסי א. 20:08, 17 בפברואר 2007 (IST)

א. האלגוריתמים של פולארד (rho ו- lambda) בהחלט מבוססים על מציאת שני מספרים בעלי אותו ריבוע; וגם האלגוריתם של Lenstra עושה אותו דבר, בעזרת הפולינום שבמכנה של נוסחת החיבור של נקודות על עקום אליפטי. ב. הסיכוי להתנגשות מועילה הוא 1/2 ולא 2/3. עוזי ו. 17:38, 19 בפברואר 2007 (IST)

למה רק הגדרות מילוניות?

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

אבל מהו x?

בפסקת "סיבוכיות" השאלה הזו נשאלת, אבל לא מצאתי לה תשובה. אז מהו x? -- רועי.ס - שיחה 22:10, 22 בספטמבר 2014 (IDT)

X הוא הגודל בפועל של מספרים שמשליכים לתוך הנפה, כלומר בערך שורש n. את המשפט המתחיל ב"פומרנץ הראה" לא הבנתי, בגלל חילופי הפונטים; האם x=X שם? עוזי ו. - שיחה 23:59, 22 בספטמבר 2014 (IDT)