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

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

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

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

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

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