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

מספר <math>\ 4<n</math> הוא פריק אם ורק אם <math>\ (n-1)! \equiv 0 \pmod{n}</math> (לשם השוואה, [[משפט וילסון]]: אם n ראשוני אז <math>\ (n-1)! \equiv -1 \pmod{n}</math>).

השיטות המהירות ביותר ל[[פירוק מספר שלם לגורמים|פירוק]] [[מספר גדול]] הן שיטת [[נפה ריבועית|הנפה הריבועית]] ושיטת ה[[נפת שדה מספרים]]. זמן הריצה של שיטות אלה תלוי רק בגודלו של המספר שאותו מבקשים לפרק. בהשוואה אליהן, [[שיטת רו של פולארד]] היא [[אלגוריתם הסתברותי]], המוצא מחלק של n בזמן שהוא בקירוב <math>\sqrt{p}</math>, כאשר p הוא המחלק הקטן ביותר (שכמובן אינושאינו ידוע מראש). שיטה זו עדיפה, אם כן, כאשר ידוע שלמספר יש [[גורם ראשוני]] קטן יחסית.