أيهما من الأسماء التالية ليس لقب شخص ما: (شور) أو (آر إس إيه) ؟ بالنظر إلى السؤال السابق، اكتب السياق الذي يحتوي على الجواب. يمكن أن تكون من 1 إلى 20 جملة السياق:
مشكلة تحليل العوامل للأعداد الصحيحة هي مشكلة حسابية لتحديد تحليل العوامل الأساسية لعدد صحيح معين. يتم صياغتها كمشكلة قرار، وهي مشكلة تحديد ما إذا كان المدخل لديه عامل أقل من k. لا توجد خوارزمية فعّالة لتقسيم الأعداد الصحيحة إلى عوامل معروفة، وتشكل هذه الحقيقة أساس العديد من الأنظمة التشفيرية الحديثة، مثل خوارزمية RSA. مسألة تحليل العوامل الصحيحة في NP و co-NP (وحتى في UP و co-UP). إذا كانت المشكلة NP-كاملة، فإن التسلسل الهرمي للوقت متعدد الحدود سوف ينهار إلى مستواه الأول (أي NP سوف يساوي co-NP). الخوارزمية الأكثر شهرة لعمليّة تخصيص العوامل للأعداد الصحيحة هي عبارة عن خيار المجال العددي العام، والذي يستغرق وقتًا O(e(64/9) 1 / 3 ((n.log 2) 1 / 3 ((log (n.log 2) 2 / 3) لتخصيص العوامل لعدد صحيح من n بت. ومع ذلك، فإن الخوارزمية الكمية الأكثر شهرة لهذه المشكلة، خوارزمية شور، تعمل في وقت متعدد الحدود. لسوء الحظ، هذه الحقيقة لا تقول الكثير عن أين تكمن المشكلة فيما يتعلق بفئات التعقيد غير الكمية.