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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

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

العمليات[عدل]

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

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

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

المرحلة الكلاسيكية[عدل]

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

انظر أيضاً[عدل]

Nuvola apps edu mathematics-ar.svg هذه بذرة مقالة عن الرياضيات تحتاج للنمو والتحسين، فساهم في إثرائها بالمشاركة في تحريرها.