خوارزمية شور

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

العمليات

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

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

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

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

^ Zyga، Lisa (28 نوفمبر 2014). "New largest number factored on a quantum device is 56,153". Phys.org. Science X Network. مؤرشف من الأصل في 2017-12-11. اطلع عليه بتاريخ 2015-08-04.
^ "Number Field Sieve". wolfram.com. مؤرشف من الأصل في 2018-07-12. اطلع عليه بتاريخ 2015-10-23.
^ 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. مؤرشف من الأصل في 2019-12-18. اطلع عليه بتاريخ 2012-10-23.

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.