כל מספר יכול להיות מיוצג בצורה ייחודית כמכפלה של מספר ראשוני. לדוגמא 10=2*5 (הסימן * מקובל כסימן מכפלה במדעי המחשב) והוא ייחודי (מלבד סדר הגורמים 2 ו-5). אומנות הפרוק לגורמים עתיקה כמעט כמתימטיקה עצמה. אך המחקר של אלגוריתמים מהירים לפרוק לגורמים הנו בן עשורים מעטים.

אלגוריתם אחד אפשרי לפרוק לגורמים של מספר הוא חלוקתו על ידי המספרים הראשוניים הקטנים עד אשר השארית היא מספר ראשוני. אלגוריתם זה יעיל כל עוד גודל המספרים פחות מ- ¹⁶10 מכיוון שזה דורש ניסיונות מול כל המספרים הראשוניים עד גודל ⁸10 . במערכות הצפנה עם מפתח ציבורי המבוססות על בעיית הפרוק לגורמים, מספרים מגיעים לסדרי גודל עד ³⁰⁰10 וזה יצריך ניסיונות מול כל המספרים הראשוניים עד ¹⁵⁰10 וישנם ¹⁴⁷10 מספריים ראשוניים כאלה לפי משפט המספרים הראשוניים. גודל זה עובר את כמות האטומים ביקום, ולא נראה שניתן למנות מספר כזה באמצעי כלשהו.

המקרה הפשוט או הקל יותר של פרוק לגורמים כאשר המספר הנתון הוא בעל גורמים של מספרים ראשוניים קטנים. לדוגמא, 759375 הוא קל לפרוק וניתן לכתוב אותו כך 3⁵ כפול 5⁵. בהצפנה אנו רוצים להשתמש רק במספרים בעלי גורמים עם מספרים ראשוניים גדולים. ההעדפה תהיה בבחירת מספר עם שני גורמים ראשוניים גדולים, כפי שנעשה במערכות ההצפנה המבוססות RSA.

כיום אחד האלגוריתמים הטובים ביותר לפירוק לגורמים נקרא NFS (number field sieve) מסננת שדה המספר- הבנויה משלב הסינון ומצעד המערך. שלב הסינון יכול להתפרס על פני מספר רב של משתתפים, אך צעד המערך צריך להתבצע במחשבי על חזקים. היעילות של אלגוריתם ה-NFS מתגלה עבור מספרים גדולים מאד. הוא יכול לפרק לגורמים מספרים בגודל של ¹⁵⁰10 בחודשים אחדים. אלגוריתם ה- NFS לוקח זמן תת-מעריכי (אשר אינו יעיל למדי).

לא ידועה הוכחה לכך שפרוק לגורמים הוא בעיה קשה ב- NP ולא שהוא אינו פתיר בזמן פולינומיאלי. אם בעיה כלשהי קשה ב- NP הייתה פתירה בזמן פולינומיאלי, אזי הפרוק לגורמים היה כזה גם כן, אך ישנה תקווה מעטה לכך. מקובל על הדעת רוב החוקרים ועל פי הידע הנוכחי שפרוק לגורמים אינו פתיר בזמן פולינומיאלי.