خوارزمية شوور

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

العمليات

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

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

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

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

1. أخد عدد شبه عشوائي a < N
2. حساب pgcd(a, N). والتي يمكن ايجادها باستعمال خوارزمية اقليدس.
3. إذا كان pgcd(a, N) ≠ 1, إذن سيكون قاسما فعليا N, يعني نهاية الخوارزمية.
4. وألا, استعمال البحث عن الدور (انظر أسفله) لإيجاد r, دالة دورية للدالة الآتية :
   خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x) = a^x\ \mbox{mod}\ N} ,
   يعني. أصغر عدد صحيح طبيعي r بحيث خطأ رياضيات (SVG مع PNG احتياطي (يمكن تمكين MathML عبر المكوِّن الإضافي للمتصفح): رد غير صحيح ("Math extension cannot connect to Restbase.") من الخادم "https://wikimedia.org/api/rest_v1/":): {\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). انتهى.

اقرأ أيضاً

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