Semiprimtal

Semiprimtal (även kallat biprimtal, 2-nästan-primtal eller pq-tal) är inom matematiken ett naturligt tal som är produkten av två (inte nödvändigtvis olika) primtal.

De första semiprimtalen är:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 121, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, 159, 161, 166, 169, 177, 178, 183, 185, 187, … (talföljd A001358 i OEIS)

Semiprimtal som inte utgör perfekta kvadrater kallas för diskreta semiprimtal eller distinkta semiprimtal.

Sedan januari 2016 är det största kända distinkta semiprimtalet (2^74207281 − 1) × (2^57885161 − 1), det vill säga produkten av de två största kända primtalen.

Sedan denna tidpunkt är (2^74207281 − 1)² det största kända semiprimtalet.

Om det största kända primtalet är a och det näst största kända primtalet är b, så är a x b det största kända distinkta semiprimtalet och a x a det största kända semiprimtalet.

Semiprimtal har aldrig några sammansatta faktorer än sig själva. Till exempel är talet 26 semiprital eftersom dess enda faktorer är 1, 2, 13, och 26. I själva verket finns det inga tal som är produkten av två primtal som har några sammansatta faktorer.

Egenskaper

Det totala antalet primtalsfaktorer Ω(n) för ett semiprimtal n är två, per definition. Ett semiprimtal är antingen en kvadrat av ett primtal eller ett kvadratfritt tal. Kvadraten av alla primtal är ett semiprimtal, så det största kända semiprimtalet kommer alltid att vara kvadraten på det största kända primtalet, såvida faktorerna i det semiprimtalet inte är kända. Det är tänkbart att en väg kunde hittas för att bevisa ett större tal som är ett semiprimtal utan att känna till de två faktorerna.^[1] Ett sammansatt tal $n$ som är icke-delbart med primtal $\leq {\sqrt[{3}]{n}}$ är ett semiprimtal. Olika metoder, såsom elliptiska pseudokurvor och Goldwasser-Kilians ECPP-sats har använts för att skapa bevisbara, ofaktoriserade semiprimtal med hundratals siffror.^[2] Dessa anses vara noveltyer, eftersom deras konstruktionsmetod kan visa sig responsiv för faktorisering, och eftersom det är enklare att multiplicera två primtal tillsammans.

För ett semiprimtal n = pq är värdet av Eulers fi-funktion (antalet positiva heltal mindre än eller lika med n som är relativt prima med n) synnerligen enkelt när p och q är distinkta:

φ(n) = (p − 1) (q − 1) = p q − (p + q) + 1 = n − (p + q) + 1.

Om annars p och q är sanna,

φ(n) = φ(p²) = (p − 1) p = p² − p = n − p.

Konceptet för prima zeta-funktionen kan anpassas till semiprimtal, som definierar konstanter som

\sum _{\Omega (n)=2}{\frac {1}{n^{2}}}\approx 0.1407604

(talföljd A117543 i OEIS)

\sum _{\Omega (n)=2}{\frac {1}{n(n-1)}}\approx 0.17105

(talföljd A152447 i OEIS)

\sum _{\Omega (n)=2}{\frac {\ln n}{n^{2}}}\approx 0.28360

(talföljd A154928 i OEIS)

Tillämpningar

Semiprimtal är mycket användbara inom kryptografi och talteori, framförallt i asymmetrisk kryptering, där de används av RSA och pseudoslumptalsgeneratorer som Blum Blum Shub. Dessa metoder grundar sig på faktumet att det är beräkningsmässigt enkelt att hitta två stora primtal och multiplicera dem tillsammans (vilket resulterar i ett semiprimtal), men mycket svårare att hitta de ursprungliga primtalsfaktorerna. I RSA Factoring Challenge erbjöd RSA Security priser för faktorisering av specifika stora semiprimtal och flera priser utdelades.^[3]

I praktiskt kryptering är det inte tillräckligt att enbart hitta ett stort semiprimtal; ett bra semiprimtal måste undvika ett antal välkända algoritmer för speciella ändamål som kan faktorisera tal av vissa former. Faktorerna p och q av n bör båda vara mycket stora, runt samma storleksordning som kvadratroten av n. Detta gör trialdivision och Pollards rho-algoritm mycket opraktiska. Samtidigt bör inte faktorerna vara för nära varandra, annars kan talet snabbt faktoriseras med Fermats faktoriseringsmetod. Dessutom bör p − 1, p + 1, q − 1 och q + 1 inte vara släta tal, vilket skyddar mot Pollards p − 1-algoritm och Williams p + 1-algoritm. Dock tar inte dessa kontroller hänsyn till framtida eller hemliga algoritmer.

År 1974 skickades Arecibomeddelandet med en radiosignal till en stjärnhop. Det bestod av 1679 binära tal som är avsedda att tolkas som en 23 × 73-bitmappsbild. Talet 1679 = 23 × 73 valdes eftersom det är en semiprimtal och därför endast kan delas upp i 23 rader och 73 kolumner, eller 73 rader och 23 kolumner.