طريقة ديكسون للتحليل إلى عوامل

في نظرية الأعداد ، تُعدّ طريقة ديكسون للتحليل إلى عوامل (وتُعرف أيضًا بطريقة ديكسون للمربعات العشوائية ^{[ 1 ]} أو خوارزمية ديكسون ) خوارزمية عامة لتحليل الأعداد الصحيحة إلى عواملها الأولية ؛ وهي النموذج الأمثل لطريقة التحليل القائمة على العوامل . وعلى عكس طرق التحليل القائمة على العوامل الأخرى، فإنّ حدّ زمن تشغيلها يأتي مصحوبًا ببرهان دقيق لا يعتمد على تخمينات حول خصائص سلاسة القيم التي تأخذها متعددة الحدود.

تم تصميم الخوارزمية بواسطة جون د. ديكسون ، وهو عالم رياضيات في جامعة كارلتون ، ونُشرت في عام 1981. ^{[ 2 ]}

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

تجد طريقة فيرما للتحليل إلى عوامل مثل هذا التطابق عن طريق اختيار قيم x عشوائية أو شبه عشوائية ، على أمل أن يكون العدد الصحيح x² ^mod N مربعًا كاملاً غير تافه (في الأعداد الصحيحة):  

${\displaystyle x^{2}\equiv y^{2}\quad ({\hbox{mod }}N),\qquad x\not \equiv \pm y\quad ({\hbox{mod }}N).}$

على سبيل المثال، إذا كان N = 84923 ، (بالبدء من 292، وهو أول عدد أكبر من جذر N، والعد تصاعديًا) فإن 505² mod 84923 ^هو 256، وهو مربع العدد 16. إذن (505 - 16)(505 + 16) = 0 mod 84923. بحساب القاسم المشترك الأكبر لـ 505 - 16 و N باستخدام خوارزمية إقليدس، نحصل على 163 ، وهو أحد عوامل N.

من الناحية العملية، سيستغرق اختيار قيم x عشوائية وقتًا طويلاً بشكل غير عملي للعثور على تطابق المربعات، نظرًا لوجود √N مربعًا أقل من N فقط .

تستبدل طريقة ديكسون الشرط "مربع كامل غير تافه" بالشرط الأضعف بكثير "له عوامل أولية صغيرة فقط"؛ على سبيل المثال، هناك 292 مربعًا أصغر من 84923؛ و662 عددًا أصغر من 84923 عواملها الأولية هي 2 أو 3 أو 5 أو 7 فقط؛ و4767 عددًا عواملها الأولية جميعها أقل من 30. (تسمى هذه الأعداد 7-smooth و30-smooth، على التوالي، لأنها B-smooth بالنسبة إلى حد ما B. )

بمجرد العثور على عدد كافٍ من هذه القيم السلسة من النوع B ، يمكن استخدام الجبر الخطي للبحث عن مربعات كاملة غير تافهة لطريقة فيرما للتحليل إلى عوامل. إذا كان هناك العديد من الأعداد${\displaystyle a_{1}\ldots a_{n}}$والتي يمكن تحليل مربعاتها إلى عواملها الأولية كما يلي:${\displaystyle a_{i}^{2}\mod N=\prod _{j=1}^{m}b_{j}^{e_{ij}}}$لمجموعة ثابتة${\displaystyle b_{1}\ldots b_{m}}$من الأعداد الأولية الصغيرة، الجبر الخطي modulo 2 على المصفوفة${\displaystyle e_{ij}}$سيعطي مجموعة فرعية من${\displaystyle a_{i}}$التي تتحد مربعاتها لتشكل ناتج ضرب أعداد أولية صغيرة مرفوعة إلى قوة زوجية - أي مجموعة جزئية من${\displaystyle a_{i}}$والتي تضرب مربعاتها في مربع عدد (نأمل أن يكون مختلفًا) mod N.

لنفترض أننا نحلل العدد المركب N إلى عوامله الأولية. نختار الحد B ، ونحدد أساس العوامل (الذي يُسمى P )، وهو مجموعة جميع الأعداد الأولية الأصغر من أو تساوي B. بعد ذلك، نبحث عن أعداد صحيحة موجبة z بحيث يكون z² ^mod N  دالة سلسة بالنسبة إلى B. لذلك ، يمكننا كتابة المعادلة التالية، لأسس مناسبة aᵢ _: 

${\displaystyle z^{2}{\text{ mod }}N=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$

عندما يتم توليد عدد كافٍ من هذه العلاقات (يكفي عمومًا أن يكون عدد العلاقات أكبر بقليل من حجم P )، يمكن استخدام طرق الجبر الخطي ، مثل طريقة الحذف الغاوسي ، لضرب هذه العلاقات المختلفة معًا بطريقة تجعل أسس الأعداد الأولية على الجانب الأيمن جميعها زوجية:

${\displaystyle {z_{1}^{2}z_{2}^{2}\cdots z_{k}^{2}\equiv \prod _{p_{i}\in P}p_{i}^{a_{i,1}+a_{i,2}+\cdots +a_{i,k}}\ {\pmod {N}}\quad ({\text{حيث ​​}}a_{i,1}+a_{i,2}+\cdots +a_{i,k}\equiv 0{\pmod {2}})}}$

ينتج عن ذلك تطابق مربعات على الصورة a² ≡ ^b² (mod N )، والذي يمكن تحويله إلى تحليل للمتغير N ، حيث N = gcd ( a + b , N ⁾ × ( N /gcd( a + b , N )). قد يكون هذا التحليل بسيطًا (أي N = N × 1 )، وهو ما لا يحدث إلا إذا كان a ≡ ± b (mod N )، وفي هذه الحالة يجب إجراء محاولة أخرى باستخدام مجموعة مختلفة من العلاقات؛ ولكن إذا تم التوصل إلى زوج غير بسيط من عوامل N ، فإن الخوارزمية تتوقف.

هذا القسم مأخوذ مباشرة من ديكسون (1981).

خوارزمية ديكسون

التهيئة. ليكن L قائمة من الأعداد الصحيحة في النطاق [1، n ]، وليكن P = { p1 _, ..., ph _} قائمة الأعداد الأولية h ≤ v . وليكن B و Z قائمتين فارغتين في البداية ( سيتم فهرسة Z بواسطة B ).

الخطوة 1. إذا كانت L فارغة، فاخرج (فشلت الخوارزمية). وإلا، فخذ الحد الأول z من L ، واحذفه من L ، ثم انتقل إلى الخطوة 2.

الخطوة 2. احسب w كأصغر باقي موجب لـ z² ^mod n . حلل w إلى:

${\displaystyle w=w'\prod _{i}p_{i}^{a_{i}}}$

حيث لا يوجد عامل لـ w ′ في P. إذا كانت w ′ = 1، فانتقل إلى الخطوة 3؛ وإلا، فارجع إلى الخطوة 1.

الخطوة 3. ليكن a ← ( a ₁ , ..., a _h ). أضف a إلى B و z إلى Z. إذا كان B يحتوي على h عنصر على الأكثر ، فارجع إلى الخطوة 1؛ وإلا، فانتقل إلى الخطوة 4.

الخطوة 4. أوجد أول متجه c في B يكون تابعًا خطيًا (mod 2) على المتجهات السابقة في B. ثم احذف c من B و${\displaystyle z_{c}}$من Z. احسب المعاملات${\displaystyle f_{b}}$بحيث:

${\displaystyle \mathbf {c} \equiv \sum _{b\in B}f_{b}\mathbf {b} {\pmod {2}}}$

يُعرِّف:

${\displaystyle \mathbf {d} =(d_{1},\dots ,d_{n})\gets {\frac {1}{2}}\left(\mathbf {c} +\sum f_{b}\mathbf {b} \right)}$

انتقل إلى الخطوة 5.

الخطوة 5. الحساب:

${\displaystyle x\gets z_{c}\prod _{b}z_{b}^{f_{b}},\quad y\gets \prod _{i}p_{i}^{d_{i}}}$

لهذا السبب:

${\displaystyle x^{2}\equiv \prod _{i}p_{i}^{2d_{i}}=y^{2}\mod n.}$

لو${\displaystyle x\equiv y}$أو${\displaystyle x\equiv -y{\pmod {n}}}$، ارجع إلى الخطوة 1. وإلا، فارجع:

${\displaystyle \gcd(n,x+y)}$

مما يوفر عاملاً غير تافه لـ n ، وينتهي بنجاح.

في هذا المثال، نحلل العدد ( ن = ٨٤٩٢٣) باستخدام خوارزمية ديكسون. هذا المثال مقتبس بتصرف من مجموعة LeetArxiv الفرعية. ^{[ ٣ ]} يُنسب الفضل إلى المؤلف الأصلي.

• التهيئة :
  • حدد قائمة من الأرقام L ، تتراوح من 1 إلى 84923:

${\displaystyle L=\{1,\dots ,84923\}}$

• حدد قيمة v ، وهي عامل النعومة:

${\displaystyle v=7}$

• عرّف قائمة P تحتوي على جميع الأعداد الأولية الأقل من أو تساوي v :

${\displaystyle P={2,3,5,7}}$

• عرّف B و Z ، وهما قائمتان فارغتان. B هي قائمة قوى الأعداد، بينما Z هي قائمة الأعداد الصحيحة المقبولة:

${\displaystyle B=[]}$

${\displaystyle Z=[]}$

• الخطوة 1 : التكرار${\displaystyle z}$قيم
  • ابدأ حلقة تكرارية تقوم بفهرسة القائمة${\displaystyle L}$العنصر الحالي في${\displaystyle L}$يُصنف على أنه${\displaystyle z}$. تنتهي حلقة for عند نهاية القائمة، أو عندما تكسر الخطوة 5 الحلقة.

int n = 84923 ; for ( int i = 1 ; i <= n ; i ++ ) { int z = i ; // الخطوات المتبقية هنا. // الخطوة 4 قد تُفعّل الخطوة 5. // الخطوة 5 قد تُنهي الحلقة. }

• الخطوة الثانية : الحوسبة${\displaystyle z^{2}\mod n}$والتحليل إلى عوامل أولية سلسة
  • للمتابعة، احسب${\displaystyle z^{2}\mod 84923}$لكل قيمة من قيم z ، ثم قم بالتعبير عن النتيجة كتحليل إلى عوامل أولية.

${\displaystyle 1^{2}\mod 84923\equiv 1\mod 84923=2^{0}\cdot 3^{0}\cdot 5^{0}\cdot 7^{0}\mod 84923}$

${\displaystyle \vdots }$

${\displaystyle 513^{2}\mod 84923=8400\mod 84923=2^{4}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1}\mod 84923}$

${\displaystyle \vdots }$

${\displaystyle 537^{2}\mod 84923=33600\mod 84923=2^{6}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1}\mod 84923}$

${\displaystyle 538^{2}\mod 84923=34675\mod 84923=5^{2}\cdot 19^{1}\cdot 73^{1}\mod 84923}$

تستمر هذه الخطوة لجميع قيم z في النطاق.

• الخطوة 3 : إلحاق نتائج التنعيم الرأسي
  • لو${\displaystyle z^{2}\mod 84923}$إذا كان سلسًا بسبع درجات، فأضف قدراته إلى القائمة${\displaystyle B}$وألحق${\displaystyle z}$لإدراج${\displaystyle Z}$.
  • لو${\displaystyle B}$لديه على الأكثر${\displaystyle h=4}$إذا كانت العناصر غير موجودة، فارجع إلى الخطوة 1. وإلا، فانتقل إلى الخطوة 4.
  • على سبيل المثال، بعد 537 تكرارًا، نحصل على:

${\displaystyle Z=\{1,\ldots ,513,537\}}$

${\displaystyle B=\{[0,0,0,0],\ldots ,[4,1,2,1],[6,1,2,1]\}}$

وننتقل إلى الخطوة الرابعة حيث سيكون لدينا أكثر من${\displaystyle h=4}$المتجهات في${\displaystyle B}$.

• الخطوة الرابعة : تنقسم هذه الخطوة إلى جزأين.
  • الجزء الأول : العثور${\displaystyle B}$modulo 2

${\displaystyle B={\begin{pmatrix}0&0&0&0\\4&1&2&1\\6&1&2&1\end{pmatrix}}\mod 2\equiv B={\begin{pmatrix}0&0&0&0\\0&1&0&1\\0&1&0&1\end{pmatrix}}}$

• الجزء الثاني : إيجاد توليفة صفوف من${\displaystyle B}$مجموعها أعداد زوجية

على سبيل المثال، جمع الصف${\displaystyle 2}$والصف${\displaystyle 3}$يعطينا متجهًا من الأعداد الزوجية.

${\displaystyle R_{2}=\{0,1,0,1\}}$و${\displaystyle R_{3}=\{0,1,0,1\}}$

ثم

${\displaystyle R_{2}+R_{3}=\{0,1,0,1\}+\{0,1,0,1\}}$

${\displaystyle R_{2}+R_{3}=\{0,2,0,2\}}$.

• الخطوة 5 : تنقسم هذه الخطوة إلى أربعة أجزاء.
  • الجزء الأول : حساب x
    • اضرب المقابل${\displaystyle z}$قيم الصفوف التي تم العثور عليها في الخطوة 4 ، mod${\displaystyle n}$للحصول على${\displaystyle x}$.

الصفان 2 و3 يتطابقان مع 513 و537، لذلك${\displaystyle x=(513\cdot 537)=20712\mod 84923}$

• الجزء الثاني : الحوسبة${\displaystyle y}$

• أضف الصفوف الموجودة في الخطوة 4 .
• اقسم على 2. (بما أن هذه تمثل أسسًا، فإن هذا يأخذ الجذر التربيعي فعليًا.)
• تُطبق كأسس على الأعداد الأولية في${\displaystyle P}$للحصول على${\displaystyle y}$.
• ارجع إلى الخطوة 1 إذا${\displaystyle x=\pm y}$.

أوجد نصف مجموع الصفين 2 و 3:

${\displaystyle {\begin{array}{ccccc}&4&1&2&1\\+&6&1&2&1\\\hline &10&2&4&2\\\div 2\\\hline &5&1&2&1\end{array}}}$

قم بتطبيقها كأسس لـ${\displaystyle P=\{2,3,5,7\}}$:

${\displaystyle y=2^{5}\cdot 3^{1}\cdot 5^{2}\cdot 7^{1}=16800}$

• منذ${\displaystyle x\neq \pm y}$ننتقل الآن إلى الجزء الثالث .

• الجزء الثالث : الحوسبة${\displaystyle x+y}$و${\displaystyle x-y}$أين${\displaystyle x=20712}$و${\displaystyle y=16800}$

${\displaystyle x+y=20712+16800=37512}$

${\displaystyle x-y=20712-16800=3912}$

• الجزء الرابع : الحوسبة${\displaystyle \gcd(x+y,n)}$و${\displaystyle \gcd(x-y,n)}$أين${\displaystyle n=84923}$،${\displaystyle x+y=292281}$و${\displaystyle x-y=258681}$

${\displaystyle {\begin{array}{ll}\gcd(37512,84923)=521\\\gcd(3912,84923)=163\end{array}}}$

يُظهر فحص سريع${\displaystyle 84923=521\cdot 163}$.

تشير الشفرة الزائفة إلى أنه يجب حساب فقط${\displaystyle x+y}$والعودة${\displaystyle \gcd(x+y,n)}$وذلك لأنه أسرع في حساب القاسم المشترك الأكبر، وبمجرد الحصول عليه، يصبح القسمة أسهل.${\displaystyle n}$والنتيجة أسرع من الحساب${\displaystyle \gcd(x-y,n)}$.

المنخل التربيعي هو تحسين لطريقة ديكسون. يختار قيم x قريبة من الجذر التربيعي لـ N بحيث يكون x² ^modulo N صغيرًا، مما يزيد بشكل كبير من فرصة الحصول على عدد سلس.

تشمل الطرق الأخرى لتحسين طريقة ديكسون استخدام خوارزمية أفضل لحل معادلة المصفوفة، والاستفادة من خاصية التباعد في المصفوفة: لا يمكن أن يتجاوز عدد عناصر المصفوفة z حدًا معينًا.${\displaystyle \log _{2}z}$العوامل، لذا فإن كل صف من المصفوفة يتكون تقريبًا من أصفار. عمليًا، تُستخدم خوارزمية لانكزوس الكتلية غالبًا. كما يجب اختيار حجم قاعدة العوامل بعناية: فإذا كان صغيرًا جدًا، سيصعب إيجاد أعداد قابلة للتحليل الكامل إليها، وإذا كان كبيرًا جدًا، فسيتعين جمع المزيد من العلاقات.

تحليل أكثر تعقيدًا، باستخدام التقريب القائل بأن جميع العوامل الأولية للعدد أقل من${\displaystyle N^{1/a}}$باحتمالية حوالي${\displaystyle a^{-a}}$(تقريب لدالة ديكمان-دي بروين )، يشير إلى أن اختيار قاعدة عوامل صغيرة جدًا أسوأ بكثير من اختيار قاعدة عوامل كبيرة جدًا، وأن حجم قاعدة العوامل المثالي هو قوة ما من${\displaystyle \exp \left({\sqrt {\log N\log \log N}}\right)}$.

التعقيد الأمثل لطريقة ديكسون هو

${\displaystyle O\left(\exp \left(2{\sqrt {2}}{\sqrt {\log n\log \log n}}\right)\right)}$

باستخدام ترميز Big-O ، أو

${\displaystyle L_{n}[1/2,2{\sqrt {2}}]}$

في تدوين L.