مشكلة التفكيك إلى جداء عوامل أولية

من ويكيبيديا، الموسوعة الحرة

في الرياضيات تفكيك عدد صحيح إلى جداء عوامل أولية, هو كتابة هذا العدد على شكل جداء أعداد أولية, و هذه الكتابة وحيدة. مثلا: تفكيك العدد45 هو 3²·5.

أمثلة أخرى:

11 = 11
25 = 5 × 5 = 5²
125 = 5 × 5 × 5 = 5³
360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5
1 001 = 7 × 11 × 13
1 010 021 = 19 × 53 × 1 003

إذن التفكيك دائما وحيد, و ارتباطا مع المبرهنة الأساسية في الحساب. هذا المشكل له أهمية كبيرة في الرياضيات, في التشفير, في نظرية التعقيد و في الحساب الكمي.

[تحرير] التفكيك إلى أعداد أولية

. 45 = 3²·5,قواسم عدد ما تستنتج من تفكيك هذا العدد. مثلا يعني أن قواسم 45 هي: 3⁰·5⁰, 3⁰·5¹, 3¹·5⁰, 3¹·5¹, 3²·5⁰, و 3²·5¹, أو 1, 5, 3, 15, 9, و 45.

[تحرير] تطبيقات

إذا أخدنا عددين أوليين كبيرين (عدد أرقامهما يفوق 100 رقم) نلاحظ أنه من السهل جدا حساب جدائهما. لكن العكس صعب جدا يعني أن تفكيك الجداء الناتج في وقت حدودي غير معروف لحد الآن. هذا المشكل يطبق في الأنظمة الحديثة في مجال تشفير كلمات المرور و غيرها من المعطيات الحساسة. و في حالة اكتشاف خوارزمية حدودية لحل مشكل التفكيك, ستكون بعض تقنيات التشفير في وضعية صعبة.

[تحرير] بعض الخوارزميات

[تحرير] القسمات المتتابعة

تتم بقسمة العدد على التوالي على الأعداد الأولية و التوقف عند الوصول إلى العدد 1, أو إلى عدد أولي.

[تحرير] التحليل إلى جسم إهليلجي للنسترا (Lenstra)

[تحرير] تقارب المربع

لتفكيك عدد, يتم الاستعانة بمفهوم تقارب المربع, فتفكيك العدد a يرجع إلى إيجاد عددين x و y من مجموعة الأعداد الصحيحة الطبيعية, يحققان المعادلة الآتية: x²+a=y². و يكون (a =(x+y)(x-y