פירוק לגורמים של מספר שלם – הבדלי גרסאות

לבעיית הפירוק לגורמים לא ידוע פתרון [[יעילות אלגוריתמית|יעיל אלגוריתמית]], כלומר כזה ש[[סיבוכיות זמן|זמן ריצתו]] [[פולינום|פולינומי]] ביחס למספר הספרות במספר שמפרקים. נחשדההשערה הרווחת היא שפתרון כזה לא קיים (משמע בעיית הפירוק לגורמים אינה ב-[[P (מחלקת סיבוכיות)|P]]) ועל חשדהשערה זהזו מבוססות שיטות הצפנה רבות כגון [[RSA]]. עם זאת, מבין הבעיות שאינן ניתנות לפתרון יעיל, בעיית הפירוק לגורמים נחשבת ל"קלה באופן יחסי". בפרט סבורים שהיא אינה [[בעיה NP-קשה]]. עדות לסברה זו היא [[אלגוריתם שור]], [[אלגוריתם קוונטי]] שפותר את בעיית הפירוק לגורמים בזמן פולינומי (מכאן שאילו בעיית הפירוק לגורמים הייתה NP-קשה, אזי [[NP (מחלקת סיבוכיות)|NP]] הייתה מוכלת ב-[[BQP]] בניגוד לסברהלהשערה הרווחת). כמו כן ידוע שבעיית הפירוק לגורמים שייכת ל-[[co-NP]], ולכן אילו היא הייתה NP-קשה הדבר היה גורר NP=co-NP, תוצאה הנחשבת מאוד לא סבירה.