נפה ריבועית


כל מה שרצית לדעת על נפה ריבועית:
שיטת הנפה הריבועית היא שיטה מהירה לפירוק לגורמים של מספר שלם, המתאימה בעיקר למספרים בני 40-100 ספרות עשרוניות (שיטת רו של פולארד עדיפה לפירוק מספרים קטנים יותר, בעוד שבמספרים ארוכים יותר נפת שדה המספרים היא השיטה היעילה ביותר).
שיטת הנפה הריבועית, שהייתה השיטה הראשונה בעלת סיבוכיות תת-אקספוננציאלית לבעיית הפירוק לגורמים, פותחה על ידי קארל פומרנץ בשנת 1981.
פומרנץ הרחיב, למעשה, רעיונות קודמים של קרייטצניק (Kraitchnik) וג'ון ד' דיקסון.
זו הייתה השיטה המהירה ביותר (באופן אסימפטוטי), עד להמצאתה של נפת שדה המספרים, ב- 1993.

נלקח מויקיפדיה

הגדרות נוספות הקשורות לנפה ריבועית:
תורת המספרים
מספרים ראשוניים
שיטות פירוק לגורמים