Áttörés a kriptográfiában: egy új algoritmussal gyorsan ellenőrizhetők a különösen nagy prímszámok
[ZDnet] Indiai kutatók új algoritmusa, számítási metódusa áttörést hozhat a titkosító algoritmusok, szoftverek fejlesztésében, kriptográfiában: az új formula segítségével nagyon gyorsan ki lehet deríteni, hogy egy adott szám prímszám-e, vagy sem. A matematikai problémán hosszú évek, évtizedek óta dolgoznak a matematikusok.
A prímszámokon alapul az RSA, a közekdvelt titkosító algoritmus is, melyet többek között az interneten történő kereskedelmi, titkosított tranzakciók során is használnak. A prímszámok egyedi számok, mivel csak önmagukkal és eggyel oszthatók. Kellően nagy prmíszám generálása és prím tulajdonságának megállapítása viszont rendkívül időigényes, s szinte lehetetlen feladat.
A prímszámok generálásához az RSA több ismert, óriási prímszámot használ, melyeket egymással szorozva, majd tovább manipulálva hoz létre valószínűsíthetően újabb prímszámot. Ennek a számnak a tesztelése azonban a jelenlegi algoritmusokkal vagy túlságosan hosszú ideig tart, vagy gyorsabb metódusok használatával téves eredményt kaphatunk.
Az indiai Kanpurban található Indian Institute of Technology intézetben Manindra Agrawal és diákjai, Neeraj Kayal és Nitin Saxena új algoritmust dolgozott ki, mellyel viszonylag gyors és teljesen megbízható eredményt kaphatunk a prímszám tesztelése során.
"A titkosító szoftverek legfőbb gyenge pontja az, hogy nem tudjuk garantálni az adott szám prím mivoltát," mondta Eric Allender, a New Jersey-i Egyetem professzora. "Az új algoritmus válaszol erre az alapvető kérdésre, mely nyitott volt évszázadokon át, s melyre évtizedek óta komoly kutatások keresték a választ."
A megoldásról elismerően szólt több kutató és matematikus. "Egyes algoritmusok rettentően bonyolultak voltak, ez azonban tiszta, világos és elegáns," mondta Allender.
"Az algoritmusunk lassabb, mint a jelenleg ismert leggyorsabb tesztelő metódus," nyilatkozta Manindra Agrawal. "Megnyugtató azonban pontossága -- az előző metódusok hibáztak, még ha elég ritkán is."