الفرق بين المراجعتين لصفحة: «خوارزمية شوور»

من موسوعة العلوم العربية
اذهب إلى التنقل اذهب إلى البحث
ط (١ مراجعة: الصفحات في تصنيف رياضيات)
 
(-)
 
سطر 28: سطر 28:
[[تصنيف:خوارزميات]]
[[تصنيف:خوارزميات]]
[[تصنيف:معلوميات]]
[[تصنيف:معلوميات]]
[[ca:Algorisme de Shor]]
[[de:Shor-Algorithmus]]
[[en:Shor's algorithm]]
[[es:Algoritmo de Shor]]
[[fi:Shorin algoritmi]]
[[fr:Algorithme de Shor]]
[[he:אלגוריתם שור]]
[[it:Algoritmo di fattorizzazione di Shor]]
[[ko:쇼어 알고리즘]]
[[lt:Šoro algoritmas]]
[[pl:Algorytm faktoryzacji Shora]]
[[ru:Алгоритм Шора]]
[[zh:秀爾演算法]]

المراجعة الحالية بتاريخ 15:50، 30 أغسطس 2012

خوارزمية شوور هي خوارزمية كنتيكية ل التفكيك لعدد طبيعي N في زمن O((log N)3) وفي مساحة 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, دالة دورية للدالة الآتية :
    ,
    يعني. أصغر عدد صحيح طبيعي r بحيث .
  5. إذا كان r فردي, نعود للمرحلة 1 1.
  6. إذا كان a r/2 ≡ -1 [N], نعود للمرحلة 1.
  7. قواسم N هي pgcd(ar/2 ± 1, N). انتهى.

اقرأ أيضاً