خوارزمية شور

خوارزمية شوور (بالإنجليزية: 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 نوفمبر 2014)، "New largest number factored on a quantum device is 56,153"، Phys.org، Science X Network، مؤرشف من الأصل في 11 ديسمبر 2017، اطلع عليه بتاريخ 04 أغسطس 2015.
  2. "Number Field Sieve"، wolfram.com، مؤرشف من الأصل في 12 يوليو 2018، اطلع عليه بتاريخ 23 أكتوبر 2015.
  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 أكتوبر 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.
  • بوابة علم الحاسوب
  • بوابة رياضيات
  • بوابة نظرية الأعداد
  • بوابة خوارزميات
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.