In order to find integers  and  such that

(1)

(a modified form of Fermat's factorization method), in which case there is a 50% chance that  is a factor of , choose a random integer , compute

(2)

and try to factor . If  is not easily factorable (up to some small trial divisor ), try another . In practice, the trial s are usually taken to be , with , 2, ..., which allows the quadratic sieve factorization method to be used. Continue finding and factoring s until  are found, where  is the prime counting function. Now for each , write

(3)

and form the exponent vector

(4)

Now, if  are even for any , then  is a square number and we have found a solution to (◇). If not, look for a linear combination  such that the elements are all even, i.e.,

(5)

(6)

Since this must be solved only mod 2, the problem can be simplified by replacing the s with

{0 for a_(ij) even; 1 for a_(ij) odd. " src="https://mathworld.wolfram.com/images/equations/DixonsFactorizationMethod/NumberedEquation7.gif" style="height:46px; width:137px" />

(7)

Gaussian elimination can then be used to solve

(8)

for , where  is a vector equal to  (mod 2). Once  is known, then we have

(9)

where the products are taken over all  for which . Both sides are perfect squares, so we have a 50% chance that this yields a nontrivial factor of . If it does not, then we proceed to a different  and repeat the procedure. There is no guarantee that this method will yield a factor, but in practice it produces factors faster than any method using trial divisors. It is especially amenable to parallel processing, since each processor can work on a different value of 

REFERENCES:

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

Dixon, J. D. "Asymptotically Fast Factorization of Integers." Math. Comput. 36, 255-260, 1981.

Lenstra, A. K. and Lenstra, H. W. Jr. "Algorithms in Number Theory." In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (Ed. J. van Leeuwen). New York: Elsevier, pp. 673-715, 1990.

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

اخر الاخبار

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

عباس.. طفل فقد والده فوجد في خدمة زائري عاشوراء وطنًا آمنًا

شعبة الخطابة النسوية تواصل إقامة مجالس العزاء في شهر المحرم الحرام

لليوم الخامس.. العتبة العباسية المقدسة تقيم مجلس عزاء في صحن مرقد أبي الفضل العباس (عليه السلام)

قسم الشؤون الفكرية يقيم مجلس عزاء حسيني في العاصمة التنزانية دار السلام

المزيد

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

لمن تجاوز الستين.. عليك بشرب 4 أكواب من القهوة يوميا ؟

الحليب مع العسل.. مزيج يمنحك 7 فوائد صحية

لا تبالغ في التنظيف.. قليل من "الاتساخ" قد يحمي عائلتك

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

المزيد

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

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

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

كيف تساعد الصيانة الوقائية في الحفاظ على كفاءة التكييف في سيارتك ؟

في ظاهرة غريبة حيرت العلماء.. كوكبنا قد يسجل أقصر يوم في التاريخ هذا الصيف!

المزيد