سؤال عشوائي من SQuAD:

متى تم اكتشاف إمكانية تطبيق الأعداد الأولية على إنشاء خوارزميات تشفير المفتاح العام؟

إجابة:

السبعينيات

الجمل المسترجعة:

1. ومع ذلك، فقد حطمت هذه الرؤية في 1970s، عندما أعلن على الملأ أن الأعداد الأولية يمكن أن تستخدم كأساس لإنشاء خوارزميات التشفير المفتاح العمومي.
2. تُستخدم الأعداد الأولية في العديد من الإجراءات الروتينية في تكنولوجيا المعلومات ، مثل تشفير المفتاح العام ، والذي يستخدم خصائص مثل صعوبة تحليل أعداد كبيرة في عواملها الأولية.
3. تم تصميم خوارزميات أكثر كفاءة من التقسيم التجريبي لاختبار بدائية الأعداد الكبيرة.
4. تعتمد العديد من خوارزميات تشفير المفتاح العام ، مثل RSA وتبادل مفاتيح Diffie-Hellman ، على أعداد أولية كبيرة (على سبيل المثال ، تُستخدم الأعداد الأولية 512 بت بشكل متكرر لـ RSA والأعداد الأولية 1024 بت نموذجية لـ Diffie-Hellman.) .
5. تُستخدم الأرقام الأولية أيضًا لجداول التجزئة ومولدات الأرقام العشوائية الزائفة.
6. تم العثور على بعض هذه الأعداد الأولية باستخدام الحوسبة الموزعة.
7. لفترة طويلة ، كان يُنظر إلى نظرية الأعداد بشكل عام ، ودراسة الأعداد الأولية على وجه الخصوص ، على أنها مثال أساسي للرياضيات البحتة ، مع عدم وجود تطبيقات خارج المصلحة الذاتية لدراسة الموضوع باستثناء استخدام الأعداد الأولية. أسنان التروس لتوزيع التآكل بالتساوي.
8. توفر الخوارزميات الحتمية طريقة لمعرفة ما إذا كان رقم معين أوليًا أم لا.
9. لا تتضمن عبارة "جميع الخوارزميات الممكنة" الخوارزميات المعروفة اليوم فحسب ، بل تشمل أي خوارزمية يمكن اكتشافها في المستقبل.
10. على سبيل المثال ، القسم التجريبي عبارة عن خوارزمية حتمية لأنه ، إذا تم إجراؤها بشكل صحيح ، فستحدد دائمًا رقمًا أوليًا كرقم أولي ورقم مركب على أنه مركب.
11. بصيغتها كمشكلة قرار ، إنها مشكلة تحديد ما إذا كان المدخل له عامل أقل من k. لا تُعرف خوارزمية عامل صحيح فعالة ، وهذه الحقيقة تشكل أساس العديد من أنظمة التشفير الحديثة ، مثل خوارزمية RSA.
12. قبل أن يبدأ البحث الفعلي المكرس بشكل صريح لتعقيد المشكلات الحسابية ، تم وضع العديد من الأسس من قبل العديد من الباحثين.
13. يؤكد هذا المبدأ المحلي العالمي مرة أخرى على أهمية الأعداد الأولية لنظرية الأعداد.
14. عادةً ما تكون الخوارزميات الاحتمالية أسرع ، لكنها لا تثبت تمامًا أن الرقم أولي.
15. ومع ذلك ، فإن أفضل خوارزمية كمومية لهذه المشكلة ، وهي خوارزمية شور ، تعمل في زمن كثير الحدود.
16. يُعد غربال إراتوستينس ، المنسوب إلى إراتوستينس ، طريقة بسيطة لحساب الأعداد الأولية ، على الرغم من أن الأعداد الأولية الكبيرة الموجودة حاليًا مع أجهزة الكمبيوتر لا يتم إنشاؤها بهذه الطريقة.
17. تعتبر المشكلة صعبة بطبيعتها إذا كان حلها يتطلب موارد كبيرة ، بغض النظر عن الخوارزمية المستخدمة.
18. تسمى الخوارزميات التي تستخدم بتات عشوائية الخوارزميات العشوائية.
19. من المعتقد أنه إذا كان من الممكن حل مشكلة ما بواسطة خوارزمية ، فهناك آلة تورينج تحل المشكلة.
20. تعد أعداد كارمايكل أكثر ندرة بشكل كبير من الأعداد الأولية ، لذلك يمكن أن يكون هذا الاختبار مفيدًا لأغراض عملية.
21. على سبيل المثال ، بدأت قائمة ديريك نورمان ليمر بالأعداد الأولية حتى 10.006.721 ، والتي أعيد طبعها حتى عام 1956 ، بالرقم 1 كأول أول أولي لها.
22. تقول أطروحة كوبهام أن المشكلة يمكن حلها باستخدام قدر ممكن من الموارد إذا سمحت بخوارزمية متعددة الحدود.
23. أظهر إقليدس أيضًا كيفية بناء رقم مثالي من Mersenne Prime.
24. اعتبارًا من يناير 2016 [تحديث] ، يحتوي أكبر عدد أولي معروف على 22،338،618 رقمًا عشريًا.
25. حفزت مثل هذه الأسئلة على تطوير فروع مختلفة من نظرية الأعداد ، مع التركيز على الجوانب التحليلية أو الجبرية للأرقام.