تحليل عدد صحيح إلى عوامل

في نظرية الأعداد، التحليل إلى العوامل[1] أو تحليل العدد الصحيح أو التفكيك إلى عوامل أولية، هو عملية تفكيكه إلى جداء عوامله الأولية، أي كتابة هذا العدد غير الأولي على شكل جداء أعداد أولية، بحيث يكون حاصل ضربها مساوٍ للعدد الأصلي. مثلا: تحليل العدد 45 هو 3·3·5 أي 32·5.

معضلات لم تحلحل بعد في علم الحاسوب:

هل يمكن تحليل عدد طبيعي إلى عوامل في وقت يتناسب مع قيم متعددة حدود على حاسوب عادي ؟

(لمزيد من المعضلات غير المحلولة (أو المحلحلة) في علم الحاسوب).
مثال توضيحي لتحليل عدد صحيح،
أي أن 864 = 25 × 33.

أمثلة أخرى:

11 = 11
25 = 5 × 5 = 52
125 = 5 × 5 × 5 = 53
360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 5
1001 = 7 × 11 × 13
1010021 = 17 × 19 × 53 × 59

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

التفكيك إلى أعداد أولية

. 45 = 32·5 قواسم عدد ما تستنتج من تفكيك هذا العدد. مثلا يعني أن قواسم 45 هي: 30·50, 30·51, 31·50, 31·51, 32·50, و 32·51, أو 1, 5, 3, 15, 9, و 45.

تطبيقات

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

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

هناك طرق عديدة تستعمل لتحليل الأعداد الصحيحة، خصوصا عندما يكون العدد كبيرا.

القسمات المتتابعة

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


مثال:
لتحليل العدد الصحيح 180

العدد وناتج القسمة عدد أولي مقسوم عليه
1802
902
453
153
55
1

أي أن 180 = 22·32·51

التحليل باستعمال منحنى لنسترا الإهليلجي

انظر إلى تحليل عدد صحيح باستعمال منحنى لنسترا الإهليلجي.

تقارب المربع

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

مراجع
  1. قاموس المورد، البعلكي، بيروت، لبنان.

انظر أيضًا
  • بوابة رياضيات
  • بوابة علم الحاسوب
  • بوابة نظرية الأعداد
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.