خوارزمية p - 1 لبولارد

خوارزمية p - 1 لبولارد (بالإنجليزية: Pollard's p − 1 algorithm)‏ هي خوارزمية تمكن من تحليل عدد صحيح إلى عوامل، تعتمد على نظرية الأعداد، اخترعها جون بولارد في عام 1974. هي خوارزمية ذات هدف خاص، أي أنها تناسب أعداد صحيحة تملك نوعا خاصا من العوامل.

انظر إلى أعداد آمنة وأعداد صوفي جيرمين الأولية وإلى أعداد أولية قوية وإلى شرط ضروري وشرط كاف وإلى توليد الأعداد العشوائية.

مفاهيم أساسية

ليكن n عددا مؤلفا (أي غير أولي)، من عوامله (أي من قواسمه الأولية) عدد p. من خلال مبرهنة فيرما الصغرى، نعلم أنه بالنسبة لكل عدد صحيح a أولي نسبيا مع العدد p وبالنسبة لكل عدد صحيح k، يتوفر ما يلي:

$a^{K(p-1)}\equiv 1(\mathrm{mod}p)$

الخوارزمية