Wko

Hvordan at kontrollere, om et tal er et primtal

Der er flere metoder til at teste primtal af heltal. Det bedste valg afhænger af omstændighederne. Nogle af de metoder er hurtigere end andre, mens nogle populære tests er faktisk kun probabilistiske algoritmer, der vil lejlighedsvist fejlagtigt karakterisere et tal som prime eller composite. Jo hurtigere metoder er primtal tests, ikke faktorisering algoritmer, så selv om de viser et tal for at være sammensat, de afslører noget om dets primfaktorer. Denne artikel vil hjælpe dig til at udforske et par af de metoder.

Steps

Hvordan at kontrollere, om et tal er et primtal. Trial division er den enkleste test for primtal.
Hvordan at kontrollere, om et tal er et primtal. Trial division er den enkleste test for primtal.

Trial division

  1. 1
    Trial division er den enkleste test for primtal. Den er baseret på definitionen af ​​et primtal. En række er et primtal, hvis det ikke har nogen divisorer andre end sig selv og én.
  2. 2
    Lad n være det nummer, du vil teste.
  3. 3
    Divider n med 2.. Hvis resultatet er et heltal, så er n ikke primtal fordi 2 er en faktor n. Kig på det sidste ciffer, og hvis det er et lige tal, er det deleligt med 2.. Hvis ikke, fortsætter.
  4. 4
    Divider n med 3.. Hvis resultatet er en, så er n ikke prime fordi 3 er en faktor n. Hvis ikke, fortsætter.
  5. 5
    Fortsæt dividere n af hver tal mellem 2 og n 1/2 inklusive. Hvis nogen af dem deler ligeligt, så n er ikke prime, fordi du fandt en faktor. Hvis n har ingen faktorer mindre end dens kvadratroden, så n er et primtal. Det er tilstrækkeligt at kontrollere kun for divisorer mindre end eller lig med n 1/2, fordi hvis n = a * b,a og b kan ikke begge overstige kvadratroden af n..
  6. 6
    Dette kan optimeres ved at springe testen division med numre, der er tydeligvis ikke prime. For eksempel springe alle lige tal større end to, og hver multiplum af tre større end tre.

Fermats lille sætning

  1. 1
    Teknisk set Fermats test er en test for sammensathed, snarere end for primeness. Dette er fordi, hvis testen mislykkes, antallet er helt sikkert komposit, men hvis de består testen, at antallet er meget sandsynligt primtal, men kan eventuelt være en sammensat pseudoprimtal.
  2. 2
    Lad n være antallet at teste for primtal.
  3. 3
    Pick enhver heltal a mellem 2 og n -1.
  4. 4
    Beregn a n (mod n).
    • Beregn det effektivt ved hjælp af kvadratur i stedet for multiplikation når det er muligt. Det vil sige, beregne 3 100 som (((((((3 2) * 3) 2) 2) 2) * 3) 2) 2, ikke som 3 * 3 * 3 * 3 *... * 3. Reducer modulo n efter hver operation.
  5. 5
    Kontroller, om en n = a (mod n). Hvis ikke, n er. Hvis det er sandt, er n sandsynligvis prime. Gentage testen med forskellige værdier for en kan øge tilliden i resultatet, selvom der er sjældne sammensatte tal, der opfylder Fermat betingelse for alle værdier af en. Disse pseudoprimtal er Carmichael tal og den mindste er 561.

Miller-Rabin

  1. 1
    Mølleren-Rabin test fungerer på samme måde Fermats men håndterer patologiske tilfælde som Carmichael tal bedre.
  2. 2
    Lad n være et ulige antal for at teste for primtal.
  3. 3
    Faktor alle beføjelser 2 fra n -1, der udtrykker sig i form n -1 = 2 s * d hvor d er ulige.
  4. 4
    Vælg et tilfældigt tal a mellem 2 og n -1.
  5. 5
    Udregne en d (mod n). Hvis d = 1 eller -1 (mod n),n passerer Miller-Rabin test og er sandsynligvis primtal.
  6. 6
    Ellers beregne en 2 d, 4 d,... og en 2 s -1 d.. Hvis en af disse er lig -1 (mod n), så er n passerer også og er sandsynligvis primtal.
  7. 7
    Hvis n passerer mølleren-Rabin test for nogle værdien af en, så prøv en anden en til at forbedre tilliden til resultatet af testen.
  8. 8
    Hvis n er i virkeligheden, vil det passere med enhver værdi af en. Hvis n komposit, vil det mislykkes for mindst tre fjerdedele af de værdier af a.

Tips

  • Mens retssagen division er langsommere end mere sofistikerede metoder til store tal, er det stadig ganske effektiv for små tal. Selv for primtalstest af store tal, er det ikke ualmindeligt at først kontrollere for små faktorer, før du skifter til en mere avanceret metode, når ingen små faktorer er fundet.
  • De 168 primtal under 1000 er: 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

Ting du behøver

  • Arbejde ud værktøjer, såsom papir og pen eller en computer