محتوا

• مراحل
• قسمت 1 از 3: آزمایش های سادگی
• قسمت 2 از 3: نحوه عملکرد آزمایشات سادگی
• قسمت 3 از 3: استفاده از قضیه باقی مانده چینی
• نکات
• چه چیزی نیاز دارید

اعداد اول اعدادی هستند که فقط بر خود و بر 1 بخش پذیر هستند. به همه اعداد دیگر اعداد مرکب گفته می شود. روشهای زیادی برای تعیین اینکه آیا یک عدد اول است تعیین می شود و همه مزایا و معایب خاص خود را دارند. از یک سو ، برخی از روشها بسیار دقیق هستند ، اما اگر با تعداد زیادی سروکار دارید ، کاملاً پیچیده هستند. از سوی دیگر ، روشهای بسیار سریعتری نیز وجود دارد ، اما می تواند منجر به نتایج نادرست شود. انتخاب روش مناسب بستگی به تعداد اعدادی دارد که با آنها کار می کنید.

مراحل

قسمت 1 از 3: آزمایش های سادگی

توجه داشته باشید: در همه فرمولها n عدد مورد بررسی را نشان می دهد.

1. 1 شمارش تقسیم کننده ها. تقسیم کردن کافی است n به همه اعداد اول از 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 شمارش تقسیم کننده ها. طبق تعریف ، عدد n ساده است فقط اگر بر 2 و اعداد صحیح دیگر به جز 1 و خود قابل تقسیم نباشد. فرمول بالا به شما امکان می دهد مراحل غیر ضروری را حذف کرده و در وقت خود صرفه جویی کنید: به عنوان مثال ، پس از بررسی اینکه آیا یک عدد بر 3 بخش پذیر است ، نیازی به بررسی این نیست که آیا بر 9 بخش پذیر است یا خیر.
   • تابع کف (x) x را به نزدیکترین عدد صحیح کوچکتر یا مساوی x می گرداند.
2. 2 با حساب مدولار آشنا شوید. عمل "x mod y" (mod مخفف کلمه لاتین "modulo" ، یعنی "module") به معنی "تقسیم x بر y و یافتن بقیه است". به عبارت دیگر ، در حساب مدولار ، پس از رسیدن به مقدار معینی ، که نامیده می شود مدول، اعداد دوباره "صفر" می شوند. به عنوان مثال ، ساعت با ماژول 12 شمارش معکوس می کند: 10 ، 11 و 12 ساعت را نشان می دهد ، و سپس به 1 برمی گردد.
   • بسیاری از ماشین حساب ها دارای کلید mod هستند. انتهای این بخش نحوه محاسبه دستی این تابع را برای اعداد بزرگ به شما نشان می دهد.
3. 3 با مشکلات قضیه کوچک فرما آشنا شوید. همه اعدادی که شرایط آزمون برای آنها رعایت نشده است ترکیبی هستند ، اما بقیه اعداد فقط هستند شاید ساده هستند اگر می خواهید از نتایج نادرست جلوگیری کنید ، جستجو کنید n در لیست "اعداد کارمایکل" (اعداد ترکیبی که این آزمایش را برآورده می کند) و "اعداد شبه جنایی فرما" (این اعداد شرایط آزمون را فقط برای برخی مقادیر برآورده می کنند آ).
4. 4 در صورت راحت بودن ، از آزمون میلر رابین استفاده کنید. اگرچه این روش برای محاسبات دستی بسیار مشکل است ، اما اغلب در برنامه های کامپیوتری استفاده می شود. سرعت قابل قبول و خطاهای کمتری نسبت به روش فرما ارائه می دهد. اگر محاسبات بیش از ¼ مقادیر انجام شود ، یک عدد مرکب به عنوان عدد اول در نظر گرفته نمی شود آ... اگر به طور تصادفی مقادیر مختلف را انتخاب کنید آ و برای همه آنها این آزمایش نتیجه مثبتی خواهد داشت ، ما می توانیم با اطمینان نسبتاً بالایی فرض کنیم که n یک عدد اول است
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}}$ حالت 50 = 43
   • ${ displaystyle (3 ^ {25}}$ مد 50 ${ displaystyle * 3 ^ {25}}$ mod 50) mod 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 97
4. 4 یک جدول برای هر MMI به ماژول log2 ایجاد کنید:
   • برای MMI1
     • F (1) = تعداد 2٪ تعداد 1 = 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) mod 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 محاسبه (ارزش 1 * شماره 2 * MMI1 + ارزش 2 * شماره 1 * MMI2)٪ (شماره 1 * شماره 2)
   • پاسخ = (1 * 97 * 27 + 2 * 35 * 61)٪ (97 * 35)
   • پاسخ = (2619 + 4270)٪ 3395
   • پاسخ = 99
6. 6 بررسی کنید که شماره 1 اول نیست
   • محاسبه (پاسخ - ارزش 1) Number شماره 1
   • 99 – 1 % 35 = 28
   • از آنجا که 28 بزرگتر از 0 است ، 35 یک عدد اول نیست.
7. 7 بررسی کنید که شماره 2 اول است.
   • محاسبه (پاسخ - ارزش 2) Number شماره 2
   • 99 – 2 % 97 = 0
   • از آنجا که 0 صفر است ، 97 به احتمال زیاد یک عدد اول است.
8. 8 مراحل 1 تا 7 را حداقل دو بار دیگر تکرار کنید.
   • اگر در مرحله 7 0 دریافت کنید:
     • اگر Number1 اول نیست عدد 1 دیگری استفاده کنید.
     • اگر Number1 اول است از Number1 دیگری استفاده کنید. در این حالت ، شما باید در مراحل 6 و 7 صفر را دریافت کنید.
     • از معنی های مختلف 1 و معنا 2 استفاده کنید.
   • اگر در مرحله 7 به طور مداوم 0 را دریافت می کنید ، به احتمال زیاد عدد 2 اول است.
   • اگر شماره 1 اول نباشد و عدد 2 مقسوم بر شماره 1 باشد ، مراحل 1 تا 7 ممکن است منجر به خطا شود. روش توصیف شده در همه مواردی که هر دو عدد اول باشند کار می کند.
   • دلیل اینکه شما باید مراحل 1 تا 7 را تکرار کنید این است که در برخی موارد ، حتی اگر شماره 1 و شماره 2 اول نیستند ، در مرحله 7 0 (برای یک یا هر دو عدد) دریافت خواهید کرد. این به ندرت اتفاق می افتد.یک عدد 1 دیگر (کامپوزیت) انتخاب کنید ، و اگر شماره 2 اول نباشد ، در مرحله 7 عدد 2 برابر صفر نخواهد بود (مگر در مواردی که عدد 1 مقسوم بر شماره 2 باشد - در اینجا اعداد اول همیشه در مرحله 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، 459، 467، 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
• اگرچه آزمایش نیروی وحشیانه هنگام کار با اعداد بزرگ یک آزمایش خسته کننده است ، اما برای اعداد کوچک کاملاً کارآمد است. حتی در مورد اعداد بزرگ ، با آزمایش تقسیم کننده های کوچک شروع کنید و سپس برای بررسی سادگی اعداد (در صورت عدم یافتن تقسیم کننده های کوچک) به سراغ روشهای پیچیده تری بروید.

چه چیزی نیاز دارید

• کاغذ ، قلم یا کامپیوتر