مشكلة التفكيك إلى جداء عوامل أولية
في الرياضيات تفكيك عدد سليم إلى جداء عوامل أولية, هوكتابة هذا العدد على شكل جداء أعداد أولية, وهذه الكتابة وحيدة. مثلا: تفكيك العدد45 هو32·5.
أمثلة أخرى:
11 = 11
25 =خمسة ×خمسة = 52
125 =خمسة ×خمسة ×خمسة = 53
360 = 2 × 2 × 2 × ثلاثة × ثلاثة ×خمسة = 23 × 32 ×خمسة
1 001 =سبعة × 11 × 13
1 010 021 = 19 × 53 × 1 003
إذن التفكيك دائما وحيد, وارتباطا مع المبرهنة الأساسية في الحساب. هذا المشكل له أهمية كبيرة في الرياضيات, في التشفير, في نظرية التعقيد وفي الحساب الكمي.
التفكيك إلى أعداد أولية
. 45 = 32·5,قواسم عدد ما تستنتج من تفكيك هذا العدد. مثلا يعني حتى قواسم 45 هي: 30·50, 30·51, 31·50, 31·51, 32·50, و32·51, أو1, 5, 3, 15, 9, و45.
تطبيقات
إذا أخدنا عددين أوليين كبيرين (عدد أرقامهما يفوق 100 رقم) نلاحظ أنه من السهل جدا حساب جدائهما. لكن العكس قاسي جدا يعني حتى تفكيك الجداء الناتج في وقت حدودي غير معروف لحد الآن. هذا المشكل يطبق في الأنظمة الحديثة في مجال تشفير حدثات المرور وغيرها من المعطيات الحساسة. وفي حالة اكتشاف خوارزمية حدودية لحل مأزق التفكيك, ستكون بعض تقنيات التشفير في وضعية صعبة.
بعض الخوارزميات
القسمات المتتابعة
تتم بقسمة العدد على التوالي على الأعداد الأولية والتوقف عند الوصول إلى العدد 1, أوإلى عدد أولي.
التحليل إلى جسم إهليلجي للنسترا (Lenstra)
تقارب المربع
لتفكيك عدد, يتم الاستعانة بمفهوم تقارب المربع, فتفكيك العدد a يرجع إلى إيجاد عددين x وy من مجموعة الأعداد السليمة الطبيعية, يحققان المعادلة الآتية: x²+a=y². وقد يكون (a =(x+y)(x-y
خوارزمية شوور
انظر خوارزمية شوور.
