طريقة أويلر للتحليل إلى عوامل

طريقة أويلر للتحليل هي أسلوب لتحليل عدد ما عن طريق كتابته كمجموع مربعين بطريقتين مختلفتين. على سبيل المثال، العدد${\displaystyle 1000009}$يمكن كتابتها على النحو التالي${\displaystyle 1000^{2}+3^{2}}$أو كما${\displaystyle 972^{2}+235^{2}}$وتعطي طريقة أويلر التحليل إلى عوامل${\displaystyle 1000009=293\cdot 3413}$.

يبدو أن فكرة إمكانية الحصول على تحليل عدد فردي موجب من خلال تمثيلين مختلفين قد اقترحها مارين ميرسين لأول مرة . مع ذلك، لم تُستخدم هذه الفكرة على نطاق واسع إلا بعد مئة عام على يد أويلر. وكان أشهر استخداماته لهذه الطريقة، التي تحمل اسمه الآن، هو تحليل العدد إلى عوامله الأولية.${\displaystyle 1000009}$، والذي كان يُعتقد سابقًا أنه عدد أولي على الرغم من أنه ليس عددًا أوليًا زائفًا وفقًا لأي اختبار رئيسي للأعداد الأولية.

تُعدّ طريقة أويلر للتحليل إلى عوامل أكثر فعالية من طريقة فيرما للأعداد الصحيحة التي لا تتقارب عواملها، وربما تكون أكثر كفاءة من القسمة التجريبية إذا أمكن إيجاد تمثيلات للأعداد كمجموع مربعين بسهولة نسبية. وتتشابه الطرق المستخدمة لإيجاد هذه التمثيلات مع طرق إيجاد الفروق بين المربعات في طريقة فيرما للتحليل إلى عوامل .

تتمثل أبرز عيوب طريقة أويلر في التحليل إلى عوامل أولية في عدم إمكانية تطبيقها على تحليل أي عدد صحيح يحتوي على أي عامل أولي من الشكل 4k +  3  مرفوعًا لقوة فردية في تحليله إلى عوامل أولية، إذ لا يمكن لمثل هذا العدد أن يكون مجموع مربعين. كذلك، فإن الأعداد المركبة الزوجية والفردية من الشكل 4k +  1  غالبًا ما تكون حاصل ضرب عددين أوليين من الشكل 4k +  3  (مثلًا 3053 = 43 × 71)، ولا يمكن تحليلها باستخدام طريقة أويلر.

أدى هذا التطبيق المحدود إلى جعل طريقة أويلر للتحليل إلى عوامل أولية غير مفضلة في خوارزميات التحليل الحاسوبية ، إذ من غير المرجح أن يعرف أي مستخدم يحاول تحليل عدد صحيح عشوائي ما إذا كان من الممكن تطبيق طريقة أويلر على هذا العدد. ولم تظهر محاولات تطوير طريقة أويلر إلى خوارزميات حاسوبية لاستخدامها على أعداد محددة حيث يُعرف إمكانية تطبيق طريقة أويلر.

تنص متطابقة براهمغوبتا -فيوناتشي على أن حاصل ضرب مجموع مربعين يساوي مجموع مربعين. تعتمد طريقة أويلر على هذه النظرية، ولكن يمكن اعتبارها عكسها، بالنظر إلى${\displaystyle n=a^{2}+b^{2}=c^{2}+d^{2}}$نجد${\displaystyle n}$كحاصل ضرب مجموع مربعين.

استنتج أولاً أن

${\displaystyle a^{2}-c^{2}=d^{2}-b^{2}}$

وقم بتحليل كلا الجانبين للحصول على

${\displaystyle (ac)(a+c)=(db)(d+b)}$(1)

والآن لنبدأ${\displaystyle k=\operatorname {gcd} (ac,db)}$و${\displaystyle h=\operatorname {gcd} (a+c,d+b)}$بحيث توجد بعض الثوابت${\displaystyle l,m,l',m'}$مُرضٍ

• ${\displaystyle (ac)=kl}$،
• ${\displaystyle (db)=km}$،

${\displaystyle \operatorname {gcd} (l,m)=1}$

• ${\displaystyle (a+c)=hm'}$،
• ${\displaystyle (d+b)=hl'}$،

${\displaystyle \operatorname {gcd} (l',m')=1}$

وبتعويض هذه القيم في المعادلة (1) نحصل على

${\displaystyle klhm'=kmhl'}$

يؤدي حذف العوامل المشتركة إلى

${\displaystyle lm'=l'm}$

والآن باستخدام حقيقة أن${\displaystyle (l,m)}$و${\displaystyle \left(l',m'\right)}$إذا كانت أزواجًا من الأعداد الأولية فيما بينها، فإننا نجد أن

• ${\displaystyle l=l'}$
• ${\displaystyle m=m'}$

لذا

• ${\displaystyle (ac)=kl}$
• ${\displaystyle (db)=km}$
• ${\displaystyle (a+c)=hm}$
• ${\displaystyle (d+b)=hl}$

نرى الآن أن${\displaystyle m=\operatorname {gcd} (a+c,db)}$و${\displaystyle l=\operatorname {gcd} (ac,d+b)}$

بتطبيق متطابقة براهمغوبتا-فيوناتشي نحصل على

${\displaystyle \left(k^{2}+h^{2}\right)\left(l^{2}+m^{2}\right)=(kl+hm)^{2}+(km-hl)^{2}={\bigl (}(ac)+(a+c){\bigr )}^{2}+{\bigl (}(db)-(d+b){\bigr )}^{2}=(2a)^{2}+(2b)^{2}=4n.}$

بما أن كل عامل هو مجموع مربعين، فلا بد أن يحتوي أحدهما على عددين زوجيين: إما${\displaystyle (k,h)}$أو${\displaystyle (l,m)}$دون الإخلال بعمومية المسألة، افترض أن الزوج${\displaystyle (k,h)}$عدد زوجي. يصبح التحليل إلى عوامل عندئذٍ

${\displaystyle n=\left(\left({\tfrac {k}{2}}\right)^{2}+\left({\tfrac {h}{2}}\right)^{2}\right)\left(l^{2}+m^{2}\right).\,}$

منذ:${\displaystyle \ 1000009=1000^{2}+3^{2}=972^{2}+235^{2}}$

لدينا من الصيغة أعلاه:

هكذا،

${\displaystyle 1000009=\left[\left({\frac {4}{2}}\right)^{2}+\left({\frac {34}{2}}\right)^{2}\right]\cdot \left[\left({\frac {14}{2}}\right)^{2}+\left({\frac {116}{2}}\right)^{2}\right]\,}$

${\displaystyle =\left(2^{2}+17^{2}\right)\cdot \left(7^{2}+58^{2}\right)\,}$

${\displaystyle =(4+289)\cdot (49+3364)\,}$

${\displaystyle =293\cdot 3413\,}$

دالة Euler_factorize(int n) -> list[int] إذا كان n عددًا أوليًا، print("العدد غير قابل للتحليل إلى عوامله الأولية") دالة الخروج حلقة تكرارية من a=1 إلى a=ceiling(sqrt(n)) b2 = n - a*a b = floor(sqrt(b2)) إذا كان b*b==b2 كسر الحلقة مع الحفاظ على a و b إذا كان a*a+b*b!=n فإن print("لم يتم العثور على أي تعبير لـ n كمجموع مربعات") دالة الخروج حلقة تكرارية من c=a+1 إلى c=ceiling(sqrt(n)) د2 = ن - ج*ج د = الجزء الصحيح من (جذر(د2)) إذا كان d*d==d2 فإن كسر الحلقة مع الحفاظ على c،d إذا كان c*c+d*d!=n فإن print("فشل في إيجاد تعبير ثانٍ لـ n كمجموع مربعات") دالة الخروج أ = ج أ، ب = ج + أ ج = ب د، د = ب + د ك = GCD(A,C)//2, h = GCD(B,D)//2 l = GCD(A,D)//2, m = GCD(B,C)//2 العامل 1 = k*k + h*h العامل 2 = ل × ل + م × م إرجاع قائمة[ العامل1، العامل2 ]

• أور، أويستين (1988). "طريقة أويلر للتحليل إلى عوامل" . نظرية الأعداد وتاريخها . مؤسسة كورير. ص 59-64 . ISBN  978-0-486-65620-5.
• ماكي، جيمس (1996). "تحويل طريقة أويلر للتحليل إلى خوارزمية تحليل". نشرة الجمعية الرياضية في لندن . 4 (28): 351-355 . doi : 10.1112/blms/28.4.351 .