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