خوارزمية شور

خوارزمية شوور (بالإنجليزية: 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= تم تجاهله (مساعدة)
 
هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. شارك في تحريرها.