Given a number , Fermat's factorization methods look for integers  and  such that . Then

(1)

and  is factored. A modified form of this observation leads to Dixon's factorization method and the quadratic sieve.

Every positive odd integer can be represented in the form  by writing  (with ) and noting that this gives

			(2)
			(3)

Adding and subtracting,

			(4)
			(5)

so solving for  and  gives

			(6)
			(7)

Therefore,

(8)

As the first trial for , try , where  is the ceiling function. Then check if

(9)

is a square number. There are only 22 combinations of the last two digits which a square number can assume, so most combinations can be eliminated. If  is not a square number, then try

(10)

so

			(11)
			(12)
			(13)
			(14)

Continue with

			(15)
			(16)
			(17)
			(18)
			(19)

so subsequent differences are obtained simply by adding two.

Maurice Kraitchik sped up the algorithm by looking for  and  satisfying

(20)

i.e., . This congruence has uninteresting solutions  and interesting solutions . It turns out that if  is odd and divisible by at least two different primes, then at least half of the solutions to  with  relatively prime to  are interesting. For such solutions,  is neither  nor 1 and is therefore a nontrivial factor of  (Pomerance 1996). This algorithm can be used to prove primality, but is not practical. In 1931, Lehmer and Powers discovered how to search for such pairs using continued fractions. This method was improved by Morrison and Brillhart (1975) into the continued fraction factorization algorithm, which was the fastest algorithm in use before the quadratic sieve factorization method was developed.

REFERENCES:

Lehmer, D. H. and Powers, R. E. "On Factoring Large Numbers." Bull. Amer. Math. Soc. 37, 770-776, 1931.

McKee, J. "Speeding Fermat's Factoring Method." Math. Comput. 68, 1729-1738, 1999.

Morrison, M. A. and Brillhart, J. "A Method of Factoring and the Factorization of ." Math. Comput. 29, 183-205, 1975.

Pomerance, C. "A Tale of Two Sieves." Not. Amer. Math. Soc. 43, 1473-1485, 1996.

اخر الاخبار

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

العتبة العباسية المقدسة تواصل تنظيم مجالس العزاء الصباحية بذكرى زيارة عاشوراء

مواكب العزاء تستذكر في التاسع من شهر المحرم شهادة عبدالله الرضيع بن الحسين (عليهما السلام)

العتبة العباسية المقدسة تستذكر تضحيات القاسم بن الحسن (عليهما السلام)

شعبة الحرم الشريف تواصل تنفيذ خطتها الخاصة بشهر المحرّم داخل مرقد أبي الفضل العباس (عليه السلام)

المزيد

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

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

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

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد