A prime factorization algorithm also known as Pollard Monte Carlo factorization method. There are two aspects to the Pollard  factorization method. The first is the idea of iterating a formula until it falls into a cycle. Let , where  is the number to be factored and  and  are its unknown prime factors. Iterating the formula

(1)

or almost any polynomial formula (an exception being ) for any initial value  will produce a sequence of number that eventually fall into a cycle. The expected time until the s become cyclic and the expected length of the cycle are both proportional to .

However, since  with  and  relatively prime, the Chinese remainder theorem guarantees that each value of  (mod ) corresponds uniquely to the pair of values (), ). Furthermore, the sequence of s follows exactly the same formula modulo  and , i.e.,

			(2)
			(3)

Therefore, the sequence (mod ) will fall into a much shorter cycle of length on the order of . It can be directly verified that two values  and  have the same value (mod ), by computing

(4)

which is equal to .

The second part of Pollard's method concerns detection of the fact that a sequence has become periodic. Pollard's suggestion was to use the idea attributed to Floyd of comparing  to  for all . A different method is used in Brent's factorization method.

Under worst conditions, the Pollard  algorithm can be very slow.

REFERENCES:

Brent, R. "An Improved Monte Carlo Factorization Algorithm." Nordisk Tidskrift for Informationsbehandlung (BIT) 20, 176-184, 1980.

Brent, R. P. "Some Integer Factorization Algorithms Using Elliptic Curves." Austral. Comp. Sci. Comm. 8, 149-163, 1986.

Bressoud, D. M. Factorization and Primality Testing. New York: Springer-Verlag, pp. 61-67, 1989.

Eldershaw, C. and Brent, R. P. "Factorization of Large Integers on Some Vector and Parallel Computers."

Montgomery, P. L. "Speeding the Pollard and Elliptic Curve Methods of Factorization." Math. Comput. 48, 243-264, 1987.

Pollard, J. M. "A Monte Carlo Method for Factorization." Nordisk Tidskrift for Informationsbehandlung (BIT) 15, 331-334, 1975.

Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 83 and 102-103, 1991.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الفكرية يطلق باقة من النشاطات الرقمية الخاصة بشهر المحرم

العتبة العباسية المقدسة تختتم السلسلة الأولى لمشروع المحاضرات القرآنية العاشورائية في بابل

العتبة العباسية المقدسة تسلّم راية العزاء إلى تجمّع مواكب محافظة الديوانية

قسم الشؤون الفكرية يواصل إقامة المجالس الحسينية ضمن سلسلة (بيوت النعيم)

المزيد

الآخبار الصحية

تناول الجبن.. مفيد للجسم أم خطر يهدد صحتك؟

طبيبة أسنان تحذر.. لا تتجاهل هذه العلامة بعد التنظيف

يجب أن تأكل المزيد من الشمام هذا الصيف.. إليك السبب ؟

تأثير صحي كبير.. كم بيضة يجب أن تتناول يوميا؟

المزيد

الآخبار التكنلوجية

أداء خلايا البيروفسكايت الشمسية تحت الماء قد يزيد كفاءة تحويل الكهرباء

مسافة الأمان: أساس القيادة الآمنة وتجنب الحوادث

هل القيادة السريعة تعني استهلاك اكثر للوقود؟

لماذا يعتبر كوكب المريخ غير صالح للحياة؟

المزيد