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.

Enligt Fermats lilla sats gäller att om ett primal p inte delar ett tal a så gäller att p delar ${\displaystyle a^{p-1}-1}$, men till exempel gäller att talet ${\displaystyle 2^{341-1}-1}$ är delbart med ${\displaystyle 341}$ fastän ${\displaystyle 341=11\cdot 31}$ inte är ett primtal och 2 inte delar 341. 341 är ett Fermat-pseudoprimtal.

Att p inte delar a är ett nödvändigt villkor för att p ska dela ${\displaystyle a^{p-1}-1}$, och detta oberoende av om p är primtal eller ej, ty om p delar a så delar p också ${\displaystyle a^{p-1}}$ och alltå inte ${\displaystyle a^{p-1}-1}$.

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 tal 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

Huvudartikel: 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.

Referenser

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