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

תיאור אלגוריתם נפת שדה המספרים כאמור מורכב מאוד, בקצרה הרעיון הבסיסי של פולרד היה למצוא פולינום מתוקן  f(x) מעל השלמים  x שהוא אי-פריק ובעל מעלה  d נמוכה ולמצוא שלם  m המקיים  f(m)\equiv 0\!\!\!{\pmod {n}} למשל עבור מספר פרמה התשיעי  n=2^{2^{9}}+1 זה קל כיוון ש- 8n=2^{515}+8 לכן אם  f(x)=x^{5}+8 אז  m=2^{103}. אולם עבור שלמים פריקים אחרים זה קצת יותר מורכב, הטריק הוא לקבוע תחילה את המעלה (אותה מחשבים על ידי  d\approx {\frac {3\ln(n)}{2\ln(\ln(n))}}. בדרך כלל  d הוא שלם אי-זוגי קטן כגון  d=5).
לאחר מכן קובעים את  m=\lfloor n^{1/d}\rfloor =\lfloor {\sqrt[{d}]{n}}\rfloor  ומייצגים את  n בבסיס  m עבורו
כאשר המקדמים של  m מקיימים  0\leq c_{i}<m.
כעת ניתן להגדיר את הפולינום  f:
כך שמתקיים  f(m)\equiv 0\!\!\!{\pmod {n}}. בסבירות גבוהה  f(x) הוא אי-פריק (במקרה שלא הרי שעובדה זו יכולה לסייע במציאת הגורמים הראשוניים של  n בזמן פולינומי, מה שלא סביר שיקרה).
נסמן ב- \alpha  שורש כלשהו של  f(x) בשדה המספרים המרוכבים, ונתבונן בחוג  \mathbb {Z} [\alpha ] הנוצר על ידי סיפוח השורש למספרים השלמים. היות ש- f(m)\equiv 0\!\!\!{\pmod {n}} אפשר להחליף את כל המופעים של  \alpha  בשארית  m{\bmod {n}} ונקבל מיפוי טבעי  \phi  מהחוג  \mathbb {Z} [\alpha ] ל- \mathbb {Z} _{n} בתנאים האמורים  \phi  הוא הומומורפיזם של חוגים.
אוספים קבוצה  S של זוגות זרים  a,b עם המאפיינים שכפולה של השלמים האלגבריים  a-\alpha b עבור כל הזוגות  a,b ב- S הם מספר ריבועי ב- \mathbb {Z} [\alpha ] נסמנו  \gamma ^{2}, וכן כפולה של כל השלמים  a-mb עבור  a,b\in S היא מספר ריבועי ב- \mathbb {Z}  אותה נסמן  v^{2}. אפשר להחליף את כל המופעים של  \alpha  בשלם  m ומקבלים את  u כך שמתקיים  \phi (\gamma )\equiv u\!\!\!{\pmod {n}}. ומזה נובע כי:
וכעת יש לנו  u,v להם אנו זקוקים כדי לפרק את  n כיוון שכאמור אם  u\not \equiv \pm v\!\!\!{\pmod {n}} אז  \gcd(u-v,n) הוא גורם לא טריוויאלי של  n.
נותר לברר כיצד למצוא קבוצה  S כזו שמקיימת את שני המאפיינים המתוארים. לשם כך יש צורך למצוא מספרים חלקים, הטריק הוא להיעזר בנורמה. הנורמה של  a-\alpha b המסומנת  N(a-\alpha b) מעל  \mathbb {Q}  קלה לחישוב והיא  b^{d}f(a/b). בהנחה כי  a-\alpha b הוא מספר חלק אם הנורמה שלו חלקה. מוודים שהנורמה של המספרים האלגבריים חלקה, בשיטת הניפוי באמצעות וקטור המעריכים ואלגברה ליניארית מעל השדה  \mathbb {F} _{2}. כדי להבטיח כי גם כפולה של המספרים  a-\alpha b מעל  \mathbb {Z} [\alpha ] היא מספר חלק, נעזרים ברעיון חוג השלמים האלגברים  \mathbb {Q} (\alpha ), עם התכונה שכל האידיאליים הראשוניים הגורמים של  a-\alpha b עבור  a,b זרים, הם ממעלה 1 והנורמה שלהם היא ראשוני רציונלי. לכן בוחרים קבוצה  R_{p} עבור כל  p, הכוללת את כל הראשוניים המקיימים  f(x)\equiv 0\!\!\!{\pmod {p}}. אם מתקבל זוג  a,b כאשר הנורמה  N(a-\alpha b) מתחלקת ב- p אזי גם  a-\alpha b מתחלק באחד האידיאליים הראשוניים ב- R_{p} וקל לדעת איזה מהם כי  a/b יהיה שקול מודולו  p לאחד מהם.
כדי להבטיח שכפולה של כל  a-\alpha b בחוג  \mathbb {Z} [\alpha ] נותנת מספר ריבועי נעזרים ברעיון של לאונרד אדלמן שנקרא מציין הריבועי (quadratic character), לפי לז'נדר, למספר ריבועי מציין ריבועי 1 ביחס לכל הראשוניים שאינם מחלקים שלו. מגדירים קבוצה  Q הכוללת את כל השלמים שאינם מחלקים של  a-\alpha b, משתמשים באלגברה ליניארית כדי למצוא מספרים חלקים  עם שני מאפיינים, האחד שוקטור המעריכים שלהם זוגי והשני שהמציין הריבועי שלהם הוא 1. בסיכויים גבוהים  a-\alpha b הוא מספר ריבועי.
כדי למצוא את  x,y המקיימים  x^{2}\equiv y^{2}\!\!\!{\pmod {n}} הדרושים לפירוק  n, נותר לחשב את השורש הריבועי של הכפולה של כל  a-\alpha b, כלומר השורש הריבועי  \beta ^{2}=\prod _{i}(a_{i}-\alpha b_{i}), אותו קל יותר לחשב אותו כ- \phi (\beta ^{2})=x^{2} ב- \mathbb {Z} _{n}, היות שמדובר בחישוב שורש בשדה  F_{p^{d}} אפשר להיעזר באלגוריתם יעיל לחישוב שורשים ריבועיים בשדות ראשוניים, כמו אלגוריתם Shanks-Tonelli או אלגוריתם מונטגומרי ואז לפתור את מערכת השקילויות באמצעות משפט השאריות הסיני כדי לקבל את  x. ולסיום נותר לחשב את  \gcd\{x-y,n\} ומתקבל גורם ראשוני של  n.
שלב חיפוש המספרים החלקים המתאימים (שכמובן רצוי שיהיו קטנים ככל האפשר) הוא לב ליבו של האלגוריתם. חלק זה ניתן לביצוע גם במקביל במספר נקודות חישוב, כלומר כל נקודת חישוב מחפשת ערכי  a מתאימים עבור  b אחר. וכאשר נמצאו מספיק זוגות החומר מועבר למחשב מרכזי (בדרך כלל מחשב-על) שבו מתבצע שלב הניפוי הסופי.
שלב הניפוי שהוא חיפוש תלויות ליניאריות, התגלה כבעייתי גם הוא לאחר שנמצא כי המטריצה מגיעה לסדר גודל העולה של מאות ג'יגה בית. הודות לתרומתו של ויידמן ניתן לדחוס את המטריצה ולבצע דירוג בסדר גודל כזה ביעילות יחסית (בתוך מספר שבועות).