خوارزمية شور

خوارزمية شوور  هي خوارزمية لتفكيك عدد طبيعي N في زمن O((log N)3) وفي مساحة (O(log N. تحمل هاته الخوارزمية اسم بيتر شور.

 العمليات 

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

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

 المرحلة الكلاسيكية 
 أخد عدد شبه عشوائي a < N
 حساب القاسم المشترك الأكبرل a و N. والتي يمكن إيجادها باستعمال خوارزمية اقليدس.
 إذا كان هذا القاسم المشترك الأكبر مخالفا ل 1, إذن سيكون قاسما فعليا N, يعني نهاية الخوارزمية.
 وإلا، استعمال البحث عن الدور (انظر أسفله) لإيجاد r, دالة دورية للدالة الآتية :,يعني. أصغر عدد صحيح طبيعي r بحيث .
 إذا كان r فرديا, نعود للمرحلة 1 1.
 إذا كان a r/2 ≡ -1 [N], نعود للمرحلة 1.
 قواسم N هي pgcd(ar/2 ± 1, N). انتهى.

 انظر أيضاً 
 تحليل (رياضيات)
 فيزياء رياضية
 مراجع 

تصنيف:خوارزميات الكم
تصنيف:خوارزميات تفكيك الأعداد الصحيحة
تصنيف:علم المعلومات الكمية
تصنيف:مقالات تحوي براهين
تصنيف:تقانات الكم