Pseudoprimtal

Pseudoprimtal är ett heltal som delar en egenskap som är gemensam för alla primtal, men som egentligen inte är primtal. Pseudoprimtal klassificeras efter vilken egenskap av primtal som de uppfyller.

Vissa källor använder termen pseudoprimtal om alla troliga primtal, både sammansatta tal och faktiska primtal.

Pseudoprimtal används för det mesta i asymmetrisk kryptering, som använder sig av svårigheten att faktorisera stora mängder i sina primtalsfaktorer. Carl Pomerance beräknade år 1998 att det skulle kosta $10 miljoner att faktorisera ett tal med 144 siffror, och $10 miljarder att faktorisera ett 200-siffrigt tal. Men att hitta och faktorisera rätt primtal för denna användning är motsvarande dyrt, så olika sannolikhetsbaserade primtalstester används för att hitta primtal bland många, av vilka i sällsynta fall felaktigt identifiera sammansatta tal som primtal.

Fermat-pseudoprimtal

Fermats lilla sats säger att om p är ett primtal och a är relativt prima till p, då är a^{p - 1} - 1 delbart med p. Om ett sammansatt heltal x är relativt prima till ett heltal a > 1 och x delar a^{x - 1} - 1, då kallas x för Fermat-pseudoprimtal till bas a. Vissa källor använder varianter av denna definition, till exempel att endast låta udda tal att vara pseudoprimtal.

Ett heltal x som är ett Fermat-pseudoprimtal till samtliga värden på a som är relativt prima till x kallas för Carmichaeltal.

Källor

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, Pseudoprime, 1 december 2013.