أحد الأسئلة الرئيسية في الرياضيات هو التحقق مما إذا كان رقم معين بسيطا أم مركبا. العدد الأولي هو عدد طبيعي أكبر من واحد ، وهو قابل للقسمة فقط على نفسه وعلى 1. من المهم أن تكون قادرا على التحقق من الأرقام من أجل البساطة ، لأن هذا هو أساس العديد من الخوارزميات الرياضية وأنظمة التشفير.
هناك العديد من الخوارزميات للتحقق من الأرقام من أجل البساطة. واحدة من أبسط الخوارزميات وأكثرها فعالية هي خوارزمية فرز المقسومات. تتكون هذه الخوارزمية من التحقق مما إذا كان الرقم قابلا للقسمة بدون الباقي على جميع الأرقام التي تبدأ من 2 إلى جذر الرقم نفسه. إذا كان الرقم قابلا للقسمة على رقم واحد على الأقل بدون باقي ، فهو مركب.
على سبيل المثال ، إذا أردنا التحقق من الرقم 17 من أجل البساطة ، فسنقوم بالتحقق مما إذا كان قابلا للقسمة بدون الباقي على جميع الأرقام من 2 إلى 4 (جذر 17 مقربا لأسفل). إذا كان قابلا للقسمة ، فسيكون الرقم 17 مركبا ، وإلا فسيكون بسيطا.
خوارزمية فرز المقسومات بسيطة للغاية وفعالة للتحقق من الأرقام من أجل البساطة. ومع ذلك ، عند العمل بأعداد كبيرة جدا ، قد يكون من الضروري استخدام خوارزميات أكثر تعقيدا ، مثل اختبار فيرما أو اختبار ميلر رابين ، مما يسمح لك بالتحقق بسرعة من الأرقام بحثا عن البساطة مع احتمال كبير.
- ما هو عدد أولي?
- لماذا أحتاج إلى التحقق من الرقم بحثا عن البساطة?
- خوارزميات للتحقق من بساطة الأرقام
- خوارزمية لفرز القواسم
- خوارزمية لاستخدام غربال إراتوستينس
- خوارزمية فيرما
- خوارزمية ميلر رابين
- التطبيق العملي للخوارزميات للتحقق من بساطة الأرقام
- رسا القرصنة
- سؤال وجواب
- كيف يمكنني التحقق مما إذا كان الرقم هو رئيس الوزراء?
- ما هي الخوارزميات الأخرى المستخدمة للتحقق من الأرقام من أجل البساطة?
- الخوارزمية التي هي الأكثر فعالية للتحقق من عدد للبساطة?
ما هو عدد أولي?
العدد الأولي هو عدد طبيعي أكبر من واحد وله قاسمان مختلفان فقط: واحد ونفسه. بمعنى آخر ، لا يقبل العدد الأولي القسمة تماما على أي رقم طبيعي باستثناء واحد وهو نفسه.
على سبيل المثال ، الأرقام 2, 3, 5, 7, 11, 13 و 17 هي الأعداد الأولية ، لأن لديهم اثنين فقط من القواسم-1 والرقم نفسه. من ناحية أخرى ، الرقم 4 ليس بسيطا ، لأنه مقسم بالكامل إلى 1 و 2 و 4.
مجموعة الأعداد الأولية لانهائية. وقد ثبت ذلك من قبل إقليدس حوالي 300 قبل الميلاد. تلعب الأعداد الأولية دورا مهما في نظرية الأعداد وتستخدم في مجالات مختلفة مثل التشفير وخوارزميات الكمبيوتر والنماذج الرياضية.
لماذا أحتاج إلى التحقق من الرقم بحثا عن البساطة?
يعد التحقق من رقم للبساطة مهمة مهمة في الرياضيات وعلوم الكمبيوتر. يتيح لك فهم الأعداد الأولية والخوارزميات لتحديدها حل العديد من المشكلات وتطبيق طرق مختلفة في مختلف مجالات العلوم والتكنولوجيا.
الأعداد الأولية هي أعداد طبيعية أكبر من 1 لها مقسومان فقط: 1 والرقم نفسه. على سبيل المثال ، الأرقام 2, 3, 5, 7, 11, 13 إنها بسيطة ، حيث لا يمكن تقسيمها إلا على 1 والرقم نفسه.
يعد التحقق من رقم للبساطة أمرا ضروريا في العديد من الخوارزميات والمهام:
- تشفير البيانات: تستخدم بعض خوارزميات التشفير الأعداد الأولية لإنشاء المفاتيح. إذا لم يكن الرقم أوليا ، فقد يؤدي ذلك إلى ثغرة أمنية في التشفير.
- توليد الأعداد الأولية: في المهام المتعلقة بتوليد الأعداد الأولية ، من الضروري أحيانا التحقق مما إذا كان الرقم أوليا قبل استخدامه.
- تحسين الخوارزميات: في بعض الخوارزميات ، مثل البحث عن الأعداد الأولية أو أرقام العوملة ، من الضروري التحقق من بساطة الأرقام. يمكن أن يساعد ذلك في تقليل وقت تنفيذ الخوارزميات.
يعد التحقق من رقم للبساطة عملية أساسية ويستخدم في مختلف مجالات العلوم والرياضيات. يتيح لك فهم الأعداد الأولية والخوارزميات لتحديدها حل المشكلات المعقدة وإنشاء خوارزميات فعالة.
خوارزميات للتحقق من بساطة الأرقام
يعد التحقق من الأرقام بحثا عن البساطة مهمة مهمة في نظرية الأعداد والتشفير. هناك العديد من الخوارزميات لتحديد ما إذا كان الرقم بسيطا أم مركبا.
- القوة الغاشمة من القواسم
- اختبار المزرعة
- نظرية فيرما الصغيرة
- اختبار ميلر رابين
- غربال إراتوستينس
- خوارزمية لوكاس لومير
الطريقة الأولى والأبسط هي التكرار على قواسم الرقم. لعدد معين ن ، جميع الأرقام من 2 إلى ن-1 يتم تكرارها ، ويتم التحقق مما إذا كان ن يقبل القسمة عليها بدون الباقي. إذا كان أحد الأرقام على الأقل مقسوما ، فإن الرقم ن مركب. ومع ذلك ، فإن هذه الطريقة غير فعالة لأن تعقيدها هو س(ن).
يعتمد اختبار فيرما على نظرية فيرما الصغيرة: إذا ص هو عدد أولي ، ثم لأي عدد صحيح أ لا يقبل القسمة على ص ، المساواة أ^(ص-1) holds 1 (وزارة الدفاع ص) يحمل. الاختبار هو تطبيق هذه النظرية على قيمة عشوائية من أ. إذا استمرت المساواة ، فإن الرقم ص من المحتمل أن يكون أوليا. ومع ذلك ، قد يعطي هذا الاختبار نتائج إيجابية خاطئة للأرقام المركبة.
اختبار ميلر رابين هو اختبار بساطة إثباتية. يعتمد على الفكرة التالية: إذا ص هو رقم أولي ، ثم لأي عدد صحيح أ لا يقبل القسمة على ص ، المساواة التالية تحمل: أ^(ص-1) 1 1 (وزارة الدفاع ص). يتكون الاختبار من تطبيق هذه النظرية على عدة أرقام أ. إذا كانت المساواة تنطبق على جميع الأرقام ، فإن الرقم ص من المحتمل أن يكون أوليا. ومع ذلك ، يمكن أن يعطي هذا الاختبار أيضا نتائج إيجابية خاطئة للأرقام المركبة.
غربال إراتوستينس هو خوارزمية للعثور على جميع الأعداد الأولية حتى رقم معين ن. يعمل على مبدأ الاستبعاد. أولا ، يتم إنشاء قائمة بالأرقام من 2 إلى ن ، ثم بدءا من الرقم 2 ، يتم استبعاد جميع الأرقام التي تعد مضاعفات الرقم الحالي بالتتابع. نتيجة لذلك ، تبقى الأعداد الأولية فقط.
تم تصميم خوارزمية لوكاس-لومير لاختبار أرقام ميرسين للبساطة. أرقام ميرسين لها النموذج 2^ص-1 ، أين ص هو رقم أولي. تعتمد خوارزمية لوكاس لومير على الصيغة المتكررة التالية: س[أنا] = (س[أنا-1]^2 — 2) وزارة الدفاع م ، أين م = 2^ف — 1. إذا كان التسلسل س [أنا] يبدأ بـ 4 بالنسبة إلى معين ص وجميع العناصر اللاحقة هي 0 ، ثم الرقم ميرسين بسيط.
يعتمد اختيار الخوارزمية على دقة التحقق المطلوبة ووقت التنفيذ. من المهم اختيار الخوارزمية المثلى في كل حالة.
خوارزمية لفرز القواسم
خوارزمية فرز المقسومات هي أبسط طريقة للتحقق مما إذا كان الرقم أوليا.
- ابدأ بالرقم 2 ، لأن 1 هو المقسوم عليه لأي رقم.
- تحقق مما إذا كان الرقم المحدد مقسوما على الرقم الذي يتم التحقق منه.
- إذا كان الأمر كذلك ، فإن الرقم ليس أوليا ، وإلا استمر في التحقق من الأرقام التالية.
- كرر الخطوتين 2 و 3 حتى تتحقق من جميع الأرقام من 2 إلى ن/2.
- إذا تم العثور على عدد من غير المقسومات أثناء هذه العملية ، فسيكون الرقم أوليا.
خوارزمية فرز المقسوم عليه بطيئة بالنسبة للأعداد الكبيرة ، ولكنها سهلة التنفيذ وفعالة بما يكفي للتحقق من الأعداد الصغيرة.
خوارزمية لاستخدام غربال إراتوستينس
غربال إراتوستينس هو خوارزمية تستخدم لتحديد جميع الأعداد الأولية في نطاق معين. تم تطويره من قبل عالم الرياضيات اليوناني إراتوستينس حوالي 240 قبل الميلاد.
خوارزمية غربال إراتوستينس يعمل وفقا للمبدأ التالي:
- إنشاء قائمة من الأرقام من 2 إلى ن ، حيث ن هو الرقم الذي تريد اختبار البساطة.
- ابدأ بالرقم الأول في القائمة (2).
- وضع علامة على أنها رئيس الوزراء وإزالة جميع مضاعفاته من القائمة.
- انتقل إلى الرقم التالي غير المسمى وكرر الخطوات من 3 إلى 4 حتى تتصفح جميع الأرقام الموجودة في القائمة.
- الأرقام المميزة التي تبقى في القائمة هي أعداد أولية.
تكمن ميزة غربال إراتوستينس في فعاليته. الخوارزمية لها تعقيد ا (ن سجل سجل ن) ، أين ن هو الرقم الذي يتم البحث فيه عن الأعداد الأولية. نتيجة لذلك ، يعمل غربال إراتوستينس بشكل أسرع من العديد من الخوارزميات الأخرى للتحقق من بساطة الأرقام.
يوجد أدناه جدول يوضح تطبيق خوارزمية غربال إراتوستينس للعثور على جميع الأعداد الأولية في النطاق من 2 إلى 30:
| العدد | بسيطة |
|---|---|
| 2 | نعم |
| 3 | نعم |
| 4 | لا |
| 5 | نعم |
| 6 | لا |
| 7 | نعم |
| 8 | لا |
| 9 | لا |
| 10 | لا |
| 11 | نعم |
| 12 | لا |
| 13 | نعم |
| 14 | لا |
| 15 | لا |
| 16 | لا |
| 17 | نعم |
| 18 | لا |
| 19 | نعم |
| 20 | لا |
| 21 | لا |
| 22 | لا |
| 23 | نعم |
| 24 | لا |
| 25 | لا |
| 26 | لا |
| 27 | لا |
| 28 | لا |
| 29 | نعم |
| 30 | لا |
كما يتضح من الجدول أعلاه ، يتم تمييز الأرقام الأولية على أنها "نعم" ، بينما يتم تمييز الأرقام المركبة على أنها "لا". وهكذا ، فإن غربال إراتوستينس يسمح لك بسرعة وكفاءة تحديد الأعداد الأولية في نطاق معين.
خوارزمية فيرما
خوارزمية فيرما هي طريقة تسمح لك بالتحقق مما إذا كان رقم معين بسيطا أم مركبا. تعتمد الخوارزمية على نظرية فيرما ، والتي تنص على أنه إذا كان الرقم ن هو رئيس الوزراء ، ثم لأي أ أين 1 a أ < ن ، أ^(ن-1) mod 1 وزارة الدفاع ن.
للتحقق من الرقم ن باستخدام خوارزمية فيرما ، تحتاج إلى تحديد رقم عشوائي أ وحساب أ^(ن-1) وزارة الدفاع ن. إذا كانت النتيجة لا تساوي 1 ، فإن الرقم ن مركب تماما ، ولكن الحصول على نتيجة تساوي 1 لا يضمن أن الرقم ن هو رئيس الوزراء.
خوارزمية فيرما ليست اختبارا كاملا للبساطة ، ولكن بساطتها وكفاءتها النسبية تجعلها مفيدة للتحقق بسرعة من بساطة الأعداد الكبيرة.
ومع ذلك ، تجدر الإشارة إلى أن خوارزمية فيرما لها قيود ، ويمكن أن تعطي نتائج غير صحيحة لبعض الأرقام ، ما يسمى بالأرقام الزائفة البسيطة. لذلك ، قبل استخدام خوارزمية فيرما ، من المهم مراعاة هذه القيود واستخدامها بحذر.
خوارزمية ميلر رابين
خوارزمية ميلر رابين هي خوارزمية احتمالية للتحقق من رقم للبساطة. يعتمد على استخدام خصائص الأعداد الأولية ويسمح لك بتحديد ما إذا كان الرقم أوليا مع احتمال حدوث خطأ قريب من الصفر.
الفكرة الرئيسية لخوارزمية ميلر رابين هي أنه إذا كان الرقم ن هو رئيس الوزراء ، ثم لأي عدد صحيح أ من المقطع [2, ن - 2] ما يلي يحمل:
- إذا كان الرقم ن هو رئيس الوزراء ، فإنه يفي بالشرط:
- إذا كان الرقم ن هو رئيس و ن > 2 ، ثم لأي عدد صحيح أ من المقطع [2, ن-2] إما أن يكون الشرط راضيا:
- إذا كان الرقم ن مركب ، ثم بالنسبة لبعض الأعداد الصحيحة أ من المقطع [2, ن-2] ما يلي صحيح:
أن - 1 1 1 (وزارة الدفاع ن) |
أن - 1 1 1 (وزارة الدفاع ن) |
أ (ن-1) / 2 1 1 (وزارة الدفاع ن) |
أ (ن-1)/2 ≡ -1 (وزارة الدفاع ن) |
أ (ن-1) / 2 -1 (وزارة الدفاع ن) |
تستخدم خوارزمية ميلر رابين طريقة التربيع المتكرر لتقليل عدد عمليات الأس.
لتحديد بساطة الرقم ن ، تستخدم خوارزمية ميلر رابين تحلل الرقم ن - 1 من النموذج ن-1 = 2س * د ، أين س و د هي أعداد صحيحة موجبة.
- يتم تحديد عدد صحيح عشوائي أ من الفاصل الزمني [2 ، ن-2].
- قيم إعلان وزارة الدفاع ن, ا (2د) وزارة الدفاع ن,...، أ (2 ثانية*د) وزارة الدفاع ن تحسب.
- إذا كان واحد منهم على الأقل لا يساوي 1 ولا يساوي ن-1 ، ثم الرقم ن مركب.
- إذا كانت جميع القيم تساوي 1 ، فإن الرقم ن هو رئيس الوزراء.
- إذا كان في تسلسل إعلان وزارة الدفاع ن, ا (2د) وزارة الدفاع ن,...، أ (2 ثانية*د) وزارة الدفاع ن هناك قيمة تساوي ن-1 ، ثم الرقم ن هو رئيس الوزراء مع احتمال خطأ يساوي 1/4 ثانية.
تعمل خوارزمية ميلر-رابين مع أي رقم وتحدد الأرقام بكفاءة من أجل البساطة ، ولديها احتمال ضعيف للخطأ ، ولكنها لا تعطي نتيجة دقيقة تماما.
التطبيق العملي للخوارزميات للتحقق من بساطة الأرقام
تعد خوارزميات التحقق من بساطة الأرقام أداة مهمة في مجال الرياضيات والبرمجة الخوارزمية. يتم استخدامها في مهام مختلفة ولها مجموعة واسعة من التطبيقات العملية.
يعد التشفير أحد التطبيقات العملية الرئيسية للخوارزميات للتحقق من بساطة الأرقام. في التشفير ، تلعب الأعداد الأولية دورا مهما لأنها أساس العديد من خوارزميات التشفير. على سبيل المثال ، في خوارزمية رسا ، وتستخدم الأعداد الأولية لتوليد مفاتيح وتشفير المعلومات.
تستخدم خوارزميات التحقق من بساطة الأرقام أيضا في مشكلات التحسين مثل تحليل الأرقام والبحث عن الأعداد الأولية من نوع معين. إنها تساعد في العثور على الأعداد الأولية التي يمكن أن تكون بمثابة أساس لخوارزميات التحليل الفعال أو العمليات الحسابية الأخرى.
أحد الأمثلة العملية لاستخدام الخوارزميات للتحقق من بساطة الأرقام هو توليد أعداد أولية كبيرة في أنظمة التشفير. تعمل الأعداد الأولية الكبيرة كأساس لإنشاء مفاتيح آمنة وتشفير البيانات.
تطبيق عملي آخر للخوارزميات للتحقق من بساطة الأرقام هو اختبار ميلر رابين. يستخدم هذا الاختبار لاختبار الأرقام من أجل البساطة في خوارزميات التشفير المختلفة مثل رسا والجمال.
خاتمة:
- خوارزميات للتحقق من بساطة الأرقام لديها مجموعة واسعة من التطبيقات العملية.
- يتم استخدامها في التشفير لإنشاء المفاتيح وتشفير المعلومات.
- تستخدم خوارزميات التحقق من بساطة الأرقام في التحسين والبحث عن الأعداد الأولية.
- تشمل الأمثلة العملية لاستخدام الخوارزميات للتحقق من بساطة الأرقام توليد الأعداد الأولية الكبيرة واستخدام اختبار ميلر رابين.
رسا القرصنة
(ريفست-شامير-أدلمان) هي واحدة من الخوارزميات الأكثر شيوعا لتشفير وتوقيع البيانات في التشفير. لأنه يقوم على صعوبة العوملة أعداد صحيحة كبيرة. ومع ذلك ، إذا كان التنفيذ غير صحيح أو يتم استخدام مفاتيح ضعيفة ، يمكنك محاولة للقضاء رسا.
يتم تنفيذ القرصنة رسا من خلال محاولة تحليل عدد كبير يسمى وحدة نمطية. إذا تمكن المتسلل من العثور على العوامل الأولية لهذا الرقم ، فسيكون قادرا على حساب المفتاح الخاص والوصول إلى البيانات المشفرة.
هناك عدة طرق للقضاء على رسا ، بما في ذلك هجوم القوة الغاشمة ، وطريقة تحليل عدد فيرما ، وهجوم التحلل المستمر. ومع ذلك ، تتطلب هذه الأساليب موارد الحوسبة كبيرة والوقت ، وخاصة عند استخدام مفاتيح طويلة.
للحماية من القرصنة رسا ، فمن المستحسن استخدام وحدات كبيرة بما فيه الكفاية ومفاتيح لتعقيد عملية التحليل إلى عوامل. من المهم أيضا استخدام أرقام عشوائية زائفة آمنة بشكل مشفر عند إنشاء المفاتيح وتنفيذ خوارزميات التشفير وتوقيع البيانات بشكل صحيح.
بشكل عام ، لا تزال رسا خوارزمية موثوقة لتشفير وتوقيع البيانات باستخدام المفاتيح الصحيحة والتنفيذ الجيد. ومع ذلك ، مع ظهور أجهزة الكمبيوتر الكمومية ، وهناك تهديدات محتملة من رسا القرصنة باستخدام خوارزمية الشاطئ.
سؤال وجواب
كيف يمكنني التحقق مما إذا كان الرقم هو رئيس الوزراء?
هناك عدة طرق للتحقق من عدد للبساطة. إحدى هذه الطرق هي استخدام خوارزمية لفرز قواسم الرقم. للقيام بذلك ، يجب عليك تقسيم الرقم باستمرار على جميع الأعداد الصحيحة ، بدءا من 2 وتنتهي بجذر الرقم نفسه. إذا تم العثور على مقسوم عليه بدون باقي أثناء عملية القسمة ، فإن الرقم ليس أوليا. إذا لم تقسم جميع القواسم الرقم بدون الباقي ، فإن الرقم يكون أوليا.
ما هي الخوارزميات الأخرى المستخدمة للتحقق من الأرقام من أجل البساطة?
بالإضافة إلى خوارزمية فرز قواسم الرقم ، يتم استخدام خوارزميات أخرى على نطاق واسع. على سبيل المثال ، خوارزمية إراتوستينس ، والذي يسمح لك للعثور على جميع الأعداد الأولية تصل إلى عدد معين. هناك أيضا خوارزميات تعتمد على اختبارات البساطة ، مثل اختبار فيرما واختبار ميلر رابين.
الخوارزمية التي هي الأكثر فعالية للتحقق من عدد للبساطة?
تعتبر الخوارزمية الأكثر فعالية للتحقق من الأرقام من أجل البساطة هي خوارزمية غربال إراتوستينس. تسمح لك هذه الخوارزمية بالعثور على جميع الأعداد الأولية حتى رقم معين ولها تعقيد س(ن سجل سجل ن) ، مما يجعلها سريعة وفعالة للغاية.