Semiprimtall

I matematikk er et halvprimtall , også kalt biprimtall , et naturlig tall som er et produkt av to ikke nødvendigvis forskjellige primtall . Semiprimer mindre enn 100 er 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 og 95. (sekvens A001358 i OEIS ). Semiprimer som ikke er perfekte kvadrater kalles diskrete, eller direkte semiprime.

Egenskaper

Det totale antallet primtallsfaktorer Ω( n ) for en semiprimtall n er to, per definisjon. Et semiprimtall er enten et kvadrat av et primtall eller et kvadratfritt heltall . Et sammensatt tall som ikke er delelig med primtall er semiprimtall. Siden kvadratet til et hvilket som helst primtall er semiprimtall, vil det største kjente semiprimtall alltid være kvadratet av det største kjente primtallstallet , med mindre faktorene til semiprimtall er ukjente.

I 1966 viste den kinesiske matematikeren Chen Jingrun at ethvert tilstrekkelig stort partall kan uttrykkes som summen av to primtall eller som summen av et primtall og et tall som er multiplikasjonen av to primtall. (" semi -prime"). [ 1 ]

Verdien av Eulers φ-funksjon for en semiprime n = pq er spesielt enkel når p og q er forskjellige:

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

Verktøy

Halvprimtal er svært nyttige innen kryptografi og tallteori , spesielt i asymmetrisk kryptografi der de brukes av RSA og i pseudo-tilfeldige sekvenser som Blum Blum Shub . Disse metodene er basert på det faktum at å finne to store primtall og deretter multiplisere dem er beregningsmessig enkelt, mens det er vanskeligere å finne de opprinnelige faktorene. I RSA Factoring Competition tilbød RSA Security premier for factoring av spesifikke store semi-prime. Utfordringen ble avsluttet i 2007. [ 2 ]

I praktisk kryptografi er det ikke nok å velge en semi-prime; et godt semiprimtall må unngå et velkjent sett med spesialalgoritmer som kan identifisere tall på en bestemt måte. Faktorene p og q til n må være veldig store, omtrent samme størrelsesorden som kvadratroten; dette gjør tentativ inndeling og Pollards rho-algoritme upraktisk. Samtidig kan de ikke være for nær hverandre, ellers kan tallet raskt faktoriseres med Fermats faktoriseringsmetode . Tallet må også velges slik at ingen av p − 1, p +1, q − 1 eller q +1 er jevne tall , og beskytter det mot Pollards p −1 algoritme eller Williams p +1 algoritme . Disse sjekkene kan ikke tas i betraktning for fremtidige algoritmer eller hemmelige algoritmer, og introduserer muligheten for at tall som brukes i dag kan bli knekt av spesialbygde algoritmer senere.

I 1974 ble Arecibo-meldingen sendt med et radiosignal som var rettet mot en stjernehop . Det besto av 1679 binære sifre ment å bli tolket som et punktgrafikkbilde . Tallet 1679 = 23×73 ble valgt fordi det er en semi-primtall og derfor bare kan analyseres i 23 rader og 73 kolonner, eller 73 rader og 23 kolonner.

Se også

Referanser

  1. ↑ Tony Crilly (2011). 50 ting å vite om matematikk . Red. Ariel. ISBN 978-987-1496-09-9 . 
  2. ↑ http://www.rsa.com/rsalabs/node.asp?id=2092 Arkivert 1. juni 2007

Eksterne lenker