المحتوى

• خطوات
• جزء 1 من 3: اختبارات البساطة
• جزء 2 من 3: كيف تعمل اختبارات البساطة
• جزء 3 من 3: استخدام نظرية البقية الصينية
• نصائح
• ماذا تحتاج

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

خطوات

جزء 1 من 3: اختبارات البساطة

ملحوظة: بجميع الصيغ ن يشير إلى الرقم المطلوب التحقق منه.

1. 1 حصر القواسم. يكفي أن نقسم ن لجميع الأعداد الأولية من 2 إلى القيمة المقربة (${ displaystyle { sqrt {n}}}$).
2. 2 نظرية فيرما الصغيرة. تحذير: في بعض الأحيان ، سيحدد الاختبار بشكل خاطئ الأرقام المركبة كأعداد أولية ، حتى بالنسبة لجميع قيم a.
   • دعنا نختار عددًا صحيحًا أمثل أن 2 a ≤ n - 1.
   • إذا كان a (mod n) = a (mod n) ، فمن المحتمل أن يكون الرقم أوليًا. إذا لم يتم استيفاء المساواة ، يكون الرقم n مركبًا.
   • تحقق من المساواة المقدمة لقيم متعددة ألزيادة احتمالية أن الرقم الذي يتم اختباره هو بالفعل عدد أولي.
3. 3 اختبار ميلر رابين. تحذير: في بعض الأحيان ، على الرغم من ندرة ذلك ، بالنسبة للقيم المتعددة لـ a ، سيحدد الاختبار بشكل خاطئ الأرقام المركبة كأعداد أولية.
   • أوجد الكميتين s و d على هذا النحو ${ displaystyle n-1 = 2 ^ {s} * d}$.
   • حدد عددًا صحيحًا أ في النطاق 2 a ≤ n - 1.
   • إذا كان a = +1 (mod n) أو -1 (mod n) ، فمن المحتمل أن يكون n هو عدد أولي. في هذه الحالة ، انتقل إلى نتيجة الاختبار. إذا لم تصمد المساواة ، فانتقل إلى الخطوة التالية.
   • مربع إجابتك (${ displaystyle a ^ {2d}}$). إذا حصلت على -1 (mod n) ، فمن المحتمل أن يكون n عددًا أوليًا. في هذه الحالة ، انتقل إلى نتيجة الاختبار. إذا فشلت المساواة ، كرر (${ displaystyle a ^ {4d}}$ وهلم جرا) حتى ${ displaystyle a ^ {2 ^ {s-1} d}}$.
   • إذا في مرحلة ما بعد تربيع رقم آخر غير ${ displaystyle pm 1}$ (mod n) ، لقد حصلت على +1 (mod n) ، لذا n هو رقم مركب. لو ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n) ، إذن n ليس أوليًا.
   • نتيجة الاختبار: إذا نجح n في الاختبار ، كرره للقيم الأخرى ألزيادة الثقة.

جزء 2 من 3: كيف تعمل اختبارات البساطة

1. 1 حصر القواسم. بحكم التعريف ، الرقم ن يكون بسيطًا فقط إذا لم يكن قابلاً للقسمة على 2 والأعداد الصحيحة الأخرى باستثناء 1 ونفسه. تسمح لك الصيغة أعلاه بإزالة الخطوات غير الضرورية وتوفير الوقت: على سبيل المثال ، بعد التحقق مما إذا كان الرقم قابلاً للقسمة على 3 ، ليست هناك حاجة للتحقق مما إذا كان قابلاً للقسمة على 9.
   • الدالة floor (x) تقرِّب x إلى أقرب عدد صحيح أقل من أو يساوي x.
2. 2 تعرف على الحساب النمطي. العملية "x mod y" (mod هي اختصار للكلمة اللاتينية "modulo" ، أي "module") تعني "قسمة x على y وابحث عن الباقي." بعبارة أخرى ، في الحساب النمطي ، عند الوصول إلى قيمة معينة تسمى وحدة، فإن الأرقام "تتحول" إلى الصفر مرة أخرى. على سبيل المثال ، تعد الساعة تنازليًا بالوحدة 12: فهي تعرض 10 و 11 و 12 ساعة ، ثم تعود إلى 1.
   • تحتوي العديد من الآلات الحاسبة على مفتاح تعديل. توضح لك نهاية هذا القسم كيفية حساب هذه الوظيفة يدويًا للأرقام الكبيرة.
3. 3 تعرف على مخاطر نظرية فيرما الصغيرة. جميع الأرقام التي لم تتحقق شروط الاختبار لها هي أرقام مركبة ، لكن باقي الأرقام تكون فقط المحتمل بسيطة. إذا كنت تريد تجنب النتائج غير الصحيحة ، ابحث ن في قائمة "أرقام كارمايكل" ​​(الأرقام المركبة التي تفي بهذا الاختبار) و "أرقام Fermat pseudoprime" (هذه الأرقام تستوفي شروط الاختبار فقط لبعض القيم أ).
4. 4 إذا كان ذلك مناسبًا ، استخدم اختبار ميلر رابين. على الرغم من أن هذه الطريقة مرهقة إلى حد ما بالنسبة للحسابات اليدوية ، إلا أنها تستخدم غالبًا في برامج الكمبيوتر. يوفر سرعة مقبولة وأخطاء أقل من طريقة فيرمات. لن يتم أخذ الرقم المركب كرقم أولي إذا تم إجراء الحسابات لأكثر من قيم أ... إذا اخترت قيمًا مختلفة بشكل عشوائي أ وبالنسبة لهم جميعًا ، سيعطي الاختبار نتيجة إيجابية ، يمكننا أن نفترض بدرجة عالية إلى حد ما من الثقة ذلك ن هو عدد أولي.
5. 5 للأعداد الكبيرة ، استخدم الحساب النمطي. إذا لم يكن لديك آلة حاسبة تعديل سهلة الاستخدام ، أو لم يتم تصميم الآلة الحاسبة للتعامل مع مثل هذه الأرقام الكبيرة ، فاستخدم خصائص الطاقة والحساب المعياري لتسهيل العمليات الحسابية. أدناه مثال على ${ displaystyle 3 ^ {50}}$ نموذج 50:
   • أعد كتابة التعبير بشكل أكثر ملاءمة: ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ تعديل 50. قد تتطلب الحسابات اليدوية المزيد من التبسيط.
   • ${ displaystyle (3 ^ {25} * 3 ^ {25})}$ تعديل 50 = ${ displaystyle (3 ^ {25}}$ وزارة الدفاع 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 50. هنا أخذنا في الاعتبار خاصية الضرب النمطي.
   • ${ displaystyle 3 ^ {25}}$ mod 50 = 43.
   • ${ displaystyle (3 ^ {25}}$ وزارة الدفاع 50 ${ displaystyle * 3 ^ {25}}$ تعديل 50) تعديل 50 = ${ displaystyle (43 * 43)}$ وزارة الدفاع 50.
   • ${ displaystyle = 1849}$ وزارة الدفاع 50.
   • ${ displaystyle = 49}$.

جزء 3 من 3: استخدام نظرية البقية الصينية

1. 1 اختر رقمين. يجب أن يكون أحد الأرقام مركبًا ، ويجب أن يكون الآخر هو بالضبط الرقم الذي تريد اختباره من أجل البساطة.
   • الرقم 1 = 35
   • عدد 2 = 97
2. 2 حدد قيمتين أكبر من الصفر وأقل من الرقمين Number1 و Number2 على التوالي. يجب ألا تكون هذه القيم هي نفسها.
   • القيمة 1 = 1
   • القيمة 2 = 2
3. 3 احسب MMI (مقلوب الضرب الرياضي) للرقم 1 والرقم 2.
   • احسب MMI
     • MMI1 = Number2 ^ -1 Mod Number1
     • MMI2 = Number1 ^ -1 Mod Number2
   • للأعداد الأولية فقط (سيعطي هذا رقمًا للأرقام المركبة ، لكنه لن يكون رقم MMI الخاص به):
     • MMI1 = (Number2 ^ (Number1-2))٪ Number1
     • MMI2 = (Number1 ^ (Number2-2))٪ Number2
   • فمثلا:
     • MMI1 = (97 ^ 33)٪ 35
     • MMI2 = (35 ^ 95)٪ 97
4. 4 قم بإنشاء جدول لكل MMI وصولاً إلى وحدات log2:
   • بالنسبة لـ MMI1
     • F (1) = Number2٪ Number1 = 97٪ 35 = 27
     • F (2) = F (1) * F (1)٪ Number1 = 27 * 27٪ 35 = 29
     • F (4) = F (2) * F (2)٪ Number1 = 29 * 29٪ 35 = 1
     • F (8) = F (4) * F (4)٪ Number1 = 1 * 1٪ 35 = 1
     • F (16) = F (8) * F (8)٪ Number1 = 1 * 1٪ 35 = 1
     • F (32) = F (16) * F (16)٪ Number1 = 1 * 1٪ 35 = 1
   • احسب الأعداد المقترنة 1-2
     • 35-2 = 33 (10001) أساس 2
     • MMI1 = F (33) = F (32) * F (1) تعديل 35
     • MMI1 = F (33) = 1 * 27 نموذج 35
     • MMI1 = 27
   • بالنسبة لـ MMI2
     • F (1) = رقم 1٪ رقم 2 = 35٪ 97 = 35
     • F (2) = F (1) * F (1)٪ Number2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)٪ Number2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)٪ Number2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)٪ Number2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)٪ Number2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)٪ Number2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)٪ Number2 = 35 * 35 mod 97 = 61
   • احسب العدد المقترن 2 - 2
     • 97-2 = 95 = (1011111) أساس 2
     • MMI2 = ((((F (64) * F (16)٪ 97) * F (8)٪ 97) * F (4)٪ 97) * F (2)٪ 97) * F (1)٪ 97)
     • MMI2 = (((((35 * 35)٪ 97) * 61)٪ 97) * 35٪ 97) * 61٪ 97) * 35٪ 97)
     • MMI2 = 61
5. 5 احسب (Value1 * Number2 * MMI1 + Value2 * Number1 * MMI2)٪ (Number1 * Number2)
   • الإجابة = (1 * 97 * 27 + 2 * 35 * 61)٪ (97 * 35)
   • الإجابة = (2619 + 4270)٪ 3395
   • الجواب = 99
6. 6 تأكد من أن Number1 ليس عددًا أوليًا
   • احسب (الإجابة - القيمة 1)٪ Number1
   • 99 – 1 % 35 = 28
   • بما أن 28 أكبر من 0 ، فإن 35 ليس عددًا أوليًا.
7. 7 تأكد من أن Number2 هو عدد أولي.
   • احسب (الإجابة - القيمة 2)٪ Number2
   • 99 – 2 % 97 = 0
   • بما أن 0 هو 0 ، فمن المرجح أن 97 عدد أولي.
8. 8 كرر الخطوات من 1 إلى 7 مرتين أخريين على الأقل.
   • إذا حصلت على 0 في الخطوة 7:
     • استخدم Number1 مختلفًا إذا لم يكن Number1 أوليًا.
     • استخدم Number1 آخر إذا كان Number1 أوليًا. في هذه الحالة ، يجب أن تحصل على 0 في الخطوتين 6 و 7.
     • استخدم المعنى المعنى 1 والمعنى 2.
   • إذا كنت تحصل في الخطوة 7 على 0 باستمرار ، فمن المحتمل جدًا أن يكون الرقم 2 أولًا.
   • قد تؤدي الخطوات من 1 إلى 7 إلى حدوث خطأ إذا لم يكن Number1 أوليًا وكان Number2 مقسومًا على Number1. تعمل الطريقة الموصوفة في جميع الحالات عندما يكون كلا الرقمين أوليين.
   • سبب احتياجك لتكرار الخطوات من 1 إلى 7 هو أنه في بعض الحالات ، حتى إذا لم يكن الرقم 1 والرقم 2 أوليًا ، فستحصل في الخطوة 7 على 0 (لأحد الرقمين أو كلاهما). نادرا ما يحدث هذا.اختر رقمًا آخر (مركب) ، وإذا لم يكن Number2 أوليًا ، فلن يساوي Number2 صفرًا في الخطوة 7 (باستثناء الحالة التي يكون فيها Number1 مقسومًا على Number2 - هنا ستساوي الأعداد الأولية صفرًا دائمًا في الخطوة 7).

نصائح

• الأعداد الأولية من 168 إلى 1000: 2 ، 3 ، 5 ، 7 ، 11 ، 13 ، 17 ، 19 ، 23 ، 29 ، 31 ، 37 ، 41 ، 43 ، 47 ، 53 ، 59 ، 61 ، 67 ، 71 ، 73 ، 79 ، 83 ، 89 ، 97 ، 101 ، 103 ، 107 ، 109 ، 113 ، 127 ، 131 ، 137 ، 139 ، 149 ، 151 ، 157 ، 163 ، 167 ، 173 ، 179 ، 181 ، 191 ، 193 ، 197 ، 199 ، 211 ، 223 ، 227 ، 229 ، 233 ، 239 ، 241 ، 251 ، 257 ، 263 ، 269 ، 271 ، 277 ، 281 ، 283 ، 293 ، 307 ، 311 ، 313 ، 317 ، 331 ، 337 ، 347 ، 349 ، 353 ، 359 ، 367 ، 373 ، 379 ، 383 ، 389 ، 397 ، 401 ، 409 ، 419 ، 421 ، 431 ، 433 ، 439 ، 443 ، 449 ، 457 ، 461 ، 463 ، 467 ، 479 ، 487 ، 491 ، 499 ، 503 ، 509 ، 521 ، 523 ، 541 ، 547 ، 557 ، 563 ، 569 ، 571 ، 577 ، 587 ، 593 ، 599 ، 601 ، 607 ، 613 ، 617 ، 619 ، 631 ، 641 ، 643 ، 647 ، 653 ، 659 ، 661 ، 673 ، 677 ، 683 ، 691 ، 701 ، 709 ، 719 ، 727 ، 733 ، 739 ، 743 ، 751 ، 757 ، 761 ، 769 ، 773 ، 787 ، 797 ، 809 ، 811 ، 821 ، 823 ، 827 ، 829 ، 839 ، 853 ، 857 ، 859 ، 863 ، 877 ، 881 ، 883 ، 887 ، 907 ، 911 ، 919 ، 929 ، 937 ، 941 ، 947 ، 953 ، 967 ، 971 ، 977 ، 983 ، 991 ، 997.
• على الرغم من أن اختبار القوة الغاشمة هو اختبار شاق عند العمل بأعداد كبيرة ، إلا أنه فعال للغاية بالنسبة للأعداد الصغيرة. حتى في حالة الأعداد الكبيرة ، ابدأ باختبار قواسم صغيرة ، ثم انتقل إلى طرق أكثر تعقيدًا للتحقق من بساطة الأرقام (إذا لم يتم العثور على قواسم صغيرة).

ماذا تحتاج

• ورق أو قلم أو كمبيوتر