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