خوارزمية شور

خوارزمية شوور (Shor's algorithm)‏ هي خوارزمية لتفكيك عدد طبيعي N في زمن O((log N)³) وفي مساحة (O(log N.^[1][2][3] تحمل هاته الخوارزمية اسم بيتر شور.

العمليات

ليكن N عددا طبيعيا معطى. الهدف هو إيجاد عدد آخر p محصور بين 1 وN ويقسم N.

خوارزمية شوور مقسمة إلى قسمين :

1. اختصار مشكلة التفكيك إلى مشكلة الترتيب (نظرية المجموعات), والتي يمكن تطبيقها باستعمال حاسوب عادي.
2. خوارزمية كانتيكية لحل مشكلة البحث عن الدور.

المرحلة الكلاسيكية

1. أخد عدد شبه عشوائي a < N
2. حساب القاسم المشترك الأكبرل a و N. والتي يمكن إيجادها باستعمال خوارزمية اقليدس.
3. إذا كان هذا القاسم المشترك الأكبر مخالفا ل 1, إذن سيكون قاسما فعليا N, يعني نهاية الخوارزمية.
4. وإلا، استعمال البحث عن الدور (انظر أسفله) لإيجاد r, دالة دورية للدالة الآتية :
   ${\displaystyle f(x)=a^{x}\ {\mbox{mod}}\ N}$,
   يعني. أصغر عدد صحيح طبيعي r بحيث ${\displaystyle f(x+r)=f(x)}$.
5. إذا كان r فرديا, نعود للمرحلة 1 1.
6. إذا كان a ^r/2 ≡ -1 [N], نعود للمرحلة 1.
7. قواسم N هي pgcd(a^r/2 ± 1, N). انتهى.

انظر أيضاً

• تحليل (رياضيات)
• فيزياء رياضية

مراجع

موسوعات ذات صلة :

• موسوعة علم الحاسوب
• موسوعة رياضيات
• موسوعة نظرية الأعداد
• موسوعة خوارزميات