مشكلة الشبكة

الموسوعة الحرة

في علوم الحاسوب ، تُعدّ مسائل الشبكات فئةً من مسائل التحسين المرتبطة بكائنات رياضية تُسمى الشبكات . ويُشكّل التوقع بصعوبة حلّ هذه المسائل عنصرًا أساسيًا في بناء أنظمة تشفير آمنة قائمة على الشبكات : تُعدّ مسائل الشبكات مثالًا على مسائل NP-hard التي ثبت أنها صعبة في الحالة المتوسطة ، مما يُوفّر حالة اختبار لأمان خوارزميات التشفير. إضافةً إلى ذلك، يُمكن استخدام بعض مسائل الشبكات التي تُعدّ صعبة في أسوأ الحالات كأساس لأنظمة تشفير بالغة الأمان. إنّ استخدام صعوبة أسوأ الحالات في هذه الأنظمة يجعلها من بين الأنظمة القليلة جدًا التي يُرجّح أن تكون آمنة حتى ضدّ الحواسيب الكمومية . بالنسبة للتطبيقات في أنظمة التشفير هذه ، تُستخدم الشبكات على فضاءات المتجهات (غالبًاسؤالن{\displaystyle \mathbb {Q} ^{n}}) أو وحدات مجانية (غالباًZن{\displaystyle \mathbb {Z} ^{n}}تُعتبر هذه الأمور عموماً ذات أهمية.

بالنسبة لجميع المسائل أدناه، افترض أن لدينا (بالإضافة إلى مدخلات أخرى أكثر تحديدًا) أساسًا للفضاء المتجهي V ومعيارًا N. المعيار الذي يُعتمد عادةً هو المعيار الإقليدي L² . ومع ذلك، تُؤخذ معايير أخرى (مثل Lₚ ) في الاعتبار أيضًا وتظهر في مجموعة متنوعة من النتائج. [ 1 ]

خلال هذا المقال، دعوناλ(ل){\displaystyle \lambda (L)}يرمز إلى طول أقصر متجه غير صفري في الشبكة L : أي،

λ(ل)=مينv∈ل∖{0}‖v‖شمال.{\displaystyle \lambda (L)=\min _{v\in L\smallsetminus \{\mathbf {0} \}}\|v\|_{N}.}

مسألة أقصر متجه (SVP)

هذا توضيح لمسألة أقصر متجه (المتجهات الأساسية باللون الأزرق، وأقصر متجه باللون الأحمر).

في مسألة القيمة الحدية، تُعطى قاعدة فضاء متجهي V ومعيار N ( غالبًا L² ) لشبكة L ، ويجب إيجاد أقصر متجه غير صفري في V ، مقاسًا بالمعيار N ، في L. بعبارة أخرى، يجب أن تُخرج الخوارزمية متجهًا غير صفري v بحيث‖v‖شمال=λ(ل){\displaystyle \|v\|_{N}=\lambda (L)}⁠ . فيما يلي، يتم تحديد حجم المشكلة بواسطة n ، وهوبُعد الفضاء المتجهي V.

في نسخة التقريب γ، SVP γ ، يجب إيجاد متجه شبكي غير صفري بطول لا يتجاوزγ⋅λ(ل){\displaystyle \gamma \cdot \lambda (L)}بالنسبة لـ ⁠γ≥1{\displaystyle \gamma \geq 1}⁠ .

نتائج الصلابة

لا يُعرف أن الصيغة الدقيقة للمسألة هي مسألة صعبة الحل (NP-hard) إلا في حالة الاختزالات العشوائية. [ 2 ] [ 3 ] في المقابل، من المعروف أن المسألة المقابلة فيما يتعلق بالمعيار الموحد هي مسألة صعبة الحل (NP-hard ). [ 4 ]

خوارزميات المعيار الإقليدي

لحل النسخة الدقيقة من مسألة القيمة المكانية الصغيرة (SVP) وفقًا للمعيار الإقليدي، توجد عدة طرق مختلفة يمكن تقسيمها إلى فئتين: خوارزميات تتطلب وقتًا فائق الأسي (2ω(ن){\displaystyle 2^{\أوميغا (ن)}}) وبولي⁡(ن){\displaystyle \operatorname {poly} (n)}الذاكرة، والخوارزميات التي تتطلب وقتاً ومساحةً هائلين (2Θ(ن){\displaystyle 2^{\Theta (n)}}) في بُعد الشبكة. تشمل الفئة الأولى من الخوارزميات بشكل ملحوظ تعداد الشبكة [ 5 ] [ 6 ] [ 7 ] وتقليل أخذ العينات العشوائية، [ 8 ] [ 9 ] بينما تشمل الفئة الثانية غربلة الشبكة، [ 10 ] [ 11 ] [ 12 ] وحساب خلية فورونوي للشبكة، [ 13 ] [ 14 ] وأخذ عينات غاوسية منفصلة. [ 15 ] يبقى السؤال مفتوحًا حول ما إذا كانت هناك خوارزميات لحل مسألة القيمة المكانية البسيطة (SVP) بدقة تعمل في وقت أسي واحد (2يا(ن){\displaystyle 2^{O(n)}}) ويتطلب توسيع الذاكرة بشكل متعدد الحدود في بُعد الشبكة. [ 16 ]

لحل صيغة التقريب γ، SVP γ لـγ>1{\displaystyle \gamma >1}بالنسبة للمعيار الإقليدي، تعتمد أفضل الطرق المعروفة على استخدام اختزال أساس الشبكة . بالنسبة للقيم الكبيرةγ=2Ω(ن){\displaystyle \gamma =2^{\Omega (n)}}يمكن لخوارزمية لينسترا -لينسترا-لوفاس (LLL) إيجاد حل في وقت متعدد الحدود في بُعد الشبكة. بالنسبة للقيم الأصغرγ{\displaystyle \gamma }تُستخدم خوارزمية Block Korkine-Zolotarev (BKZ) [ 17 ] [ 18 ] [ 19 ] بشكل شائع، حيث يكون مُدخل الخوارزمية (حجم الكتلة)β{\displaystyle \beta }) يحدد التعقيد الزمني وجودة المخرجات: بالنسبة لعوامل التقريب الكبيرةγ{\displaystyle \gamma }حجم كتلة صغيرβ{\displaystyle \beta }يكفي ذلك، وتنتهي الخوارزمية بسرعة. بالنسبة للقيم الصغيرةγ{\displaystyle \gamma }أكبرβ{\displaystyle \beta }يلزم إيجاد متجهات شبكية قصيرة بما يكفي، ويستغرق الخوارزمية وقتًا أطول لإيجاد حل. تستخدم خوارزمية BKZ داخليًا خوارزمية SVP دقيقة كإجراء فرعي (تعمل في شبكات ذات بُعد لا يتجاوزβ{\displaystyle \beta })، ويرتبط تعقيدها الإجمالي ارتباطًا وثيقًا بتكاليف استدعاءات SVP هذه في البعد ⁠β{\displaystyle \beta }⁠ .

GapSVP

تتمثل مشكلة GapSVP β في التمييز بين حالات SVP التي يكون فيها طول أقصر متجه على الأكثر1{\displaystyle 1}أو أكبر منβ{\displaystyle \beta }، حيثβ{\displaystyle \beta }يمكن أن تكون دالة ثابتة لأبعاد الشبكةن{\displaystyle n}. بالنظر إلى أساس الشبكة، يجب على الخوارزمية أن تقرر ما إذا كانλ(ل)≤1{\displaystyle \lambda (L)\leq 1}أو​λ(ل)>β{\displaystyle \lambda (L)>\beta }. مثل مشاكل الوعود الأخرى ، يُسمح للخوارزمية بالخطأ في جميع الحالات الأخرى.

وهناك صيغة أخرى للمسألة وهي GapSVP ζ,γ لبعض الدوال ζ و γ. المدخل للخوارزمية هو أساسب{\displaystyle B}وعددد{\displaystyle d}من المؤكد أن جميع المتجهات في عملية التعامد لغرام-شميدت لا يقل طولها عن 1، وأنλ(ل(ب))≤ζ(ن){\displaystyle \lambda (L(B))\leq \zeta (n)}وذلك​1≤د≤ζ(ن)/γ(ن){\displaystyle 1\leq d\leq \zeta (n)/\gamma (n)}، حيثن{\displaystyle n}هو البُعد. يجب أن تقبل الخوارزمية إذا ⁠λ(ل(ب))≤د{\displaystyle \lambda (L(B))\leq d}، ورفض إذاλ(ل(ب))≥γ(ن)⋅د{\displaystyle \lambda (L(B))\geq \gamma (n)\cdot d}. للأحجام الكبيرةζ{\displaystyle \zeta }( أيζ(ن)>2ن/2{\displaystyle \zeta (n)>2^{n/2}}) ، تُعادل هذه المشكلة مشكلة GapSVP γ لأن [ 20 ] المعالجة المسبقة التي تتم باستخدام خوارزمية LLL تجعل الشرط الثاني (وبالتالي، ⁠ζ{\displaystyle \zeta }) زائد عن الحاجة.

مسألة أقرب متجه (CVP)

هذا توضيح لمسألة أقرب متجه (متجهات الأساس باللون الأزرق، والمتجه الخارجي باللون الأخضر، وأقرب متجه باللون الأحمر).

في مسألة القيم المترابطة (CVP ) ، تُعطى قاعدة فضاء متجهي V ومقياس M (غالبًا L² ) لشبكة L ، بالإضافة إلى متجه v في V ولكن ليس بالضرورة في L. والمطلوب هو إيجاد المتجه في L الأقرب إلى v (كما يُقاس بواسطة M ).γ{\displaystyle \gamma }في نسخة التقريب CVP γ ، يجب إيجاد متجه الشبكة على مسافة لا تتجاوزγ{\displaystyle \gamma }.

العلاقة مع نائب الرئيس الأول

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

يكون الاختزال من SVP γ إلى CVP γ كما يلي: لنفترض أن المدخل إلى SVP γ هو أساس الشبكةب=[ب1،ب2،...،بن]{\displaystyle B=[b_{1},b_{2},\ldots ,b_{n}]}ضع في اعتبارك الأساسبأنا=[ب1،...،2بأنا،...،بن]{\displaystyle B^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]}ودعxأنا{\displaystyle x_{i}}ليكن المتجه الذي تُرجعه دالة CVP γ ( B i , bi ) . ويُزعم أن أقصر متجه في المجموعة{xأنا-بأنا}{\displaystyle \{x_{i}-b_{i}\}}هو أقصر متجه في الشبكة المعطاة.

نتائج الصلابة

أظهر غولدريتش وآخرون أن أي صعوبة في SVP تستلزم نفس الصعوبة لـ CVP. [ 22 ] وباستخدام أدوات PCP ، أظهر أرورا وآخرون أن تقريب CVP ضمن عامل واحد أمر صعب.2سجل1-ϵ⁡(ن){\displaystyle 2^{\log ^{1-\epsilon }(n)}}إلا إذاNP⊆دي تايم⁡(2بولي⁡(سجل⁡ن)){\displaystyle \operatorname {NP} \subseteq \operatorname {DTIME} (2^{\operatorname {poly} (\log n)})}[ 23 ] عزز دينور وآخرون هذا الأمر من خلال تقديم نتيجة صعوبة NP معϵ=(سجل⁡سجل⁡ن)ج{\displaystyle \epsilon =(\log \log n)^{c}}لج<1/2{\displaystyle c<1/2}[ 24 ]​

فك تشفير المجال

استُخدمت خوارزميات حل مشكلة القيمة الحدية (CVP)، وخاصةً خوارزمية فينكه وبوست [ 6 ] ، للكشف عن البيانات في أنظمة الاتصالات اللاسلكية متعددة المدخلات والمخرجات ( MIMO ) (للإشارات المشفرة وغير المشفرة). [ 25 ] [ 13 ] وفي هذا السياق، يُطلق عليها اسم فك تشفير الكرة نظرًا لنصف القطر المستخدم داخليًا في العديد من حلول CVP. [ 26 ]

حل غموض الأعداد الصحيحة في نظام الملاحة العالمي عبر الأقمار الصناعية (GNSS) ذي الطور الحامل

تم تطبيق هذه الطريقة في مجال حل غموض الأعداد الصحيحة في أنظمة الملاحة العالمية عبر الأقمار الصناعية (GPS) القائمة على طور الموجة الحاملة. [ 27 ] وتُعرف في هذا المجال باسم طريقة لامدا . وفي المجال نفسه، تُعرف مسألة CVP العامة باسم طريقة المربعات الصغرى للأعداد الصحيحة .

GapCVP

هذه المشكلة مشابهة لمشكلة GapSVP. بالنسبة لـ GapSVP β ، يتكون المدخل من أساس شبكي ومتجهv{\displaystyle v}ويجب على الخوارزمية أن تجيب عما إذا كان أحد الأمور التالية صحيحًا:

  • يوجد متجه شبكي بحيث تكون المسافة بينه وبينv{\displaystyle v}لا يتجاوز 1، و
  • كل متجه شبكي على مسافة أكبر منβ{\displaystyle \beta }بعيدًا عنv{\displaystyle v}.

أما الشرط المعاكس فهو أن يكون أقرب متجه شبكي على مسافة1<λ(ل)≤β{\displaystyle 1<\lambda (L)\leq \beta }ومن هنا جاء اسم Gap CVP.

النتائج المعروفة

تندرج المشكلة بشكل بديهي ضمن فئة NP لأي عامل تقريب.

أظهر شنور ، في عام 1987، أن الخوارزميات الحتمية ذات الوقت متعدد الحدود يمكنها حل المشكلة لـβ=2يا(ن(سجل⁡سجل⁡ن)2/سجل⁡ن){\displaystyle \beta =2^{O(n(\log \log n)^{2}/\log n)}}[ 28 ] أظهر أجتاي وآخرون أن الخوارزميات الاحتمالية يمكن أن تحقق عامل تقريب أفضل قليلاً لـβ=2يا(نسجل⁡سجل⁡ن/سجل⁡ن){\displaystyle \beta =2^{O(n\log \log n/\log n)}}[ 10 ]​

في عام 1993، أظهر باناسزيك أن GapCVP n موجود فيشمالP∩جoشمالP{\displaystyle {\mathsf {NP\cap coNP}}}[ 29 ] في عام 2000 ، أظهر غولدريتش وغولدواسير أنβ=ن/سجل⁡ن{\displaystyle \beta ={\sqrt {n/\log n}}}يضع هذا المشكلة في كل من NP و coAM . [ 30 ] في عام 2005، أظهر أهارونوف وريجيف أنه بالنسبة لبعض الثوابتج{\displaystyle c}المشكلة معβ=جن{\displaystyle \beta =c{\sqrt {n}}}هو فيشمالP∩جoشمالP{\displaystyle {\mathsf {NP\cap coNP}}}[ 31 ]​

بالنسبة للحدود الدنيا، أظهر دينور وآخرون في عام 1998 أن المشكلة من نوع NP-hard بالنسبة لـβ=نo(1/سجل⁡سجل⁡ن){\displaystyle \beta =n^{o(1/\log {\log {n}})}}[ 32 ]​

مسألة أقصر المتجهات المستقلة (SIVP)

بالنظر إلى شبكة L ذات بُعد n ، يجب أن تُخرج الخوارزمية n عناصر مستقلة خطيًاv1،v2،...،vن{\displaystyle v_{1},v_{2},\ldots ,v_{n}}لهذا السبب.الأعلى‖vأنا‖≤الأعلىب‖بأنا‖{\displaystyle \max \|v_{i}\|\leq \max _{B}\|b_{i}\|}، حيث يأخذ الجانب الأيمن في الاعتبار جميع الاحتمالاتب={ب1،...،بن}{\displaystyle B=\{b_{1},\ldots ,b_{n}\}}من الشبكة.

فيγ{\displaystyle \gamma }- في النسخة التقريبية، عند إعطاء شبكة L ذات بُعد n ، يجب إيجاد n متجهات مستقلة خطيًاv1،v2،...،vن{\displaystyle v_{1},v_{2},\ldots ,v_{n}}من الطول ⁠الأعلى‖vأنا‖≤γλن(ل){\displaystyle \max \|v_{i}\|\leq \gamma \lambda _{n}(L)}، حيثλن(ل){\displaystyle \lambda _{n}(L)}هو ⁠ن{\displaystyle n}الحد الأدنى المتتالي لـل{\displaystyle L}⁠ .

فك التشفير بمسافة محدودة

هذه المسألة مشابهة لمسألة القيمة الحدية. بفرض وجود متجه بحيث تكون المسافة بينه وبين الشبكة على الأكثرλ(ل)/2{\displaystyle \lambda (L)/2}، يجب أن تُخرج الخوارزمية أقرب متجه شبكي إليه.

مشكلة نصف قطر التغطية

بالنظر إلى أساس الشبكة، يجب على الخوارزمية إيجاد أكبر مسافة (أو في بعض الإصدارات، تقريبها) من أي متجه إلى الشبكة.

مشكلة أقصر أساس

تصبح العديد من المسائل أسهل إذا كانت قاعدة الإدخال تتكون من متجهات قصيرة. يجب على الخوارزمية التي تحل مسألة أقصر قاعدة (SBP)، عند إعطائها قاعدة شبكية ، أن...ب{\displaystyle B}⁠ , إخراج أساس مكافئب′{\displaystyle B'}بحيث يكون طول أطول متجه فيب′{\displaystyle B'}أقصر ما يمكن.

تتمثل النسخة التقريبية لمسألة SBP γ في إيجاد أساس يكون أطول متجه فيه على الأكثرγ{\displaystyle \gamma }أطول بعدة مرات من أطول متجه في أقصر أساس.

الاستخدام في علم التشفير

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

تُعدّ مسائل الشبكة المذكورة أعلاه سهلة الحل إذا ما زُوِّدت الخوارزمية بأساس "جيد". تهدف خوارزميات اختزال الشبكة ، عند إعطاء أساس للشبكة، إلى إخراج أساس جديد يتألف من متجهات قصيرة نسبيًا وشبه متعامدة . كانت خوارزمية لينسترا-لينسترا-لوفاس لاختزال أساس الشبكة (LLL) من أوائل الخوارزميات الفعّالة لهذه المسألة، إذ استطاعت إخراج أساس شبكة مُختزل تقريبًا في وقت متعدد الحدود. [ 33 ] استُخدمت هذه الخوارزمية وتحسيناتها اللاحقة لكسر العديد من أنظمة التشفير، مما رسّخ مكانتها كأداة بالغة الأهمية في تحليل الشفرات . أدّى نجاح خوارزمية LLL على البيانات التجريبية إلى الاعتقاد بأن اختزال الشبكة قد يكون مسألة سهلة عمليًا؛ إلا أن هذا الاعتقاد وُوجه بالتحدي في أواخر التسعينيات، عندما تم الحصول على العديد من النتائج الجديدة حول صعوبة مسائل الشبكة، بدءًا من نتيجة أجتاي . [ 2 ]

في أبحاثه الرائدة، بيّن أجتاي أن مسألة SVP هي مسألة صعبة الحل (NP-hard)، واكتشف بعض الروابط بين تعقيد الحالة الأسوأ وتعقيد الحالة المتوسطة لبعض مسائل الشبكة. [ 2 ] [ 3 ] وبناءً على هذه النتائج، ابتكر أجتاي ودورك نظام تشفير بالمفتاح العام، يمكن إثبات أمانه باستخدام صعوبة الحالة الأسوأ فقط لإصدار معين من مسألة SVP، [ 34 ] مما يجعله أول نتيجة تستخدم صعوبة الحالة الأسوأ لإنشاء أنظمة آمنة. [ 35 ]

انظر أيضاً

مراجع

  1. ↑ خوت، سوبهاش (2005). "صعوبة تقريب مسألة أقصر متجه في الشبكات". مجلة ACM . 52 (5): 789-808 . doi : 10.1145/1089023.1089027 . S2CID 13438130 . 
  2. 1 2 3 أجتاي، م. (1996). "توليد حالات صعبة لمسائل الشبكة" . وقائع الندوة السنوية الثامنة والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة . فيلادلفيا، بنسلفانيا، الولايات المتحدة: جمعية آلات الحوسبة. الصفحات 99-108 . doi : 10.1145/237814.237838 . ISBN  978-0-89791-785-8. S2CID 6864824 . 
  3. 1 2 أجتاي، ميكلوس (1998). "مسألة أقصر متجه في L² هي مسألة صعبة من نوع NP بالنسبة للاختزالات العشوائية" . وقائع الندوة السنوية الثلاثين لجمعية ACM حول نظرية الحوسبة . دالاس، تكساس، الولايات المتحدة: ACM. الصفحات 10-19 . doi : 10.1145/276698.276705 . ISBN  978-0-89791-962-3. S2CID 4503998 . 
  4. ↑ فان إمده بواس، بيتر (1981). "مسألة أخرى من مسائل NP-complete وتعقيد حساب المتجهات القصيرة في الشبكة" . تقرير فني رقم 8104. جامعة أمستردام، قسم الرياضيات، هولندا.
  5. ↑ كانان، رافي (1983). "خوارزميات محسّنة للبرمجة العددية الصحيحة ومسائل الشبكة ذات الصلة". وقائع الندوة السنوية الخامسة عشرة لجمعية ACM حول نظرية الحوسبة - STOC '83 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 193-206 . doi : 10.1145/800061.808749 . ISBN  978-0-89791-099-6. S2CID 18181112 . 
  6. 1 2 فينكه، يو.؛ بوست، إم. (1985). "طرق محسّنة لحساب المتجهات ذات الطول القصير في الشبكة، بما في ذلك تحليل التعقيد" . الرياضيات الحاسوبية 44 (170): 463-471 . doi : 10.1090/S0025-5718-1985-0777278-8 .
  7. ↑ غاما، نيكولاس؛ نغوين، فونغ كيو؛ ريغيف، أوديد (30 مايو 2010). "تعداد الشبكة باستخدام التقليم المتطرف" . التطورات في علم التشفير - يورو كريبت 2010. سلسلة محاضرات في علوم الحاسوب. المجلد 6110. سبرينغر، برلين، هايدلبرغ. الصفحات 257-278 . doi : 10.1007/978-3-642-13190-5_13 . ISBN   978-3-642-13189-9. S2CID 1938519 . 
  8. ↑ شنور، كلاوس بيتر (27 فبراير 2003). "اختزال الشبكة عن طريق أخذ العينات العشوائية وطرق عيد الميلاد". ستاكس 2003. سلسلة محاضرات في علوم الحاسوب. المجلد 2607. سبرينغر، برلين، هايدلبرغ. الصفحات 145-156 . CiteSeerX 10.1.1.137.4293 . doi : 10.1007/3-540-36494-3_14 . ISBN    978-3-540-36494-8.
  9. ↑ أونو، يوشينوري؛ نغوين، فونغ كيو. (30 أبريل 2017). "إعادة النظر في أخذ العينات العشوائية: تعداد الشبكة مع التقليم المنفصل". التطورات في علم التشفير - يورو كريبت 2017 (ملف PDF) . سلسلة محاضرات في علوم الحاسوب. المجلد 10211. سبرينغر، تشام. الصفحات 65-102 . doi : 10.1007/978-3-319-56614-6_3 . ISBN   978-3-319-56613-9. S2CID 39082279 . 
  10. 1 2 أجتاي، ميكلوس؛ كومار، رافي؛ سيفاكومار، د. (2001). "خوارزمية غربلة لمسألة أقصر متجه شبكي" . وقائع الندوة السنوية الثالثة والثلاثين لجمعية ACM حول نظرية الحوسبة . خيرسونيسوس، اليونان: ACM. ص 601-610 . doi : 10.1145/380752.380857 . ISBN  1-58113-349-9. S2CID 14982298 . 
  11. ↑ ميتشيانسيو، دانييلي؛ فولغاريس، بانايوتيس (2010). "خوارزميات أسرع ذات زمن أسي لمسألة أقصر متجه" . وقائع الندوة السنوية الحادية والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة . SODA '10. فيلادلفيا، بنسلفانيا، الولايات المتحدة الأمريكية: جمعية الرياضيات الصناعية والتطبيقية. الصفحات 1468-1480 . doi : 10.1137/1.9781611973075.119 . ISBN  978-0-89871-698-6. S2CID 90084 . 
  12. ↑ بيكر، أ.؛ دوكاس، ل.؛ غاما، ن.؛ لارهوفن، ت. (21-12-2015). "اتجاهات جديدة في البحث عن أقرب جار مع تطبيقات على غربلة الشبكة". وقائع الندوة السنوية السابعة والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة . جمعية الرياضيات الصناعية والتطبيقية. ص 10-24 . doi : 10.1137/1.9781611974331.ch2 . ISBN  978-1-61197-433-1.
  13. 1 2 أغريل، إي.؛ إريكسون، تي.؛ فاردي، أ.؛ زيغر، ك. (2002). "بحث أقرب نقطة في الشبكات" (ملف PDF) . معاملات IEEE لنظرية المعلومات . 48 (8): 2201-2214 . doi : 10.1109/TIT.2002.800499 .
  14. ↑ ميتشيانسيو، دانييلي؛ فولغاريس، بانايوتيس (2010). "خوارزمية حتمية أحادية الزمن الأسي لمعظم مسائل الشبكة تعتمد على حسابات خلايا فورونوي". وقائع ندوة ACM الثانية والأربعين حول نظرية الحوسبة . STOC '10. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 351-358 . CiteSeerX 10.1.1.705.3304 . doi : 10.1145/1806689.1806739 . ISBN   978-1-4503-0050-6. S2CID 2449948 . 
  15. ↑ أغاروال، ديفيش؛ دادوش، دانيال؛ ريغيف، أوديد؛ ستيفنز-دافيدويتز، نوح (2015). "حل مسألة أقصر متجه في زمن 2^ n باستخدام أخذ العينات الغاوسية المنفصلة". وقائع الندوة السنوية السابعة والأربعين لجمعية ACM حول نظرية الحوسبة . STOC '15. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 733-742 . doi : 10.1145/2746539.2746606 . ISBN  978-1-4503-3536-2. S2CID 10214330 . 
  16. ↑ ميتشيانسيو، دانييلي (2017-07-01). "تشفير الشبكة - مشكلة أقصر متجه" .
  17. ↑ شنور، سي بي (1987-01-01). "تسلسل هرمي لخوارزميات اختزال أساس الشبكة في زمن متعدد الحدود" . علوم الحاسوب النظرية . 53 (2): 201-224 . doi : 10.1016/0304-3975(87)90064-8 .
  18. ↑ شنور، سي بي؛ يوشنر، إم. (1994-08-01). "اختزال أساس الشبكة: خوارزميات عملية محسّنة وحل مسائل مجموع المجموعات الجزئية" (ملف PDF) . البرمجة الرياضية . 66 ( 1-3 ): 181-199 . doi : 10.1007/bf01581144 . ISSN 0025-5610 . S2CID 15386054 .  
  19. ↑ تشين، يوانمي؛ نغوين، فونغ كيو. (4 ديسمبر 2011). "BKZ 2.0: تقديرات أفضل لأمن الشبكة". التطورات في علم التشفير - ASIACRYPT 2011. سلسلة محاضرات في علوم الحاسوب. المجلد 7073. سبرينغر، برلين، هايدلبرغ. الصفحات 1-20 . doi : 10.1007/978-3-642-25385-0_1 . ISBN   978-3-642-25384-3.
  20. ↑ بيكرت، كريس (2009). "أنظمة التشفير بالمفتاح العام من مشكلة أقصر متجه في أسوأ الحالات: ملخص موسع" . وقائع الندوة السنوية الحادية والأربعين لجمعية ACM حول نظرية الحوسبة . بيثيسدا، ماريلاند، الولايات المتحدة الأمريكية: ACM. الصفحات 333-342 . doi : 10.1145/1536414.1536461 . ISBN  978-1-60558-506-2. S2CID 1864880 . 
  21. ^ دانييلي ميسيانسيو. غولدفاسر، شافي (2002). تعقيد مشاكل شعرية . سبرينغر.
  22. ↑ غولدريتش، أ.؛ وآخرون (1999). "تقريب أقصر متجهات الشبكة ليس أصعب من تقريب أقرب متجهات الشبكة". رسائل معالجة المعلومات 71 ( 2): 55-61 . doi : 10.1016/S0020-0190(99)00083-6 . 
  23. ↑ أرورا، سانجيف؛ وآخرون (1993). "وقائع المؤتمر السنوي الرابع والثلاثين لمؤسسة علوم الحاسوب لعام 1993 التابع لمعهد مهندسي الكهرباء والإلكترونيات". مجلة علوم أنظمة الحاسوب . المجلد 54. الصفحات 317-331 . doi : 10.1109/SFCS.1993.366815 . ISBN    978-0-8186-4370-5. S2CID 44988406 . 
  24. ↑ دينور، إ.؛ وآخرون (2003). "تقريب CVP ضمن عوامل شبه متعددة الحدود هو مسألة صعبة من نوع NP". كومبيناتوريكا . 23 (2): 205-243 . doi : 10.1007/s00493-003-0019-y . S2CID 45754954 .  
  25. ↑ بيغلييري، إي.؛ كالدربانك، ر.؛ كونستانتينيدس، أنتوني ج .؛ غولدسميث، أ.؛ بولراج، أ.؛ بور، إتش في (2007). اتصالات MIMO اللاسلكية . كامبريدج: مطبعة جامعة كامبريدج
  26. ↑ وانغ، بينغ؛ لي-نغوك، ثو (2011). "خوارزمية فك تشفير قائمة كروية مع استراتيجيات محسّنة لتحديد نصف القطر". الاتصالات الشخصية اللاسلكية . 61 (1): 189-200 . doi : 10.1007/s11277-010-0018-4 . S2CID 30919872 . 
  27. ↑ حسيب، أ.؛ بويد، س. (1998). "تقدير المعاملات الصحيحة في النماذج الخطية مع تطبيقات على نظام تحديد المواقع العالمي (GPS)". معاملات IEEE لمعالجة الإشارات. 46 ( 11): 2938-2952 . Bibcode : 1998ITSP...46.2938H . CiteSeerX 10.1.1.114.7246 . doi : 10.1109/78.726808 . 
  28. ↑ شنور، سي بي "تحليل الأعداد الصحيحة وحساب اللوغاريتمات المنفصلة عبر التقريب الديوفانتي". التقدم في علم التشفير - وقائع مؤتمر يورو كريبت 91 .
  29. ↑ باناسزيك، و. (1993). "حدود جديدة في بعض نظريات النقل في هندسة الأعداد". حوليات الرياضيات 296 (1): 625-635 . doi : 10.1007/BF01445125 . S2CID 13921988 . 
  30. ↑ غولدريتش، أوديد؛ غولدواسير، شافي (1998). "حول حدود عدم إمكانية تقريب مسائل الشبكة" . وقائع الندوة السنوية الثلاثين لجمعية آلات الحوسبة (ACM) حول نظرية الحوسبة . دالاس، تكساس، الولايات المتحدة: جمعية آلات الحوسبة (ACM). الصفحات 1-9 . doi : 10.1145/276698.276704 . ISBN  0-89791-962-9. S2CID 3051993 . 
  31. ^ أهارونوف، دوريت. عوديد ريجيف (2005). "مشاكل شعرية في NP∩{\displaystyle \cap }coNP". J. ACM . 52 (5): 749-765 . CiteSeerX 10.1.1.205.3730 . دوى : 10.1145/1089023.1089025 . S2CID 1669286 .  
  32. ↑ دينور، آي.؛ كيندلر، جي.؛ صفرا، إس. (1998). "تقريب مسألة القيمة الثابتة ضمن عوامل شبه متعددة الحدود هو مسألة صعبة من نوع NP" . وقائع الندوة السنوية التاسعة والثلاثين حول أسس علوم الحاسوب . جمعية مهندسي الكهرباء والإلكترونيات. ص 99. ISBN  978-0-8186-9172-0.
  33. ↑ لينسترا، أ.ك.؛ لينسترا، هـ.و. الابن؛ لوفاس، ل. (1982). "تحليل كثيرات الحدود ذات المعاملات النسبية" (ملف PDF) . حوليات الرياضيات 261 (4): 515-534 . doi : 10.1007/BF01457454 . S2CID 5701340. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 17 يوليو 2011. 
  34. ↑ أجتاي، ميكلوس؛ دورك، سينثيا (1997). "نظام تشفير بالمفتاح العام مع تكافؤ أسوأ الحالات/متوسط ​​الحالات" . وقائع الندوة السنوية التاسعة والعشرين لجمعية ACM حول نظرية الحوسبة . إل باسو، تكساس، الولايات المتحدة: ACM. الصفحات 284-293 . doi : 10.1145/258533.258604 . ISBN  0-89791-888-6. S2CID 9918417 . 
  35. ↑ كاي، جين-يي (2000). "تعقيد بعض مسائل الشبكة". نظرية الأعداد الخوارزمية . سلسلة محاضرات في علوم الحاسوب. المجلد 1838. الصفحات 1-32 . doi : 10.1007/10722028_1 . ISBN   978-3-540-67695-9.

للمزيد من القراءة