تقليل الشبكة

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

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

أحد مقاييس شبه التعامد هو عيب التعامد . يقارن هذا المقياس حاصل ضرب أطوال متجهات الأساس بحجم متوازي السطوح الذي تحدده. بالنسبة لمتجهات الأساس المتعامدة تمامًا، تكون هاتان الكميتان متساويتين.

أي أساس محدد لـ${\displaystyle n}$يمكن تمثيل المتجهات بواسطة مصفوفة${\displaystyle B}$، والتي تمثل أعمدتها متجهات الأساس${\displaystyle b_{i},i=1,\ldots ,n}$في الحالة ذات الأبعاد الكاملة حيث يساوي عدد متجهات الأساس بُعد الفضاء الذي تشغله، تكون هذه المصفوفة مربعة، وحجم متوازي المستطيلات الأساسي هو ببساطة القيمة المطلقة لمحدد هذه المصفوفة.${\displaystyle \det(B)}$إذا كان عدد المتجهات أقل من بُعد الفضاء الأساسي، فإن الحجم يكون${\displaystyle {\sqrt {\det(B^{T}B)}}}$بالنسبة لشبكة معينة${\displaystyle \Lambda }$، هذا الحجم هو نفسه (حتى الإشارة) لأي أساس، ومن ثم يُشار إليه باسم محدد الشبكة${\displaystyle \det(\Lambda )}$أو ثابت الشبكة${\displaystyle d(\Lambda )}$.

عيب التعامد هو حاصل ضرب أطوال متجهات الأساس مقسومة على حجم متوازي المستطيلات؛

${\displaystyle \delta (B)={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{\sqrt {\det(B^{T}B)}}}={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{d(\Lambda )}}}$

من التعريف الهندسي يمكن إدراك أن${\displaystyle \delta (B)\geq 1}$مع المساواة إذا وفقط إذا كانت القاعدة متعامدة.

إذا عُرِّفت مسألة اختزال الشبكة بأنها إيجاد الأساس ذي أصغر عيب ممكن، فإن المسألة تُصنَّف ضمن مسائل NP-complete . ^{[ 1 ]} ومع ذلك، توجد خوارزميات ذات زمن متعدد الحدود لإيجاد أساس ذي عيب.${\displaystyle \delta (B)\leq c}$ حيث c ثابت يعتمد فقط على عدد متجهات الأساس وبُعد الفضاء الأساسي (إن كان مختلفًا). ^{[ 2 ] [ 1 ]} يُعد هذا حلاً جيدًا بما يكفي في العديد من التطبيقات العملية، مثل تحليل كثيرات الحدود ^{[ 2 ].}

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

الشفرة الزائفة للخوارزمية، والمعروفة غالبًا باسم خوارزمية لاغرانج أو خوارزمية لاغرانج-غاوس، هي كما يلي:

 مدخل:${\textstyle (u,v)}$أساس للشبكة${\textstyle L}$افترض أن${\textstyle ||v||\leq ||u||}$وإلا فقم بتبديلها. الناتج: أساس${\textstyle (u,v)}$مع${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$.

 بينما${\textstyle ||v||<||u||}$: ${\textstyle q:=\left\lfloor {\left\langle u,{\dfrac {v}{||v||^{2}}}\right\rangle }\right\rceil }$قرّب إلى أقرب عدد صحيح ${\textstyle r:=u-qv}$${\textstyle u:=v}$${\textstyle v:=r}$

انظر إلى القسم الخاص بخوارزمية لاغرانج في ^{[ 3 ]} لمزيد من التفاصيل.

تُستخدم خوارزميات اختزال الشبكة في عدد من التطبيقات الحديثة لنظرية الأعداد، بما في ذلك اكتشاف خوارزمية الصنبور لـ${\displaystyle \pi }$على الرغم من أن تحديد أقصر أساس قد يكون مسألةً معقدةً من نوع NP-complete، إلا أن خوارزميات مثل خوارزمية LLL ^{[ 2 ]} قادرة على إيجاد أساس قصير (ليس بالضرورة الأقصر) في وقت متعدد الحدود مع ضمان أداء ممتاز في أسوأ الحالات. تُستخدم خوارزمية LLL على نطاق واسع في تحليل أنظمة التشفير بالمفتاح العام .

عند استخدامها لإيجاد العلاقات بين الأعداد الصحيحة، يتكون المدخل النموذجي للخوارزمية من مجموعة موسعة${\displaystyle n\times n}$مصفوفة الوحدة التي تتكون عناصر عمودها الأخير من${\displaystyle n}$العناصر (مضروبة في ثابت موجب كبير)${\displaystyle w}$(لمعاقبة المتجهات التي لا يساوي مجموعها صفرًا) والتي يتم البحث عن العلاقة بينها.

استُخدمت خوارزمية LLL لحساب أساس شبه متعامد لإظهار أنه يمكن تنفيذ البرمجة العددية في أي بُعد ثابت في وقت متعدد الحدود . ^{[ 4 ]}

تعمل الخوارزميات التالية على تقليل قواعد الشبكة؛ كما تم إدراج العديد من التطبيقات العامة لهذه الخوارزميات.