سؤال عشوائي من SQuAD:
متى تم اكتشاف إمكانية تطبيق الأعداد الأولية على إنشاء خوارزميات تشفير المفتاح العام؟
إجابة:
السبعينيات
الجمل المسترجعة:
- ومع ذلك، فقد حطمت هذه الرؤية في 1970s، عندما أعلن على الملأ أن الأعداد الأولية يمكن أن تستخدم كأساس لإنشاء خوارزميات التشفير المفتاح العمومي.
- تُستخدم الأعداد الأولية في العديد من الإجراءات الروتينية في تكنولوجيا المعلومات ، مثل تشفير المفتاح العام ، والذي يستخدم خصائص مثل صعوبة تحليل أعداد كبيرة في عواملها الأولية.
- تم تصميم خوارزميات أكثر كفاءة من التقسيم التجريبي لاختبار بدائية الأعداد الكبيرة.
- تعتمد العديد من خوارزميات تشفير المفتاح العام ، مثل RSA وتبادل مفاتيح Diffie-Hellman ، على أعداد أولية كبيرة (على سبيل المثال ، تُستخدم الأعداد الأولية 512 بت بشكل متكرر لـ RSA والأعداد الأولية 1024 بت نموذجية لـ Diffie-Hellman.) .
- تُستخدم الأرقام الأولية أيضًا لجداول التجزئة ومولدات الأرقام العشوائية الزائفة.
- تم العثور على بعض هذه الأعداد الأولية باستخدام الحوسبة الموزعة.
- لفترة طويلة ، كان يُنظر إلى نظرية الأعداد بشكل عام ، ودراسة الأعداد الأولية على وجه الخصوص ، على أنها مثال أساسي للرياضيات البحتة ، مع عدم وجود تطبيقات خارج المصلحة الذاتية لدراسة الموضوع باستثناء استخدام الأعداد الأولية. أسنان التروس لتوزيع التآكل بالتساوي.
- توفر الخوارزميات الحتمية طريقة لمعرفة ما إذا كان رقم معين أوليًا أم لا.
- لا تتضمن عبارة "جميع الخوارزميات الممكنة" الخوارزميات المعروفة اليوم فحسب ، بل تشمل أي خوارزمية يمكن اكتشافها في المستقبل.
- على سبيل المثال ، القسم التجريبي عبارة عن خوارزمية حتمية لأنه ، إذا تم إجراؤها بشكل صحيح ، فستحدد دائمًا رقمًا أوليًا كرقم أولي ورقم مركب على أنه مركب.
- بصيغتها كمشكلة قرار ، إنها مشكلة تحديد ما إذا كان المدخل له عامل أقل من k. لا تُعرف خوارزمية عامل صحيح فعالة ، وهذه الحقيقة تشكل أساس العديد من أنظمة التشفير الحديثة ، مثل خوارزمية RSA.
- قبل أن يبدأ البحث الفعلي المكرس بشكل صريح لتعقيد المشكلات الحسابية ، تم وضع العديد من الأسس من قبل العديد من الباحثين.
- يؤكد هذا المبدأ المحلي العالمي مرة أخرى على أهمية الأعداد الأولية لنظرية الأعداد.
- عادةً ما تكون الخوارزميات الاحتمالية أسرع ، لكنها لا تثبت تمامًا أن الرقم أولي.
- ومع ذلك ، فإن أفضل خوارزمية كمومية لهذه المشكلة ، وهي خوارزمية شور ، تعمل في زمن كثير الحدود.
- يُعد غربال إراتوستينس ، المنسوب إلى إراتوستينس ، طريقة بسيطة لحساب الأعداد الأولية ، على الرغم من أن الأعداد الأولية الكبيرة الموجودة حاليًا مع أجهزة الكمبيوتر لا يتم إنشاؤها بهذه الطريقة.
- تعتبر المشكلة صعبة بطبيعتها إذا كان حلها يتطلب موارد كبيرة ، بغض النظر عن الخوارزمية المستخدمة.
- تسمى الخوارزميات التي تستخدم بتات عشوائية الخوارزميات العشوائية.
- من المعتقد أنه إذا كان من الممكن حل مشكلة ما بواسطة خوارزمية ، فهناك آلة تورينج تحل المشكلة.
- تعد أعداد كارمايكل أكثر ندرة بشكل كبير من الأعداد الأولية ، لذلك يمكن أن يكون هذا الاختبار مفيدًا لأغراض عملية.
- على سبيل المثال ، بدأت قائمة ديريك نورمان ليمر بالأعداد الأولية حتى 10.006.721 ، والتي أعيد طبعها حتى عام 1956 ، بالرقم 1 كأول أول أولي لها.
- تقول أطروحة كوبهام أن المشكلة يمكن حلها باستخدام قدر ممكن من الموارد إذا سمحت بخوارزمية متعددة الحدود.
- أظهر إقليدس أيضًا كيفية بناء رقم مثالي من Mersenne Prime.
- اعتبارًا من يناير 2016 [تحديث] ، يحتوي أكبر عدد أولي معروف على 22،338،618 رقمًا عشريًا.
- حفزت مثل هذه الأسئلة على تطوير فروع مختلفة من نظرية الأعداد ، مع التركيز على الجوانب التحليلية أو الجبرية للأرقام.