בעיה היא בעלת זמן פולינומיאלי או ב- P אם היא יכולה להיפתר על ידי אלגוריתם בעל פחות מ- (n^t) פעולות בסיסיות, כאשר t מספר סופי כלשהו והמשתנה n מודד את גודל הבעיה.

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

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

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

מספר ראשוני הנו מספר אשר אין לו מחלקים מלבד עצמו ו- 1. כך המספרים ..,2,3,5,7,11 והלאה הנם מספרים ראשוניים. ישנם אין סוף מספרים ראשוניים, והגדול ביותר הידוע לנו הוא

1- (2^6,972,593).