مبدأ الخوارزمية:
Pollard Rho هي خوارزمية احتمالية لتحليل الأعداد الصحيحة، مناسبة بشكل خاص لإيجاد العوامل متوسطة الحجم للأعداد المركبة. سميت الخوارزمية بهذا الاسم لأن مسار تشغيلها يشبه الحرف اليوناني ρ (rho).
استراتيجيات التحسين:
- تحسين القسمة التجريبية:استخدام الأعداد الأولية الصغيرة (2, 3, 5, 7, 11...) للقسمة التجريبية، للعثور بسرعة على العوامل الصغيرة
- Pollard Rho:للأعداد المركبة الكبيرة، استخدام المتتالية العشوائية الزائفة x = (x² + c) mod n لإيجاد العوامل
- خوارزمية اكتشاف الدورة Floyd:استخدام مؤشرين سريع وبطيء للكشف عن الدورة في المتتالية، لتحسين التعقيد المكاني
- اختبار أولية Miller-Rabin:بعد إيجاد العامل، تحديد ما إذا كان عدداً أولياً لتجنب الاستمرار في التحليل
- التحليل التكراري:تحليل العوامل الموجودة تكراريًا حتى تصبح جميع العوامل أعداداً أولية
التعقيد الزمني:
- القسمة التجريبية:O(√n)، مناسب للأعداد الصغيرة أو إيجاد العوامل الصغيرة بسرعة
- Pollard Rho:الزمن المتوقع O(n^(1/4))، فعال جداً للأعداد ذات العوامل متوسطة الحجم
- Miller-Rabin:O(k log³n)، k هو عدد جولات الاختبار، يستخدم لتحديد الأولية