Matematik
Find Primtal
15. maj 2007 af
stræber-pigen (Slettet)
Hvordan finder man primtallene? Altså tjekke om et tal er et primtal?
Kan man ikke bruge:
1. Fermats lille Sætning
2. Wilson's sætning
På forhånd tak!
Kan man ikke bruge:
1. Fermats lille Sætning
2. Wilson's sætning
På forhånd tak!
Svar #1
15. maj 2007 af Bruger slettet (Slettet)
Her en god side om primtal:
http://www.loria.fr/~zimmerma/records/primes.html
Man har ikke nogen generel formel til at udregne, om et tal er et primtal, derfor må man prøve sig frem, om det kan opløses i faktorer. Kan det ikke det, er det et primtal.
V.h.
Erik Morsing.
http://www.loria.fr/~zimmerma/records/primes.html
Man har ikke nogen generel formel til at udregne, om et tal er et primtal, derfor må man prøve sig frem, om det kan opløses i faktorer. Kan det ikke det, er det et primtal.
V.h.
Erik Morsing.
Svar #2
15. maj 2007 af stræber-pigen (Slettet)
#1 Så sagde min lærer også noget med at hvis man fandt en faktorisering-formel ville vernde gå under?
Svar #3
15. maj 2007 af peter lind
Fermats lille sætning siger kun noget om, hvad der sker, hvis man har et primtal; men ikke noget om hvad der sker hvis det ikke er et primtal. Eksempelvis gælder der -hvis jeg ellers husker rigtigt- at 2^340 modulo 341 = 1 selvom 341 = 11*31.
Den mest anvendte test for store primtal er Rabin-Miller testen, som er baseret på en udvidelse af Fermats lille sætning.
Hvis man skal teste om p er et primtal beregner man for nogle primtal a a^(p-1) mod p, a^[(p-1)/2] mod p, a^[(p-1)/4] og videre for alle værdier af (p-1)/(2^q) som er hele. Man ved så at en af disse skal være ækvivalent med -1 med mindre alle er ækvivalent med 1.
Denne metode er heller ikke helt sikker, så man tester for flere primtal a. Hvis der er testet for tilstrækkelig mange primtal a, kan man vise at sandsynligheden for at p ikke er et primtal er helt usandsynlig lille.
En anden og sikker metode er først at teste om p er ulige og forskellig fra 2. Dernæst test om ingen ulige tal op til kvadratrod p går op i p. Denne metode kan på en nutidig PC sagtens teste tal på lidt over 20 cifre.
Desuden findes der en speciel metode til at teste Mersenne tal.
Den mest anvendte test for store primtal er Rabin-Miller testen, som er baseret på en udvidelse af Fermats lille sætning.
Hvis man skal teste om p er et primtal beregner man for nogle primtal a a^(p-1) mod p, a^[(p-1)/2] mod p, a^[(p-1)/4] og videre for alle værdier af (p-1)/(2^q) som er hele. Man ved så at en af disse skal være ækvivalent med -1 med mindre alle er ækvivalent med 1.
Denne metode er heller ikke helt sikker, så man tester for flere primtal a. Hvis der er testet for tilstrækkelig mange primtal a, kan man vise at sandsynligheden for at p ikke er et primtal er helt usandsynlig lille.
En anden og sikker metode er først at teste om p er ulige og forskellig fra 2. Dernæst test om ingen ulige tal op til kvadratrod p går op i p. Denne metode kan på en nutidig PC sagtens teste tal på lidt over 20 cifre.
Desuden findes der en speciel metode til at teste Mersenne tal.
Skriv et svar til: Find Primtal
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.