הצגת המקור של הדף "נפת שדה מספרים"

ב[[תורת המספרים]], '''נפת שדה המספרים''' הוא [[אלגוריתם]] ל[[פירוק לגורמים של מספר שלם|פירוק]] [[מספרים גדולים]] לגורמיהם ה[[מספר ראשוני|ראשוניים]]. אלגוריתם זה הוא האלגוריתם הקלאסי ה[[סיבוכיות מקום|יעיל]] וה[[סיבוכיות זמן|מהיר]] ביותר הידוע כיום לפירוק מספרים גדולים מאוד (בני כ-110 ספרות עשרוניות או יותר).

בדומה לשיטת [[נפה ריבועית|הנפה הריבועית]], שהייתה השיטה הטובה ביותר לפירוק עד תחילת [[שנות ה-90 של המאה ה-20]], גם נפת שדה המספרים מבוססת על [[תחשיב אינדקסים|תחשיב]] [[אינדקס (מתמטיקה)|אינדקסים]] ביחס לבסיס קבוע. במקום לבסס את חיפוש הגורמים על בסיס של [[מספר ראשוני|ראשוניים רציונליים]], כמו בנפה הריבועית, נפת שדה המספרים מבוססת על בסיס של [[אידיאל ראשוני|אידיאלים ראשוניים]] ב[[חוג המספרים השלמים|חוג שלמים]] של [[שדה מספרים]] מתאים. באלגוריתם ישנם פרמטרים רבים שאינם ברורים די הצורך, והוא מצוי בתהליך מתמשך של שיפור והרחבה.

==סיבוכיות==
עם הופעתן של מערכת ה[[הצפנה]] ה[[מפתח ציבורי|א-סימטרית]] [[RSA]], המבוססת על הקושי שבפירוק מספרים גדולים לגורמים, עלה קרנה של בעיה זו ב[[תורת המספרים]] היישומית. בבעיית פירוק מספר נתון <math>n</math>, גודל הקלט מורכב ממספר הספרות הבינאריות ומסומן <math>\log(n)</math>. סיבוכיות פולינומית היא מהצורה <math>\log(n)^c</math> עבור קבוע <math>c>0</math> כלשהו. לעומת זאת סיבוכיות מעריכית היא מהצורה <math>n^c=2^{c\log(n)}</math>; אלגוריתם בעל סיבוכיות כזו נחשב בדרך כלל לגרוע במיוחד. לא ידוע כיום על אלגוריתם בעל סיבוכיות פולינומית לבעיית הפירוק והעוסקים בתחום מעריכים שאלגוריתם כזה כלל אינו קיים. למעשה, עד להמצאתה של הנפה הריבועית, כל האלגוריתמים לבעיית הפירוק היו מעריכיים.

סיבוכיות פירוק <math>n</math> לגורמים באמצעות שיטת הנפה הריבועית מוערכת ב-<math>L_n[1/2,c]</math>, כאשר <math>L_n[\alpha,c]=2^{c\log(n)^{\alpha}\log(\log(n))^{1-\alpha}}</math> היא פונקציית הסיבוכיות המתאימה לאלגוריתמים מסוג זה. <math>\alpha</math> הוא משקל החלק הלוגריתמי במעריך, בעוד שהמשלים ל-<math>\alpha</math> הוא משקל החלק הלוג-לוגריתמי, הקטן יותר. לכל ערך של <math>\alpha</math>, הפונקציה מייצגת סיבוכיות גדולה יותר ככל ש-<math>c</math> גדול יותר. לשם השוואה, <math>L_n[1,c]=n^c</math> היא סיבוכיות מעריכית, בעוד ש-<math>L_n[0,c]=\log(n)^c</math> היא סיבוכיות פולינומית. על סולם זה, הסיבוכיות של הנפה הריבועית נמצאת ב"אמצע הדרך" בין סיבוכיות מעריכית לפולינומית, והיא כאמור הראשונה שפרצה את מחסום המעריכיות. משך זמן רב עמדה בעיית הפירוק על סיבוכיות של <math>L_n[1/2,c]</math> והושגו רק שיפורים מינוריים בערכו של הקבוע <math>c</math>.

פריצת הדרך ארעה ב-[[1988]], כאשר המתמטיקאים [[ג'ון פולארד]], מארק מאנאס, [[הנדריק לנסטרה]] ו[[ארג'ן לנסטרה]] פרסמו את שיטת "נפת שדה המספרים המיוחדת", שנועדה לפירוק מספרים בעלי מבנה מיוחד, כזה של [[מספר פרמה|מספרי פרמה]] ומספרי קנינגהם. לשיטה זו סיבוכיות מהצורה <math>L_n[1/3,c]</math> כשהקבוע <math>c=(32/9)^{1/3}\approx1.526</math>. כמספר שנים לאחר מכן, פותח האלגוריתם הכללי – "נפת שדה המספרים הכללית", המתאים לפירוק כל [[מספר שלם]] ויעילותו מוערכת ב-<math>L_n[1/3,c]</math>, כשהקבוע <math>c=(64/9)^{1/3}\approx1.923</math>. בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות – אך אינן [[הוכחה|מוכחות]].

==לידתה של נפת שדה המספרים==
הרעיון של נפת שדה המספרים החל עם עבודתם של [[דון קופרסמיט]], [[אנדרו אודליצקו]] וריצ'רד שרופל, שניסו באמצע שנות ה-90 לפתור את [[בעיית הלוגריתם הבדיד]] באמצעות אלגוריתם [[שדה המספרים הריבועיים]] (Quadratic Number Field). הרעיון צד את עינו של פולרד שהציע ב-[[1988]] לנצל את האלגוריתם גם לפירוק לגורמים של מספרים מהצורה <math>x^3-k</math> כאשר <math>|k|</math> קטן בשיטה שכונתה '''שדה מספרים אלגבריים'''. תחילה נוסה האלגוריתם בהצלחה בפירוק המספר <math>2F_7=x^3+2</math> כאשר <math>x=2^{43}</math>. מאוחר יותר הרחיבו האחים לנסטרה, מאנאס ופולרד עצמו את האלגוריתם לפירוק מספרים מהצורה <math>r^e\pm s</math> כאשר <math>r</math> הוא שלם חיובי קטן ו-<math>|s|</math> קטן. מספרים אילו נקראים [[מספרי קנינגהם]] (Cunningham), האלגוריתם כונה [[נפת שדה מספרים מיוחדת]] (SNFS), יישום זה של האלגוריתם שימש בפירוק [[מספר פרמה]] התשיעי <math>F_9=2^{512}+1</math> (בסדר גודל של 155 ספרות עשרוניות), שהתגלה ככפולה של שלושה מספרים ראשוניים.

הגרסה הכללית של האלגוריתם פותחה ושופצה על ידי מתמטיקאים רבים בראשם ג'ו בוהלר, ארג'ן לנסטרה, [[קארל פומרנץ]], דון קופרסמיט ורבים אחרים. קופרסמיט הציע שיפורים אחדים שייעלו את האלגוריתם לזמן של <math>L_n[1/3,2.007]</math> ומקום בסדר גודל <math>L_n[1/3,1.639]</math>. מאוחר יותר דווח צוות מתמטיקאים בראשות ברנשטיין ולנסטרה שהפעילו את האלגוריתם באופן מקבילי עם 16,384 [[מעבד|מעבדים]] ופרקו בהצלחה מספר בגודל 119 ספרות עשרוניות בזמן קצר יחסית. קצב השיפור רק עלה במרוצת השנים. לנסטרה הכריז על הצלחתו לפרק באמצעות האלגוריתם, מודולוס [[RSA]] (ממספרי האתגר של מעבדות [[RSA (חברה)|RSA]]), בגודל 130 ספרות עשרוניות. בנובמבר [[2005]] שימש האלגוריתם בהצלחה לפירוק המודולוס RSA-200 (בגודל 200 ספרות עשרוניות) גם הוא ממספרי האתגר. זהו המספר הגדול ביותר שפורק לגורמים נכון להיום. המאמץ נמשך כמעט שלוש שנים, תוך שימוש במספר גדול של מחשבים שעבדו במקביל.

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

==מספרי פרמה ומספרי קנינגהם==
מספרי פרמה <math>F_k=2^{2^k}+1</math> נקראים על שם [[פייר דה פרמה]], שהתעניין בפירוק לגורמים בשל הקשר ל[[מספר משוכלל|מספרים משוכללים]] ו[[מספרים ידידים]]. הוא טען כי מספרים מהצורה <math>2^m+1</math> יכולים להיות ראשוניים רק אם <math>m</math> הוא [[חזקה של שתיים]], והאמין שמספרים אלה ראשוניים כולם. כיום ידוע שלא, למשל <math>F_5=2^{2^5}+1</math> אינו ראשוני, אם כי פרמה עצמו החמיץ עובדה זו מסיבה לא ידועה. שנים לאחר מכן הוכיח [[קרל פרידריך גאוס|גאוס]] את חשיבות מספרי פרמה ב[[גאומטריה]] אלמנטרית ומתמטיקאים רבים ניסו כוחם בפירוק מספרי פרמה תוך שימוש במיטב האלגוריתמים הידועים בתקופתם.

הבעיה הורחבה לבעיה כללית יותר של פירוק מספרים מהצורה <math>b^m\pm1</math> (כאשר <math>b</math> קטן ו-<math>m</math> גדול), מספרים אלה מכונים מספרי קנינגהם על שם המתמטיקאי [[אלן ג'וזף קנינגהם]] (Allan J. C. Cunningham). פרויקט קנינגהם הווה כעין מבחן כח להתקדמות בתחום הכללי של פירוק לגורמים. ב-[[1880]] מצאו מתמטיקאים את הגורמים הראשוניים של <math>F_6</math>, רק כמאה שנה לאחר מכן ב-[[1970]] הצליחו מוריסון וברילהרט לפרק את <math>F_7</math> באמצעות [[שבר משולב|שברים משולבים]]. מספר פרמה השמיני פורק ב-[[1980]] על ידי ברנט ופולארד באמצעות גרסה של [[אלגוריתם rho של פולרד]] היעיל במיוחד במציאת גורמים קטנים. מספר פרמה התשיעי פורק לחלוטין ב-[[1990]] על ידי האחים לנסטרה, מאנאס ופולארד שעשו זאת במאמץ שנמשך כארבעה חודשים, באמצעות נפת שדה המספרים והשתמשו בכח חישוב של כ-700 מחשבים שגויסו ממקומות שונים ברחבי העולם ומחשב-על אחד שריכז את העבודה. מספר פרמה העשירי פורק לגורמים ב-[[1999]] על ידי [[ריצ'רד ברנט]] באמצעות שיטת [[עקום אליפטי|העקום האליפטי]]. ב-[[1988]] נעשה שימוש באותה שיטה כדי לפרק לגורמים את <math>F_{11}</math> (שגורמיו הראשוניים נמצאו כולם קטנים). גורמים ראשוניים אחדים של מספרי פרמה מסוימים עד <math>F_{32}</math> נמצאו גם הם, אך פירוקם המלא של מספרים אלה לגורמים טרם צלח.

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

==שיטת הנפה הריבועית==
{{ערך מורחב|נפה ריבועית}}
מלבד חלוקה נסיונית (Trial Division) הנאיבית, כל שיטות הפירוק הידועות כיום מבוססות על רעיון אחד: כדי לפרק את המספר <math>n</math>, יש לאתר זוג ריבועים, השקולים זה לזה [[חשבון מודולרי|מודולו]] <math>n</math>. אם <math>y^2\equiv x^2\!\!\!\pmod{n}</math> אך <math>y\not\equiv\pm x\!\!\!\pmod{n}</math>, אז <math>\gcd\{x-y,n\}</math> הוא גורם לא [[טריוויאלי (מתמטיקה)|טריוויאלי]] של <math>n</math> (gcd מסמן את [[מחלק משותף מקסימלי]]). 

אם <math>n</math> פריק והמספרים <math>x,y</math> (או לפחות אחד מהם) [[מספר אקראי|אקראיים]] וריבועיהם שקולים מודולו <math>n</math>, הסיכוי לכך ש-<math>y\equiv\pm x\!\!\!\pmod{n}</math> אינו עולה על חצי; לכן מספיק לאתר פתרונות למשוואה <math>y^2\equiv x^2\!\!\!\pmod{n}</math> האמורה, ובמקרה של כישלון לנסות לאתר זוג אחר. הדרך להשיג זוג כזה הוצעה לראשונה על ידי דיקסון ונוסתה לראשונה במסגרת שיטת הנפה הריבועית. היא מבוססת על כך שגם אם קשה לפרק את <math>n</math>, ישנם מספרים שקל לפרקם, אלו שכל גורמיהם קטנים יחסית (וניתנים לניחוש). בוחרים "בסיס" המורכב מ-<math>m</math> הראשוניים הקטנים ביותר <math>F=\{p_1,p_2,\ldots,p_m\}</math> ומספר שכל גורמיו נמצאים ב-<math>F</math> נקרא "F-[[מספר חלק|חלק]]". כעת מחפשים באקראי מספרים <math>r_i</math> עבורם <math>f(r_i)=r^2_i-n</math> הוא מספר חלק ביחס ל-<math>F</math>. מכיוון שהפירוק של כל אחד מהמספרים <math>f(r_i)</math> ידוע, אפשר לחפש מכפלות של מספרים כאלה, השוות בעצמן לריבוע. חיפוש זה נעשה באמצעות [[דירוג מטריצות|דירוג]] של [[מטריצה|מטריצת]] המעריכים שהתקבלה מן הפירוקים השונים, מודולו 2, וחיפוש [[תלות ליניארית]] בין וקטורי המעריכים. אותה מכפלה <math>f(r_{i_1})\cdots f(r_{i_k})</math> היא, מחד, מכפלה של גורמים ראשוניים שכל אחד מהם מופיע [[מספר זוגי]] של פעמים, ומאידך שקולה מודולו <math>n</math> לריבוע של <math>r_{i_1}\cdots r_{i_k}</math>. כך מתקבל זוג הריבועים המבוקש.

אלגוריתם נפת שדה המספרים משתמש ברעיונות דומים, אך הפולינום <math>f</math> אינו עוד ריבועי, וכך הפירוק אינו נעשה במספרים שלמים, אלא באיברים של חוג שלמים גדול יותר.

==תקציר האלגוריתם==
תיאור אלגוריתם נפת שדה המספרים כאמור מורכב מאוד, בקצרה הרעיון הבסיסי של פולרד היה למצוא [[פולינום מתוקן]] <math>f(x)</math> מעל השלמים <math>x</math> שהוא אי-פריק ובעל מעלה <math>d</math> נמוכה ולמצוא שלם <math>m</math> המקיים <math>f(m)\equiv0\!\!\!\pmod{n}</math> למשל עבור מספר פרמה התשיעי <math>n=2^{2^9}+1</math> זה קל כיוון ש-<math>8n=2^{515}+8</math> לכן אם <math>f(x)=x^5+8</math> אז <math>m=2^{103}</math>. אולם עבור שלמים פריקים אחרים זה קצת יותר מורכב, הטריק הוא לקבוע תחילה את ה'''מעלה''' (אותה מחשבים על ידי <math>d\approx\frac{3\ln(n)}{2\ln(\ln(n))}</math>. בדרך כלל <math>d</math> הוא שלם אי-זוגי קטן כגון <math>d=5</math>).

לאחר מכן קובעים את <math>m=\lfloor n^{1/d}\rfloor=\lfloor\sqrt[d]{n}\rfloor</math> ומייצגים את <math>n</math> ב[[בסיס (אריתמטיקה)|בסיס]] <math>m</math> עבורו
:<math>n=c_dm^d+c_{d-1}m^{d-1}+\cdots+c_1m+c_0</math> (המקדם <math>c_d</math> הוא 1 אם <math>n>(2d)^d</math>).
כאשר המקדמים של <math>m</math> מקיימים <math>0\le c_i<m</math>.

כעת ניתן להגדיר את הפולינום <math>f</math>:
:<math>f(x)=c_dx^d+c_{d-1}x^{d-1}+\cdots+c_1x+c_0</math>
כך שמתקיים <math>f(m)\equiv0\!\!\!\pmod{n}</math>. בסבירות גבוהה <math>f(x)</math> הוא אי-פריק (במקרה שלא הרי שעובדה זו יכולה לסייע במציאת הגורמים הראשוניים של <math>n</math> בזמן פולינומי, מה שלא סביר שיקרה). 

נסמן ב-<math>\alpha</math> שורש כלשהו של <math>f(x)</math> ב[[שדה המספרים המרוכבים]], ונתבונן ב[[חוג (מבנה אלגברי)|חוג]] <math>\Z[\alpha]</math> הנוצר על ידי סיפוח השורש ל[[חוג המספרים השלמים|מספרים השלמים]]. היות ש-<math>f(m)\equiv0\!\!\!\pmod{n}</math> אפשר להחליף את כל המופעים של <math>\alpha</math> בשארית <math>m\bmod n</math> ונקבל מיפוי טבעי <math>\phi</math> מהחוג <math>\Z[\alpha]</math> ל-<math>\Z_n</math> בתנאים האמורים <math>\phi</math> הוא [[הומומורפיזם]] של חוגים. 

אוספים קבוצה <math>S</math> של זוגות [[מספרים זרים|זרים]] <math>a,b</math> עם המאפיינים שכפולה של [[מספר אלגברי|השלמים האלגבריים]] <math>a-\alpha b</math> עבור כל הזוגות <math>a,b</math> ב-<math>S</math> הם [[מספר ריבועי]] ב-<math>\Z[\alpha]</math> נסמנו <math>\gamma^2</math>, וכן כפולה של כל השלמים <math>a-mb</math> עבור <math>a,b\in S</math> היא מספר ריבועי ב-<math>\Z</math> אותה נסמן <math>v^2</math>. אפשר להחליף את כל המופעים של <math>\alpha</math> בשלם <math>m</math> ומקבלים את <math>u</math> כך שמתקיים <math>\phi(\gamma)\equiv u\!\!\!\pmod{n}</math>. ומזה נובע כי:
:<math>u^2\equiv\phi(\gamma)^2=\phi(\gamma^2)=\phi\left(\prod_{a,b\in S}(a-\alpha b)\right)=\prod_{a,b\in S}\phi(a-\alpha b)\equiv\prod_{a,b\in S}(a-mb)\equiv v^2\!\!\!\pmod{n}</math>
וכעת יש לנו <math>u,v</math> להם אנו זקוקים כדי לפרק את <math>n</math> כיוון שכאמור אם <math>u\not\equiv\pm v\!\!\!\pmod{n}</math> אז <math>\gcd(u-v,n)</math> הוא גורם לא טריוויאלי של <math>n</math>. 

נותר לברר כיצד למצוא קבוצה <math>S</math> כזו שמקיימת את שני המאפיינים המתוארים. לשם כך יש צורך למצוא מספרים חלקים, הטריק הוא להיעזר ב[[נורמה (אלגברה)|נורמה]]. הנורמה של <math>a-\alpha b</math> המסומנת <math>N(a-\alpha b)</math> מעל <math>\Q</math> קלה לחישוב והיא <math>b^df(a/b)</math>. בהנחה כי <math>a-\alpha b</math> הוא מספר חלק אם הנורמה שלו חלקה. מוודים שהנורמה של המספרים האלגבריים חלקה, בשיטת הניפוי באמצעות וקטור המעריכים ואלגברה ליניארית מעל השדה <math>\mathbb{F}_2</math>. כדי להבטיח כי גם כפולה של המספרים <math>a-\alpha b</math> מעל <math>\Z[\alpha]</math> היא מספר חלק, נעזרים ברעיון חוג השלמים האלגברים <math>\Q(\alpha)</math>, עם התכונה שכל [[אידיאל ראשוני|האידיאליים הראשוניים]] הגורמים של <math>a-\alpha b</math> עבור <math>a,b</math> זרים, הם ממעלה 1 והנורמה שלהם היא ראשוני רציונלי. לכן בוחרים קבוצה <math>R_p</math> עבור כל <math>p</math>, הכוללת את כל הראשוניים המקיימים <math>f(x)\equiv0\!\!\!\pmod{p}</math>. אם מתקבל זוג <math>a,b</math> כאשר הנורמה <math>N(a-\alpha b)</math> מתחלקת ב-<math>p</math> אזי גם <math>a-\alpha b</math> מתחלק באחד האידיאליים הראשוניים ב-<math>R_p</math> וקל לדעת איזה מהם כי <math>a/b</math> יהיה שקול [[מודולו]] <math>p</math> לאחד מהם. 

כדי להבטיח שכפולה של כל <math>a-\alpha b</math> בחוג <math>\Z[\alpha]</math> נותנת מספר ריבועי נעזרים ברעיון של [[לאונרד אדלמן]] שנקרא [[מציין הריבועי]] (quadratic character), לפי [[אדריאן-מארי לז'נדר|לז'נדר]], למספר ריבועי מציין ריבועי 1 ביחס לכל הראשוניים שאינם מחלקים שלו. מגדירים קבוצה <math>Q</math> הכוללת את כל השלמים שאינם מחלקים של <math>a-\alpha b</math>, משתמשים ב[[אלגברה ליניארית]] כדי למצוא מספרים חלקים  עם שני מאפיינים, האחד שוקטור המעריכים שלהם זוגי והשני שהמציין הריבועי שלהם הוא 1. בסיכויים גבוהים <math>a-\alpha b</math> הוא מספר ריבועי. 

כדי למצוא את <math>x,y</math> המקיימים <math>x^2\equiv y^2\!\!\!\pmod{n}</math> הדרושים לפירוק <math>n</math>, נותר לחשב את [[שורש ריבועי|השורש הריבועי]] של הכפולה של כל <math>a-\alpha b</math>, כלומר השורש הריבועי <math>\beta^2=\prod_i(a_i-\alpha b_i)</math>, אותו קל יותר לחשב אותו כ-<math>\phi(\beta^2)=x^2</math> ב-<math>\Z_n</math>, היות שמדובר בחישוב שורש בשדה <math>F_{p^d}</math> אפשר להיעזר באלגוריתם יעיל לחישוב שורשים ריבועיים בשדות ראשוניים, כמו [[אלגוריתם Shanks-Tonelli]] או אלגוריתם מונטגומרי ואז לפתור את מערכת השקילויות באמצעות [[משפט השאריות הסיני]] כדי לקבל את <math>x</math>. ולסיום נותר לחשב את <math>\gcd\{x-y,n\}</math> ומתקבל גורם ראשוני של <math>n</math>.

שלב חיפוש המספרים החלקים המתאימים (שכמובן רצוי שיהיו קטנים ככל האפשר) הוא לב ליבו של האלגוריתם. חלק זה ניתן לביצוע גם במקביל במספר נקודות חישוב, כלומר כל נקודת חישוב מחפשת ערכי <math>a</math> מתאימים עבור <math>b</math> אחר. וכאשר נמצאו מספיק זוגות החומר מועבר ל[[מחשב מרכזי]] (בדרך כלל [[מחשב-על]]) שבו מתבצע שלב הניפוי הסופי.

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

==קישורים חיצוניים==
*המאמר [http://www.ams.org/notices/199612/pomerance.pdf A Tale of Two Sieves] של [[קרל פומרנץ]] ממציא [[נפה ריבועית|הנפה הריבועית]] ונמנה עם מפתחי NFS.
*מאמר על [http://www.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb178.pdf פולינומים ממעלה שנייה לנפת שדה המספרים] של Brian Murphy ו-Richard Brent.
*Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag
*{{MathWorld}}

{{קריפטוגרפיה}}

[[קטגוריה:תורת המספרים]]
[[קטגוריה:מספרים ראשוניים]]
[[קטגוריה:שיטות פירוק לגורמים]]