وظيفة ضئيلة

في الرياضيات، الدالة المهملة هي دالة${\displaystyle \mu$ :\mathbb {N} \to \mathbb {R} } بحيث أنه لكل عدد صحيح موجب c يوجد عدد صحيح N _c بحيث أنه لكل x  > N _c ، 

${\displaystyle |\mu (x)|<{\frac {1}{x^{c}}}.}$

وبالمثل، يمكن استخدام التعريف التالي. دالة${\displaystyle \mu$ يكون التعبير `:\mathbb {N} \to \mathbb {R}` مهملاً ، إذا كان لكل متعددة حدود موجبة `poly(·)` يوجد عدد صحيح `N` <sub>`poly</sub>  > 0` بحيث يكون لكل `x  > N` _`poly` 

${\displaystyle |\mu (x)|<{\frac {1}{\operatorname {poly} (x)}}.}$

يمكن تتبع مفهوم الإهمال إلى نماذج تحليلية سليمة. مع أن مفهومي " الاستمرارية " و" التناهي في الصغر " اكتسبا أهمية في الرياضيات خلال عصر نيوتن وليبنيز (ثمانينيات القرن السابع عشر)، إلا أنهما لم يُحددا بدقة إلا في أواخر العقد الثاني من القرن التاسع عشر. يعود أول تعريف دقيق للاستمرارية في التحليل الرياضي إلى برنارد بولزانو ، الذي كتب عام ١٨١٧ التعريف الحديث لها. وفي وقت لاحق ، عرّفها كل من كوشي وويرستراس وهاينه على النحو التالي (مع اعتبار جميع الأعداد في مجال الأعداد الحقيقية) .${\displaystyle \mathbb {R} }$):

( دالة متصلة ) دالة${\displaystyle f:\mathbb {R} {\rightarrow }\mathbb {R} }$متصل عند​${\displaystyle x=x_{0}}$إذا لكل${\displaystyle \varepsilon >0}$يوجد عدد موجب${\displaystyle \delta >0}$بحيث${\displaystyle |x-x_{0}|<\delta }$يشير إلى${\displaystyle |f(x)-f(x_{0})|<\varepsilon .}$

يمكن تحويل هذا التعريف الكلاسيكي للاستمرارية إلى تعريف الإهمال في بضع خطوات عن طريق تغيير المعلمات المستخدمة في التعريف. أولاً، في حالة${\displaystyle x_{0}=\infty }$مع${\displaystyle f(x_{0})=0}$، يجب علينا تعريف مفهوم " الدالة المتناهية الصغر ":

( متناهي الصغر ) دالة متصلة${\displaystyle \mu$ :\mathbb {R} \to \mathbb {R} } متناهي الصغر (كما${\displaystyle x}$(يؤول إلى ما لا نهاية) إذا كان لكل${\displaystyle \varepsilon >0}$يوجد${\displaystyle N_{\varepsilon }}$بحيث يكون ذلك لجميع${\displaystyle x>N_{\varepsilon }}$

${\displaystyle |\mu (x)|<\varepsilon \,.}$

بعد ذلك، نستبدل${\displaystyle \varepsilon >0}$بواسطة الوظائف${\displaystyle 1/x^{c}}$أين${\displaystyle c>0}$أو عن طريق${\displaystyle 1/\operatorname {poly} (x)}$أين${\displaystyle \operatorname {poly} (x)}$هي دالة كثيرة الحدود موجبة . وهذا يؤدي إلى تعريفات الدوال المهملة الواردة في بداية هذه المقالة. بما أن الثوابت${\displaystyle \varepsilon >0}$يمكن التعبير عنها على النحو التالي${\displaystyle 1/\operatorname {poly} (x)}$مع وجود دالة متعددة الحدود ثابتة، يوضح هذا أن الدوال المتناهية الصغر هي مجموعة شاملة من الدوال المهملة.

في علم التشفير الحديث القائم على التعقيد ، يكون نظام الأمان آمنًا بشكل مثبت إذا كان احتمال فشل الأمان (على سبيل المثال، عكس دالة أحادية الاتجاه ، أو التمييز بين البتات شبه العشوائية القوية تشفيرًا والبتات العشوائية الحقيقية) ضئيلاً بالنسبة للمدخلات.${\displaystyle x}$= طول المفتاح التشفيري${\displaystyle n}$ومن هنا يأتي التعريف الموجود في أعلى الصفحة لأن طول المفتاح${\displaystyle n}$يجب أن يكون عددًا طبيعيًا .

ومع ذلك، فإن المفهوم العام للإهمال لا يتطلب أن تكون معلمة الإدخال${\displaystyle x}$الطول هو المفتاح${\displaystyle n}$. بالفعل،${\displaystyle x}$يمكن أن يكون أي مقياس نظام محدد مسبقًا، وسيوضح التحليل الرياضي المقابل بعض السلوكيات التحليلية الخفية للنظام.

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

من الناحية العملية، قد يرغب المرء في الحصول على وظائف أكثر تحديدًا تحد من احتمالية نجاح الخصم واختيار معلمة الأمان كبيرة بما يكفي بحيث تكون هذه الاحتمالية أصغر من عتبة معينة، على سبيل المثال  2 ^{- 128} .

أحد أسباب استخدام الدوال المهملة في أسس التشفير القائم على نظرية التعقيد هو أنها تخضع لخصائص الإغلاق. ^{[ 1 ]} على وجه التحديد،

1. لو${\displaystyle f,g:\mathbb {N} \to \mathbb {R} }$إذا كانت ضئيلة، فإن الدالة${\displaystyle x\mapsto f(x)+g(x)}$لا يُذكر.
2. لو${\displaystyle f:\mathbb {N} \to \mathbb {R} }$ضئيل و${\displaystyle p}$إذا كانت أي كثيرة حدود حقيقية، فإن الدالة${\displaystyle x\mapsto p(x)\cdot f(x)}$لا يُذكر.

على العكس من ذلك ، إذا${\displaystyle f:\mathbb {N} \to \mathbb {R} }$إذا لم يكن الأمر ضئيلاً، فإن الأمر ليس كذلك أيضاً.${\displaystyle x\mapsto f(x)/p(x)}$لأي كثير حدود حقيقي${\displaystyle p}$.

• ${\displaystyle n\mapsto a^{-n}}$لا يُعتد به لأي${\displaystyle a\geq 2}$:
  • الخطوة : هذه دالة اضمحلال أسي حيث${\displaystyle a}$ثابت أكبر من أو يساوي 2.${\displaystyle n\to \infty }$،${\displaystyle a^{-n}\to 0}$بسرعة كبيرة، مما يجعلها ضئيلة.
• ${\displaystyle f(n)=3^{-{\sqrt {n}}}}$لا يُذكر:
  • الخطوة : هذه الدالة لها انحلال أسي أساسه 3، لكن الأس ينمو بشكل أبطأ من${\displaystyle n}$(فقط في${\displaystyle {\sqrt {n}}}$). مثل${\displaystyle n\to \infty }$،${\displaystyle 3^{-{\sqrt {n}}}\to 0}$لذا فهو لا يزال ضئيلاً ولكنه يتلاشى بشكل أبطأ من${\displaystyle 3^{-n}}$.
• ${\displaystyle f(n)=n^{-\log n}}$لا يُذكر:
  • الخطوة : في هذه الحالة،${\displaystyle n^{-\log n}}$يمثل هذا اضمحلالًا متعدد الحدود، حيث ينمو الأس بشكل سلبي بسبب${\displaystyle \log n}$بما أن معدل التحلل يزداد مع${\displaystyle n}$، تقترب الدالة من الصفر أسرع من الدوال متعددة الحدود مثل${\displaystyle n^{-k}}$لأي ثابت${\displaystyle k}$مما يجعله ضئيلاً.
• ${\displaystyle f(n)=(\log n)^{-\log n}}$لا يُذكر:
  • الخطوة : تتناقص هذه الدالة مع لوغاريتم${\displaystyle n}$مرفوعًا إلى أس سالب${\displaystyle -\log n}$مما يؤدي إلى اقتراب سريع من الصفر عندما${\displaystyle n\to \infty }$. إن معدل التحلل هنا أسرع من المعدلات اللوغاريتمية العكسية أو المعدلات متعددة الحدود، مما يجعله ضئيلاً.
• ${\displaystyle f(n)=2^{-c\log n}}$لا يمكن إهمالها، بالنسبة للإيجابية${\displaystyle c}$:
  • الخطوة : يمكننا إعادة كتابة هذا على النحو التالي${\displaystyle f(n)=n^{-c}}$وهو اضمحلال متعدد الحدود وليس اضمحلالًا أُسّيًا.${\displaystyle c}$إيجابي،${\displaystyle f(n)\to 0}$مثل${\displaystyle n\to \infty }$لكنها لا تتلاشى بالسرعة نفسها التي تتلاشى بها الدوال الأسية الحقيقية بالنسبة إلى${\displaystyle n}$مما يجعلها ذات أهمية لا يُستهان بها.

يفترض${\displaystyle n>0}$نعتبر الحد كما يلي${\displaystyle n\to \infty }$:

ضئيل:

• ${\displaystyle f(n)={\frac {1}{x^{n/2}}}}$:
  • الخطوة : تتناقص هذه الدالة أُسّيًا مع الأساس${\displaystyle x}$رُفعت إلى قوة${\displaystyle -{\frac {n}{2}}}$. مثل${\displaystyle n\to \infty }$،${\displaystyle x^{-{\frac {n}{2}}}\to 0}$بسرعة، مما يجعلها ضئيلة.
• ${\displaystyle f(n)={\frac {1}{x^{\log {(n^{k})}}}}}$ل${\displaystyle k\geq 1}$:
  • الخطوة : يمكننا التبسيط${\displaystyle x^{-\log(n^{k})}}$مثل${\displaystyle n^{-k\log x}}$، والتي تتلاشى أسرع من أي متعددة حدود.${\displaystyle n\to \infty }$، تقترب الدالة من الصفر وتُعتبر ضئيلة لأي${\displaystyle k\geq 1}$و${\displaystyle x>1}$.
• ${\displaystyle f(n)={\frac {1}{x^{(\log n)^{k}}}}}$ل${\displaystyle k\geq 1}$:
  • الخطوة : يتم تحديد معدل التحلل بواسطة القاعدة${\displaystyle x}$رُفعت إلى قوة${\displaystyle -(\log n)^{k}}$. منذ${\displaystyle (\log n)^{k}}$ينمو مع${\displaystyle n}$تقترب هذه الدالة من الصفر أسرع من التضاؤل ​​متعدد الحدود، مما يجعلها ضئيلة.
• ${\displaystyle f(n)={\frac {1}{x^{\sqrt {n}}}}}$:
  • الخطوة : هنا،${\displaystyle f(n)}$يتناقص أُسّيًا بقاعدة قدرها${\displaystyle x}$تم رفعه إلى${\displaystyle -{\sqrt {n}}}$. مثل${\displaystyle n\to \infty }$،${\displaystyle f(n)\to 0}$بسرعة، لذلك يعتبر ضئيلاً.
• ${\displaystyle f(n)={\frac {1}{x^{n(\log n)}}}}$:
  • الخطوة : باستخدام أساس وأس أُسّيين${\displaystyle n(\log n)}$، ستقترب هذه الدالة من الصفر بسرعة كبيرة، مما يشير إلى إمكانية إهمالها.

غير مهمل:

• ${\displaystyle f(n)={\frac {1}{n^{1/n}}}}$:
  • الخطوة : بما أن${\displaystyle n^{1/n}\to 1}$مثل${\displaystyle n\to \infty }$تتلاشى هذه الدالة ببطء شديد، ولا تقترب من الصفر بسرعة كافية لاعتبارها ضئيلة.

• مجموعة ضئيلة
• جبر كولومبو
• الأرقام غير القياسية
• نظرية غروموف حول مجموعات النمو متعدد الحدود
• حساب التفاضل والتكامل غير القياسي

• جولدرايش، أوديد (2001). أسس التشفير: المجلد 1، الأدوات الأساسية . مطبعة جامعة كامبريدج. ISBN 0-521-79172-3.
• سيبسر، مايكل (1997). "القسم 10.6.3: الدوال أحادية الاتجاه" . مقدمة في نظرية الحوسبة . دار نشر PWS. الصفحات 374-376 . ISBN  0-534-94728-X.
• باباديميتريو، كريستوس (1993). "القسم 12.1: الدوال أحادية الاتجاه". التعقيد الحسابي (  الطبعة الأولى). أديسون ويسلي. الصفحات 279-298 . ISBN  0-201-53082-1.
• كولومبو، جان فرانسوا (1984). الدوال المعممة الجديدة وضرب التوزيعات . دراسات في الرياضيات 84، نورث هولاند. ISBN 0-444-86830-5.
• بيلاري، ميهير (1997). “ملاحظة حول الوظائف المهملة”. مجلة علم التشفير . 15 . قسم علوم وهندسة الكمبيوتر جامعة كاليفورنيا في سان دييغو: 2002. CiteSeerX 10.1.1.43.7900 .