Text 3045, 47 rader
Skriven 1999-04-10 11:52:25 av Henrik Schröder (2:201/128.9)
   Kommentar till text 2951 av Sack Jönsson (2:206/145.4242)
Ärende: LÅGPRISALTERNATIV TILL INTERNET
=======================================
 EL>> Men om du menar att någon kommer på en metod att snabbt testa
 EL>> faktoriseringen av godtyckligt stora primtal, så visst, då är
 EL>> PGP i princip värdelöst.

 ZJ> Och hur får alla PGP-användare veta, när någon har lyckats?

 ZJ> Fan, vad jag ska skratta åt er den dag det händer.

Först en kort förklaring för att du inte ska ställa en massa dumma frågor sen:

Det finns en mängd matematiska problem som kallas för NP-kompletta,
primtalsuppdelningen som behövs för att knäcka vanliga krypton exempelvis. Det
alla dessa problem har gemensamt är att man inte kan lösa problemet på
polynomiell tid, dvs det finns inget samband mellan tiden det tar att lösa
problemet och komplexiteten på problemet som kan skrivas som ett polynom.

Problemet att sortera en sträng bokstäver kan lösas på polynomiell tid t ex. Om
strängens längd är n, så kan jag göra en sorteringsalgoritm som sorterar på
tiden n^2 (och om jag anstränger mig går det på n*log(n)), dvs lösningstiden
ökar kvadratiskt med komplexiteten.

För alla dessa NP-kompletta problem är det alltså så att lösningstiden ökar
otroligt mycket om man bara ökar komplexiteten lite. Nån annan skrev nåt i
mötet om att om man ökade bitlängden på nyckeln med en bit, så skulle det ta
dubbelt så lång tid att lösa problemet, detta för att man måste gå igenom alla
möjliga nycklar, och ökar man med en bit så blir ju nyckeln dubbelt så stor
(eftersom man räknar binärt). Det gäller också att alla NP-kompletta problem
kan verifieras i polynomiell tid, dvs det är trivialt att kolla om lösningen är
korrekt. För primtalsuppdelningen är det rätt självklart, man multiplicerar
bara de två primtalen man tror är rätt, och blir det det tal man delade upp så
stämmer det ju.

Man kan dessutom med matematisk teori (som jag inte kan eller orkar slå upp)
bevisa att om man löser ETT NP-komplett problem på polynomiell tid, så kan man
lösa ALLA NP-kompletta problem på polynomiell tid, och en sån stor matematisk
händelse kommer

a) Att uppmärksammas otroligt fett

b) troligtvis aldrig hända, eftersom väldigt många har spenderat väldigt mycket
tid på att tänka på den stora mängden problem som finns.


/Henrik Schröder

--- FMailX32 1.46
 * Origin: Two households, both alike in dignity, in Fair Verona. (2:201/128.9)