خوارزمية شور

خوارزمية شوور (بالإنجليزية: Shor's algorithm)‏ هي خوارزمية لتفكيك عدد طبيعي N في زمن O((log N)3) وفي مساحة (O(log N.[1][2][3] تحمل هاته الخوارزمية اسم بيتر شور.

العمليات

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

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

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

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

انظر أيضاً

مراجع
  1. Zyga, Lisa (28 November 2014). "New largest number factored on a quantum device is 56,153". Phys.org. Science X Network. مؤرشف من الأصل في 11 ديسمبر 2017. اطلع عليه بتاريخ 04 أغسطس 2015. الوسيط |CitationClass= تم تجاهله (مساعدة)
  2. "Number Field Sieve". wolfram.com. مؤرشف من الأصل في 12 يوليو 2018. اطلع عليه بتاريخ 23 أكتوبر 2015. الوسيط |CitationClass= تم تجاهله (مساعدة)
  3. Martín-López, Enrique; Enrique Martín-López; Anthony Laing; Thomas Lawson; Roberto Alvarez; Xiao-Qi Zhou; Jeremy L. O'Brien (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. مؤرشف من الأصل في 18 ديسمبر 2019. اطلع عليه بتاريخ 23 أكتوبر 2012. الوسيط |CitationClass= تم تجاهله (مساعدة)
    • بوابة علم الحاسوب
    • بوابة رياضيات
    • بوابة نظرية الأعداد
    • بوابة خوارزميات
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.