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.

اخر الاخبار

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

قسم صناعة الشبابيك يشرع بإدامة شباكين قديمين لمرقد الإمامين العسكريين (عليهما السلام)

فرقة العباس (عليه السلام) تختتم خدماتها المقدمة للزائرين في سامراء

موكب العتبتين المقدستين يحيي ذكرى استشهاد الإمام الهادي (عليه السلام) في سامراء

العتبة العسكرية المقدسة تكرّم وفد العتبة العباسية المقدسة لمشاركته في تقديم الخدمات للزائرين

المزيد

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

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

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

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد