• 0
مصطفى 36a2

اختبار الرقم الكبير .. هل هو أولي؟

سؤال

بسم الله الرحمن الرحيم
السلام عليكم ورحمة الله وبركاته :
في استكمالنا موضوع البحث عن أكبر عدد أولي .. فقد وصلنا إلى فقرة اختبار أولية الرقم الذي وصلنا إليه ..
كملخص لما وصلنا إليه سابقاً :
مقدمة الموضوع
الخطوة الأولى
ولمعرفة المزيد عن موضوع الأعداد الأولية :
Mersenne
Largets Known Prime
أما بعد : فخطوات الوصول كانت :
1- الوصول إلى أكبر رقم معروف حتى الآن وهو 2^43112609 -1 وذلك بطريقتين : الأولى هي عن طريق البرمجة والثانية عن طريق الرابط التالي :
أكبر رقم أولي (الرابط موجود في الصفحة لأن الرقم حجمه 13 ميغا)
2-الانطلاق من هذا الرقم إلى 2^ الرقم الأولي التالي ل 43112609 وهو 43112621 (عملية بسيطة )
3-اختبار الرقم الذي وصلنا إليه هل هو أولي ؟ ( وهو موضوعنا اليوم )
 

كيف نختبر رقم هل هو أولي أم لا ...
وكما ذكرت في المرة الماضية :
إذاً بقي علينا إيجاد الخوارزمية اللازمة لاختبار رقم بهذا الحجم هل هو أولي ؟؟
وإليكم الخطوات ...
بشكل عام .. لمعرفة أي رقم هل هو أولي أم لا .. يجب أن نختبر قابلية قسمته على كل الأعداد الأولية الأصغر او تساوي جذره ....
مثلاً : لاختبار الرقم 49 هل هو أولي أم لا ...
أولاً نوجد جذره : 7
ثانياً : نوجد الأعداد الأولية الأصغر أو تساوي جذره 2و3و5و7
ثالثاً : نوجد باقي القسمة على 2 ثم 3 ثم 5 ... هل يساوي 0 .. لا نختبره على 7 الباقي 0 إذاً فهو ليس أولي ...
هناك طريقة أخرى بالعكس ..
فوراً نختبره على الأرقام الأولية منذ البداية وعند كل رقم نختبر قابلية القسمة ...
كما يجب أن نختبر إن كان مربع الرقم الأولي أصغر من الرقم الهدف ..
مثال : نختبر الرقم 53
على 2 و 3 و 5 و 7 لايقبل القسمة ونلاحظ أن 7*7 هو 49 إذا يجب الاستمرار
هل يقبل على 11 لا ولكن 11*11 هو 121 وهو أكبر من الرقم الهدف 53 لذلك نتوقف ونعتبره أولياً ..
////////////
هذا بشكل عام ..
ونلاحظ أن العمليات هي :
1-إيجاد الأعداد الأولية من البداية( وهنا سنستخدم العودية بحيث أن إيجاد عدد اولي أكبر من الحد سيتطلب القيام بالخطوات نفسها وهذا هدفنا أصلا)
2-قابلية القسمة
3-التربيع أو الجذر ( حسب الطريقة المستخدمة )



من الخطوات الثلاث المذكورة .. الخطوة التي تمثل التحدي الحقيقي هي قابلية القسمة ...
وكمقدمة بسيطة :
عملية القسمة ( أو النسبة ) هي عملية تهدف لمعرفة عدد مرات احتواء المقام في البسط .. أي أنه لدينا مقسوم ومقسوم عليه ..
وهدف القسمة هو معرفة عدد مرات احتواء المقسوم عليه في المقسوم ...
وعندما يكون عدد مرات الاحتواء هو عدد صحيح نقول أن العدد يقبل القسمة على المقسوم عليه ..
133552486651.png

ويمكننا على هذا الأساس أن نستعيض عن قابلية القسمة بالطرح عدد من المرات وعندما نصل إلى رقم منازله هي نفس منازل المقسوم عليه وهو أصغر من المقسوم عليه ولا يساوي الصفر
نقول أن العدد لا يقبل القسمة على المقسوم عليه ...

1335524869512.png

هذه مقدمة للموضوع أرجو أن ... يكون ذلك كافياً حتى الآن ... للموضوع تتمة بإذن الله تعالى
والسلام عليكم ورحمة الله وبركاته

تم تعديل بواسطه مصطفى 36a2
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

28 إجابة على هذا السؤال .

  • 0

السلام عليكم

بارك الله فيك أخى العزيز مصطفى على كلماتك الجميلة .

لا بد أنك قصدت :الأعداد الأولية ...
قصدت الأعداد الفردية لأن إيجاد الأعداد الأولية تحت الجذر فى كل مرة يتطلب وقت أكبر من القسمة على الأعداد الفردية ولكن إن تمت تخزين هذه الأعداد الأولية حتى لا نحتاج لحسابها دورياً فبالطبع هذا أفضل بكثير من الأعداد الفردية كما تفضلت أنت بالشرح مسبقاً .
جزاك الله خيرا على تشجيعك أخي أحمد ... ربما لم أكن لأصل إلى هنا لولا ذلك ... فالحمد لله ...
هذا من فضل الله علينا , ومن إجتهادك أخى الكريم .

- هل تعلم أن نفس هذا الموضع هو مشوارى مع البرمجة عندما كنت أدرس لغة fortran منذ ثنتان تقريباً , وأخبرنى أحد زملائى فى قسم الرياضيات بجائزة لأكبر عدد أولى يتم التوصل إليه ومن ثم قم بسؤال معيد بالقسم عن كيفية إيجاد الرقم الأولى العادى فقال لى إبحث بنفسك ومن هنا بدأ مشوارى مع البرمجة بدأت فى فى تنفيذ البرنامج وقمت بتحسينة شيئاً فشيئاً ثم تركته , ولهذا أرفقت مشاركة هنا فى المنتدى بهذا الموضوع لعموم الفائدة .

ملاحظة : سأسرح الكود الذي أرفقته في ردي السابق شرحا مفصلا اليوم أو غداً ...مع شرح الخوارزمية ... بإذن الله تعالى ...
بارك الله فيك وجعله فى ميزان حسناتك إن شاء الله .

وفقك الله لما يحب ويرضى

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

بسم الله الرحمن الرحيم

السلام عليكم أخي العزيز أحمد,والسلام عليكم جميعاً ..

لا أريد أن أكون متشائماً ولكن اكتشفت بعد دراسة طويلة للموضوع ككل .. أنه يستحيل .. وأشدد على كلمة "يستحيل " أن نصل إلى الرقم الأولي

بواسطة الخوارزمية الحالية ..

صحيح أننا عملنا كثيراً .. واستمتعنا بوضع خوارزميات للتعامل مع الأرقام الضخمة ..

ولكن .. للأسف الرقم أكبر بكثيييير من أن نوجده حسب معلوماتنا الحالية ..

لماذا ؟؟

سأجيبك ..happy.gif

نعلم ان اختبار أولية الرقم تحتاج اختبار باقي قسمته على جميع الأرقام الأولية الأقل من جذره ...

للأسف تبين أن عدد الأرقام الأولية

الأقل من 10 هو 4

الأقل من 100 هو 25

الأقل من مليار هو حوالي 51مليون

الأقل من 1,000,000,000,000,000,000,000,000 هو

هل أنت مستعد للصدمة ؟؟

18,435,599,767,349,200,867,866

أي أننا يجب أن نقوم ب

18,435,599,767,349,200,867,866

في أسوأ الحالات

وهذا الرقم يستحيل معه ما يلي :

أولاً . يستحيل حفظ هذا العدد من الأرقام ولو استعملنا كل ذواكر العالم

لو أخذ كل رقم بت واحد ستحتاج إلى 1,676,708 تيرا بايت

ثانياً.يستحيل القيام بهذا العدد من الاختبارات ولو انتظرنا ألف عام

لو أخذت كل عملية واحدا بالألف من الثانية سنحتاج 59,936,796 سنة

ولو قمنا بتوزيع العمل على مليون جهاز سنحتاج 58 سنة laugh.giflaugh.giflaugh.giflaugh.giflaugh.giflaugh.giflaugh.gif

ثالثاً. حتى لو كان كل ما ذكرته ممكناً فحتماً ::يستحيل أن نقوم بكل ما سبق بالنسبة لأرقام من 12مليون منزلة

سنخرج عن كوننا بشراً عندها wacko.gifwacko.gif

تخيل أنك ستقوم بعدد من الاختبارات لا يمكنك لفظ رقمه laugh.gif

لا أدري كيف قام بها فريق الGMP ولكن حسب المعلومات التي لدينا ..

يبدو أن الأمر انتهى ..

شكراً لك .. جزيلاً على تشجيعك الدائم ... شكرا للجميع ...smile.gif

نلتقي في مشروع ناجح في المرة القادمة إن شاء الله تعالى ...laugh.gif

والسلام عليكم ورحمة الله وبركاته ...

تحياتي للجميع

تم تعديل بواسطه مصطفى 36a2
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم ورحم الله ,,,

تحية طيبة الى الاخوة الكرام و المناقشة الممتعة 

اود ان اضيف ان اختبار القسمة لتحديد اولوية العدد هو من قبل الميلاد ولا يستخدم حاليا انما توجد خوارزميات احدث بكثير منها ما يعطى نتيجة بدقة yes ,no or maybe و منها ما يعطى بدقة عالية جدا يمكنك البحث عن aks test و elliptic curve و apr test و غيرها من الطرق مع رأيى المتواضع ان التقدم فى دراسة elliptic curves  سيكون المستقبل لتسريع هذا الاختبار 

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

من فضلك سجل دخول لتتمكن من التعليق

ستتمكن من اضافه تعليقات بعد التسجيل



سجل دخولك الان

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .