تحليل كثيرات الحدود

يمكن إيجاد جميع العوامل الخطية ذات المعاملات النسبية باستخدام اختبار الجذر النسبي . إذا كانت كثيرة الحدود المراد تحليلها${\displaystyle a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$إذاً، فإن جميع العوامل الخطية الممكنة تكون على الشكل التالي:${\displaystyle b_{1}x-b_{0}}$، أين${\displaystyle b_{1}}$هو عامل صحيح لـ${\displaystyle a_{n}}$و${\displaystyle b_{0}}$هو عامل صحيح لـ${\displaystyle a_{0}}$يمكن اختبار جميع التوليفات الممكنة للعوامل الصحيحة للتأكد من صحتها، ويمكن استخراج كل توليفة صحيحة باستخدام القسمة المطولة لكثيرات الحدود . إذا كانت كثيرة الحدود الأصلية ناتجة عن عوامل، اثنان منها على الأقل من الدرجة الثانية أو أعلى، فإن هذه الطريقة توفر تحليلًا جزئيًا فقط؛ وإلا فإن التحليل يكون كاملًا. على وجه الخصوص، إذا كان هناك عامل غير خطي واحد فقط، فستكون هذه هي كثيرة الحدود المتبقية بعد استخراج جميع العوامل الخطية. في حالة كثيرة الحدود التكعيبية ، إذا كانت قابلة للتحليل، فإن اختبار الجذر النسبي يُعطي تحليلًا كاملًا، إما إلى عامل خطي وعامل تربيعي غير قابل للاختزال، أو إلى ثلاثة عوامل خطية.

تهدف طريقة كرونكر إلى تحليل كثيرات الحدود أحادية المتغير ذات المعاملات الصحيحة إلى كثيرات حدود ذات معاملات صحيحة.

تعتمد هذه الطريقة على حقيقة أن تقييم كثيرات الحدود الصحيحة عند قيم صحيحة يجب أن ينتج عنه أعداد صحيحة. أي، إذا${\displaystyle f(x)}$إذا كانت دالة كثيرة الحدود ذات معاملات صحيحة، فإن${\displaystyle f(a)}$يكون عددًا صحيحًا بمجرد أن يكون a عددًا صحيحًا. يوجد عدد محدود فقط من القيم الصحيحة الممكنة لعامل من عوامل a . لذا، إذا${\displaystyle g(x)}$هو عامل من عوامل${\displaystyle f(x),}$قيمة${\displaystyle g(a)}$لا بد أن يكون أحد عوامل${\displaystyle f(a).}$

إذا بحث المرء عن جميع عوامل الدرجة d المعطاة ، فيمكنه أن ينظر في${\displaystyle d+1}$قيم،${\displaystyle a_{0},\ldots ,a_{d}}$بالنسبة لـ a ، والتي تعطي عددًا محدودًا من الاحتمالات للزوج المرتب${\displaystyle (f(a_{0}),\ldots ,f(a_{d})).}$كل${\displaystyle f(a_{i})}$له عدد محدود من القواسم${\displaystyle b_{i,0},\ldots ,b_{i,k_{i}}}$وكل${\displaystyle (d+1)}$-tuple حيث${\displaystyle i^{\text{th}}}$المدخل هو قاسم لـ${\displaystyle f(a_{i})}$أي، مجموعة من الشكل${\displaystyle (b_{0,j_{1}},\ldots ,b_{d,j_{d}})}$، ينتج متعددة حدود فريدة من الدرجة على الأكثر${\displaystyle d}$والتي يمكن حسابها باستخدام الاستيفاء متعدد الحدود . ويمكن اختبار كل من هذه الحدود المتعددة الحدود لمعرفة ما إذا كانت عاملاً عن طريق القسمة متعددة الحدود . وبما أن عددها محدود${\displaystyle a_{i}}$وكل${\displaystyle f(a_{i})}$إذا كان للمتغير عدد محدود من القواسم، فإن عدد هذه القواسم يكون محدودًا أيضًا. لذا، فإن البحث الشامل يسمح بإيجاد جميع العوامل التي لا تتجاوز درجتها d .

على سبيل المثال، انظر

${\displaystyle f(x)=x^{5}+x^{4}+x^{2}+x+2}$.

إذا كان هذا كثير الحدود يحلل إلى Z ، فإن أحد عوامله على الأقل${\displaystyle p(x)}$يجب أن تكون من الدرجة الثانية أو أقل، لذلك${\displaystyle p(x)}$يتم تحديدها بشكل فريد من خلال ثلاث قيم . وبالتالي، نقوم بحساب ثلاث قيم.${\displaystyle f(0)=2}$،${\displaystyle f(1)=6}$و${\displaystyle f(-1)=2}$إذا كانت إحدى هذه القيم تساوي صفرًا، فلدينا عامل خطي. أما إذا كانت القيم غير صفرية، فيمكننا سرد التحليلات الممكنة لكل منها. الآن، لا يمكن تحليل العدد 2 إلا إلى عوامل خطية.

1×2، 2×1، (−1)×(−2)، أو (−2)×(−1).

لذلك، إذا وُجد عامل كثير الحدود من الدرجة الثانية، فلا بد أن يأخذ إحدى القيم التالية

p (0) = 1، 2، -1، أو -2

وينطبق الأمر نفسه على p (−1). هناك ثمانية تحليلات للعدد 6 (أربعة لكل من 1×6 و2×3)، مما يجعل المجموع 4×4×8 = 128 ثلاثية ممكنة ( p (0)، p (1)، p (−1))، يمكن استبعاد نصفها باعتبارها معكوسات النصف الآخر. وبالتالي، يجب علينا التحقق من 64 متعددة حدود صحيحة صريحة.${\displaystyle p(x)=ax^{2}+bx+c}$كعوامل محتملة لـ${\displaystyle f(x)}$. يكشف اختبارها بشكل شامل أن

${\displaystyle p(x)=x^{2}+x+1}$

تم تكوينها من العوامل ( g (0)، g (1)، g (-1)) = (1، 3، 1)${\displaystyle f(x)}$.

قسمة f ( x ) على p ( x ) تعطي العامل الآخر${\displaystyle q(x)=x^{3}-x+2}$، لهذا السبب${\displaystyle f(x)=p(x)q(x)}$يمكن الآن إجراء اختبار تكراري لإيجاد عوامل p ( x ) و q ( x )، باستخدام اختبار الجذر النسبي في هذه الحالة. يتضح أن كليهما غير قابل للاختزال، لذا فإن التحليل غير القابل للاختزال لـ f ( x ) هو: ^{[ 5 ]}

${\displaystyle f(x)=p(x)q(x)=(x^{2}+x+1)(x^{3}-x+2).}$

لو${\displaystyle f(x)}$إذا كانت دالة متعددة الحدود أحادية المتغير على الأعداد الصحيحة، مفترضة أنها خالية من المحتوى وخالية من المربعات ، يبدأ المرء بحساب حد.${\displaystyle B}$بحيث يكون أي عامل${\displaystyle g(x)}$لها معاملات قيمة مطلقة محدودة بـ${\displaystyle B}$بهذه الطريقة، إذا${\displaystyle m}$هو عدد صحيح أكبر من${\displaystyle 2B}$وإذا${\displaystyle g(x)}$معروف بـ modulo${\displaystyle m}$، ثم${\displaystyle g(x)}$يمكن إعادة بنائها من تعديل صورتها${\displaystyle m}$.

تتم خوارزمية زاسنهاوس على النحو التالي. أولاً، اختر عددًا أوليًا${\displaystyle p}$بحيث تكون صورة${\displaystyle f(x){\bmod {p}}}$يبقى خالياً من المربعات ، وبنفس درجة${\displaystyle f(x)}$إن الاختيار العشوائي سيحقق هذه القيود في أغلب الأحيان، لأن عددًا محدودًا فقط من الأعداد الأولية لا يحققها، وهي القواسم الأولية لحاصل ضرب المميز والمعامل الرئيسي لكثير الحدود. ثم حلل${\displaystyle f(x){\bmod {p}}}$ينتج عن ذلك كثيرات حدود عددية صحيحة${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$المنتج الذي يتطابق${\displaystyle f(x){\bmod {p}}}$بعد ذلك، قم بتطبيق رفع هينسل ؛ هذا يُحدّث${\displaystyle f_{i}(x)}$بطريقة تجعل منتجهم متطابقًا${\displaystyle f(x){\bmod {p}}^{a}}$، أين${\displaystyle a}$كبيرة بما يكفي بحيث${\displaystyle p^{a}}$يتجاوز${\displaystyle 2B}$وهكذا كل${\displaystyle f_{i}(x)}$يتوافق مع متعددة حدود عددية صحيحة محددة جيدًا. باقي القسمة${\displaystyle p^{a}}$، متعددة الحدود${\displaystyle f(x)}$لديه${\displaystyle 2^{r}}$العوامل (حتى الوحدة): نواتج جميع المجموعات الجزئية من${\displaystyle \{f_{1}(x),\ldots ,f_{r}(x)\}{\bmod {p}}^{a}}$هذه العوامل modulo${\displaystyle p^{a}}$لا يشترط أن تتطابق مع العوامل "الحقيقية" لـ${\displaystyle f(x)}$في${\displaystyle \mathbb {Z} [x]}$لكن يمكننا اختبارها بسهولة عن طريق القسمة على${\displaystyle \mathbb {Z} [x]}$وبهذه الطريقة، يمكن إيجاد جميع العوامل الحقيقية غير القابلة للاختزال عن طريق التحقق من عدد لا يتجاوز${\displaystyle 2^{r}}$الحالات، انخفضت إلى${\displaystyle 2^{r-1}}$في الحالات التي يتم فيها تخطي المكملات. إذا${\displaystyle f(x)}$إذا كان بالإمكان تقليلها، فإن عدد الحالات ينخفض ​​أكثر بإزالة تلك${\displaystyle f_{i}(x)}$التي تظهر في عامل صحيح تم العثور عليه مسبقًا. تعالج خوارزمية زاسنهاوس كل حالة (كل مجموعة فرعية) بسرعة، ولكن في أسوأ الحالات، فإنها تأخذ في الاعتبار عددًا هائلاً من الحالات.

تم اكتشاف أول خوارزمية زمنية متعددة الحدود لتحليل كثيرات الحدود النسبية بواسطة لينسترا، لينسترا ولوفاس، وهي تطبيق لخوارزمية لينسترا-لينسترا-لوفاس لتقليل أساس الشبكة (LLL). ^{[ 6 ]}

فيما يلي نسخة مبسطة من خوارزمية تحليل LLL: حساب الجذر المركب (أو الجذر p -adic) α لكثير الحدود${\displaystyle f(x)}$للحصول على دقة عالية، استخدم خوارزمية تقليل أساس الشبكة Lenstra–Lenstra – Lovász لإيجاد علاقة خطية تقريبية بين 1، α ، α2 ^، α3 ^، ... بمعاملات صحيحة، والتي قد تكون علاقة خطية دقيقة وعاملًا متعدد الحدود لـ${\displaystyle f(x)}$يمكن تحديد حدٍّ للدقة يضمن أن هذه الطريقة تُنتج إما عاملًا أو برهانًا على عدم الاختزال. مع أن هذه الطريقة تُنجز في وقت متعدد الحدود، إلا أنها لا تُستخدم عمليًا لأن الشبكة ذات أبعاد عالية وعدد هائل من المدخلات، مما يُبطئ الحساب.

ينبع التعقيد الأسي في خوارزمية زاسنهاوس من مشكلة توافقية: كيفية اختيار المجموعات الفرعية الصحيحة من${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$تعمل أحدث تطبيقات التحليل إلى عوامل بطريقة مشابهة لطريقة زاسنهاوس، باستثناء أن المسألة التوافقية تُحوّل إلى مسألة شبكية تُحل بعد ذلك باستخدام خوارزمية LLL. ^{[ 7 ]} في هذا النهج، لا تُستخدم خوارزمية LLL لحساب معاملات العوامل، بل لحساب المتجهات ذات${\displaystyle r}$المدخلات في {0,1} التي ترمز إلى المجموعات الفرعية من${\displaystyle f_{1}(x),\ldots ,f_{r}(x)}$بما يتوافق مع العوامل الحقيقية غير القابلة للاختزال.

يمكننا تحليل كثير الحدود${\displaystyle p(x)\in K[x]}$، حيث الحقل${\displaystyle K}$هو امتداد محدود لـ${\displaystyle \mathbb {Q} }$أولًا، باستخدام تحليل العوامل الخالية من المربعات ، يمكننا افتراض أن متعددة الحدود خالية من المربعات. بعد ذلك، نُعرّف حلقة القسمة.${\displaystyle L=K[x]/p(x)}$درجة علمية${\displaystyle n=[L:\mathbb {Q} ]=\deg p(x)\,[K:\mathbb {Q} ]}$هذا ليس حقلاً إلا إذا${\displaystyle p(x)}$غير قابلة للاختزال، لكنها حلقة مختزلة لأن${\displaystyle p(x)}$خالٍ من المربعات. في الواقع، إذا

${\displaystyle p(x)=\prod _{i=1}^{m}p_{i}(x)}$

إذا كان التحليل المطلوب لـ p ( x )، فإن الحلقة تتحلل بشكل فريد إلى حقول كما يلي:

${\displaystyle L=K[x]/p(x)\cong \prod _{i=1}^{m}K[x]/p_{i}(x).}$

سنجد هذا التفكيك دون معرفة التحليل إلى عوامل. أولاً، نكتب L صراحةً كجبر على${\displaystyle \mathbb {Q} }$نختار عنصرًا عشوائيًا${\displaystyle \alpha \in L}$، مما ينتج${\displaystyle L}$زيادة${\displaystyle \mathbb {Q} }$باحتمالية عالية وفقًا لنظرية العنصر الأولي . إذا كان هذا هو الحال، فيمكننا حساب متعددة الحدود الدنيا${\displaystyle q(y)\in \mathbb {Q} [y]}$ل${\displaystyle \alpha }$زيادة${\displaystyle \mathbb {Q} }$، من خلال إيجاد${\displaystyle \mathbb {Q} }$العلاقة الخطية بين 1، α ، ...، αₙ ^. باستخدام خوارزمية تحليل كثيرات الحدود النسبية، نقوم بتحليلها إلى عناصر غير قابلة للاختزال في${\displaystyle \mathbb {Q} [y]}$:

${\displaystyle q(y)=\prod _{i=1}^{n}q_{i}(y).}$

وهكذا لدينا:

${\displaystyle L\cong \mathbb {Q} [y]/q(y)\cong \prod _{i=1}^{n}\mathbb {Q} [y]/q_{i}(y),}$

أين${\displaystyle \alpha }$يتوافق مع${\displaystyle y\leftrightarrow (y,y,\ldots ,y)}$يجب أن يكون هذا متماثلاً مع التفكيك السابق لـ${\displaystyle L}$.

مولدات L هي x بالإضافة إلى مولدات${\displaystyle K}$زيادة${\displaystyle \mathbb {Q} }$كتابة هذه على شكل كثيرات حدود في${\displaystyle \alpha }$، يمكننا تحديد تضمينات${\displaystyle x}$و${\displaystyle K}$في كل مكون${\displaystyle \mathbb {Q} [y]/q_{i}(y)=K[x]/p_{i}(x)}$من خلال إيجاد متعددة الحدود الدنيا لـ${\displaystyle x}$في${\displaystyle \mathbb {Q} [y]/q_{i}(y)}$، نقوم بالحساب${\displaystyle p_{i}(x)}$وبالتالي عامل${\displaystyle p(x)}$زيادة${\displaystyle K.}$

بشكل عام، لا تحتوي معظم كثيرات الحدود على جذور تربيعية. مع ذلك، تستخدم بعض التطبيقات، مثل وظيفة مهندسي الكهرباء في الحصول على معاملات Y من معاوقة نقطة القيادة لشبكة ثنائية المنافذ ^{[ 8 ]} ، كثيرات حدود تربيعية يجب تحليلها إلى كثيرتي حدود متطابقتين بجذر تربيعي. ستقوم الخوارزمية أدناه بتحليل كثيرة حدود تربيعية.${\displaystyle {\sqrt {x^{6}-6x^{5}+17x^{4}-36x^{3}+52x^{2}+48x+36}}}$، إلى جذرين متطابقين لكثير الحدود،${\displaystyle R=X^{3}-3x^{2}+4x-6}$، باستخدام مثال من موقع Mathematics Stack Exchange . ^{[ 9 ] [ 10 ]}

${\displaystyle {\begin{aligned}&{\begin{array}{|l|l|l|}\hline Q&R&R(2Q+R)\\\hline \\0&x^{3}&x^{6}\\\hline \\x^{3}&-3x^{2}&6x^{5}-9x^{4}\\\hline \\x^{3}-3x^{2}&4x&8x^{4}-24x^{3}+16x^{2}\\\hline \\x^{3}-3x^{2}+4x&-6&-12x^{3}+36x^{2}-48x+36\\\hline \end{array}}&{\begin{array}{|c|c|c|c|c|c|c|c|}\hline R&x^{3}&&-3x^{2}&&4x&&-6\\\hline 1&x^{6}&-6x^{5}&17x^{4}&-36x^{3}&52x^{2}&48x&36\\&x^{6}&&&&&&\\\hline 2&&-6x^{5}&17x^{4}&&&&\\&&-6x^{5}&9x^{4}&&&&\\\hline 3&&&8x^{4}&-36x^{3}&52x^{2}&&\\&&&8x^{4}&-24x^{3}&16x^{2}&&\\\hline 4&&&&-12x^{3}&36x^{2}&-48x&36\\&&&&-12x^{3}&36x^{2}&-48x&36\\\hline \end{array}}\end{aligned}}}$

خطوات:

الخطوة الأولى: احسب الجذر التربيعي للحد الرئيسي،${\displaystyle x^{6}}$ثم ضعه في مكانه.${\displaystyle x^{3}}$، في الحد الرئيسي لحل متعدد الحدود R، صف الحل في الأعلى، وضع${\displaystyle x^{6}}$الحد الموجود في الصف 1 أسفل كثير الحدود المراد تحليله، كما هو موضح.

الخطوة الثانية: اطرح ما تم وضعه حديثًا${\displaystyle x^{6}}$من كثير الحدود المراد تحليله، قم بإسقاط الحدين التاليين إلى الصف الثاني.

الخطوة 3 : ضاعف الحالة الحالية لكثير الحدود R، ثم أضف حدًا جديدًا، Q، بحيث ينفي R(2Q+R) الحد الرئيسي للصف 2، وضع معكوس R(2Q+R) في المساحة السفلية للصف 2.

الخطوة الرابعة: اطرح العددين في الصف 2، وضع النتائج في الصف 3، وانقل الحدين التاليين من الصف 1 إلى الصف 3.

الخطوة 5: كرر ذلك لجميع الصفوف والأعمدة المتبقية حتى الانتهاء.

عند اكتمال الحل، ستظهر متعددة الحدود R في العمود R في الجدول الجانبي الأيسر وفي الصف R من الجدول الجانبي الأيمن.