unknown

Primtal er i polynominal tid

8 aug. 2002 11:16 - Via Slashdot - af Richter

En indisk Professor “Manindra Agrawal” fra Indian Institute of Technology Kanpur CS department, har fundet og bevist en ny og hurtigere måde at bestemme, hvorvidt et tal er et primtal eller ej i polynominal tid. Et bevis som sætter 512 bits kryptering i et dårligt lys

Forside
⟨
Forum
⟨
Nyheder

Gå til bund

#1 - SaD
9. aug. 2002 08:00

*rømme sig*
Jeg er ganske simpelt alt for rastløs en sjæl til selv at finde ud af hvad i alverden dette vil sige - så er der ikke en barmhjertig matematisk engel der vil lade sit visdommens lys skinne over mig?
*rømme rømme*

#2 - ClausMadsen
9. aug. 2002 08:10

#1 - oss mig tak :-)

#3 - west
9. aug. 2002 08:15

<A name=4023307>Re:What's Polynomial Time?</A>Goonie: (rgmerk at mira dot net)-The technical definition is kinda long and complex, but in essence it's like this. Given a problem of some size n, a polynomial time algorithm is guaranteed to give a solution in time proportional to a polynomial of n. If a polynomial-time algorithm exists that solves a problem, then the problem is said to be in polynomial time.
To give an example, say you've got a list of numbers and you want to know the sum. That can be done in linear time - ie, the time taken is proportional to the length of the list of numbers. The size of the problem (n) is defined by the length of the list and the time taken (T) is as follows: T = c1 * n + c0, where c1 and c0 are some fixed constants. The formula for T is a polynomial, and so the problem "LIST-SUM" is in polynomial time. It would still be in polynomial time if the formula for T was a polynomial with n^2, n^3, n^50 terms in it, or even terms like n^1.5 (because as n grows very large an n^1.5 term will always be smaller than an n^2 term).
Showing you an example of something outside polynomial time is a little more difficult, but some standard examples are SAT (the satisfiability problem) or the travelling-salesman problem, which you can read about in any book on the subject. Sakset fra /. ..

#4 - sKIDROw
9. aug. 2002 08:18

Kører da også 2048bit i pgp.. ;)

#5 - mr.muffin
9. aug. 2002 08:26

Formelen er skod hvis man ikke bruger en på en pc, eller andet fordi mennesker bruger ikke samme tid på at løse problemer.

Problem løsningstiden = beregningen * list størrelse + en konstant (huh! hvad mener han lige med det?)

Formlen er relativ, hvis det ikke er samme "enhed" der bruger formlen

#6 - idle
9. aug. 2002 08:41

Der eksisterer allerede effektive metoder til at bestemme om et tal er et primtal (med stor sandsynlighed). Det bruges (i krypteringssammenhæng: det "gamle" RSA m.fl.) kun når man genererer nøgler, og ikke i selve krypteringen. Der er altså ikke noget der kompromitterer sikkerheden i kryptering her.

Det nye er at i stedet for en probalistisk funktion til at bestemme om et tal er et primtal, kan man med en passende mængde processorkraft sige det med sikkerhed.

/idle

#7 - iluka
9. aug. 2002 10:03

mr.muffin:
Siger det ikke sig selv? Hvis det tager 20 sec. at pille en gullerod op af jorden og og du skal pille alle gullerødderne i en række med 100 gullerøder op, så tager det 20*100 sec (c1*n). Og så kan du selv tænke på hvad konstanten(c0) skal bruges til, men i matematisk sammenhæng er den fuldstændigt ligegyldig, og vil af de fleste bare blive ignoreret. Det skyldes at ligemeget hvor stor konstanten bliver, så ændrer det ikke på at du piller gullerødderne op i linær tid. Det bliver mere udtalt hvis det nu tog dig f.eks c1*n*n+c0, altså en konstant tid gange n i anden. Meget mere om det når du begynder at læse matematik, datalogi eller noget andet fornuftigt på universitet :o)

#8 - bebe
9. aug. 2002 11:09

godt nok kan man nu bestemme om et tal er et primtal eller ej hurtigere, men det tager stadig lang tid at opløse et tal i dets primfaktorer, da man stadig skal benytte udtømmende søgning. Dvs at ond kryptering stadig tager lang tid at knække.

#9 - DOMMER
9. aug. 2002 11:38

#7 - iluka:

Det er vel faktisk lige præcis i matematik, at c0 IKKE er ligegyldig...
Først når man laver det i praksis, og n -> uendelig, får c0 næsten ingen betydning.
Det er klart, den er ligegyldig for problemet med linær tid, men ellers har den vel en vis betydning.

#10 - Pingu
9. aug. 2002 12:43

er der ikke noget med at deter ulovligt at kryptere over 128bit eller sådan noget?

#11 - lean
9. aug. 2002 15:31

OK, hvorfor skal newz altid indsætte sjove kommentarer i nyheden som er skrup forkerte?

'Et bevis som sætter 512 bits kryptering i et dårligt lys'
Hvem finder på sådan noget ævl.
Husk på at det ikke er lineær tid man kan finde primtal, men kun polynomisk.
Dvs det kan være x², x³ osv. De bedste algoritmer til at bestemme om et tal er primtal er i ca x^4 tid, og de er ikke engang deterministiske.
Og selvom man kunne finde ud af om et tal er et primtal i x tid, skal man stadig checke alle tallene for at finde faktoriseringen i RSA.
Men måske har i læst beviset og forstået det anderledes end mig...

(Og fra _nu_ af vil jeg kun kommentere artikler og ikke nyhedsfortolkningen)

#12 - Erroneus
9. aug. 2002 16:59

Så er det nu jeg er pissegald for min 03 i mat B, for jeg fatter da hat af hvad der sker her, men måske er jeg den eneste :(

#13 - Onde Pik
9. aug. 2002 17:06

#7

Siden hvornår er Datalogi fornuftigt? ;) At sidde i et terminalrum med lavt ilt indhold og spise instantnudler, drikke cola og kaffe, i 12 timer om dagen gennem det meste af semester virker udmidlbart ikke særlig fornuftigt. Nok omkring lige så fornuftigt som det faktum at der ikke er nogle blå vingummibamser i posen. ;)

#14 - grav
9. aug. 2002 17:07

Jeg har haft naturfag i gym ... hvis der er nogen, der vil vide noget om hvordan man genkender månefaser, så bare sig til ...

#15 - PSiX
9. aug. 2002 17:24

Til staben på newz.dk:

Begynd dog at moderere jeres udtalelser, og hold for guds skyld op med selv at digte videre på nyheder, som i forvejen blot er copy/pasted direkte fra sites der selv copy/paster fra andre sites. Jeres troværdighed daler konsekvent hver gang det sker.

Som kommentar til selve indholdet af nyheden kan http://unixhq.dk/ være interessant stof...

#16 - Mozez
9. aug. 2002 21:07

1# og 2#:
Visdommens lys:
Et primtal p skal ifølge definitionen tilhøre N og være større 1 (dvs. p>1). Et primtal er et tal hvor kun tallet selv og 1 går op i f.eks. 2, 3, 5, 7, 11, 13, 17, 19 og 23. Man kan spekulere over hvorfor 1 som sagt ikke kaldes et primtal men sådan er det defineret. Så kan I lære det ;-).

#17 - wzk3
9. aug. 2002 22:50

Wow.

#18 - OrlaPiksmed
9. aug. 2002 22:58

Du er sgu klog Mozez.

Men jeg tror ikke der er nogen der var i tvivl om det. Nu kan du jo så bruge din enorme viden på at forklare os hvad polynomiel tid er...

på forhånd tak... (læs: spar os).

#19 - Jensen
10. aug. 2002 06:54

#10
Det er vidst kun i USA det er forbudt, at bruge 128bit kryptering i sine programmer.. Det skyldes (efter min hukommelse) noget med, at det ikke må være for svært at dekryptere, så man ikke kan skjule ulovligheder. I Danmark og resten er Europa tror jeg ikke der er noget max.

#20 - BurningShadow
10. aug. 2002 15:47

I må ikke gå ind i den lokale computer butik, her i landet, for at købe et krypteringsprogram, der kan kryptere med mere end 128bit, og hvis i gør, så skal resten af nøglen opbevares af PET. Så hvis i bruger en 256bit nøgle, så skal de SIDSTE 128bit opbevares af myndighederne. Hvordan dette varetages i praksis ved jeg ikke, men der er ingen problemer hvis i bruger downloadet software (PGP), da det ikke er underlagt samme lov.
Reglerne er lamme, jeg ved det… men det er også den eneste grund til at jeg kan huske dem :-)

#21 - Jazz_1.41
11. aug. 2002 16:48

Jeg er stadig ikke helt med på hvad polynominel tid er, er der en der kan give nysgerrige, samt måske lettere dumme, mig, en nogenlunde jordnær forklaring på hvad det er? Helst på dansk hvis muligt.
Eller polynominel tid er måske så indviklet et begreb at forståelse, uden først at have læst matematik på universitetet, ikke er muligt?

#22 - Mozez
11. aug. 2002 21:26

#18 og 21:
Visdommens lys 2:
For at slå det fast for en god ordens skyld hedder det polynomial tid ikke polynomiel tid.
Hvis du har en tid f.eks 5 (enheden er ligegyldig, forskellen er den samme) kaldes denne for konstant tid.
Hvis du har en tid x kaldes denne for lineær tid.
Hvis du har en tid n^x kaldes denne for eksponentiel tid.
Endelig hvis du har en tid x^n kaldes denne for polynomial tid.

Så kan I lære det 2.

Hvad betyder: #18 "på forhånd tak... (læs: spar os)."

#23 - mindflay
11. aug. 2002 21:56

#21 m.fl. hvad er polynomiel tid?
I (meget) teoretisk datalogi skelner man (forsimplet) imellem polynomiel tid og eksponentiel tid. Når noget vokser polynomielt vokser det som et polynomium. Simple eksempler er x, x^2, x^3 osv. Sammenlignet generelt og teoretisk er eksponentiel vækst meget voldsommere.
Tankegangen er populært sagt at hvis noget tager polynomiel tid er det IKKE praktisk umuligt at udføre selv for store datamængder. Hvis noget tager eksponentiel tid VIL det være praktisk umuligt at udføre for store datamængder.
Det betyder altså i praksis alt om opgaven bliver ekstremt meget(=eksponentielt) langsommere eller kun "noget" (=polynomielt) langsommere af at man f.eks. har dobbelt så mange bits i kryptering eller dobbelt så mange tal at sortere osv. Det er dog først når der er tale om "uendeligt" store datamængder at disse overvejelser er 100% korrekte.

Nyheden har altså "kun" teoretisk betydning.

Forklaring eller forvirring? :)

#24 - Scarpia
6. sep. 2002 18:21

#22 Mozez:
Det hedder polynomiEl tid på dansk. På engelsk hedder det "polynomial Time", hvilket dog KAN oversættes til polynomialtid (men bemærk at de to ord så må sammenskrives!). Det hedder altså IKKE "polynomial tid".

Men, for lige at gennemgå fakta endnu en gang: #6 har ret, der eksisterer allerede metoder som kan benyttes til at bestemme om et givent tal er et primtal med vilkårlig stor sandsynlighed. En enkel primtalstest kan udledes af Fermats Lille Sætning; denne slår dog desværre fejl ved de såkaldte Carmichael tal, så i stedet anvender man normalt Rabins test, der har eksisteret siden 1980.

Så denne indiske professors nye metode er altså ikke noget større gennembrud fra et kryptografisk synspunkt.

Scarpia

Forside
⟨
Forum
⟨
Nyheder

Gå til top

Opret dig som bruger i dag

Det er gratis, og du binder dig ikke til noget.

Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.

Opret Bruger Login

mboost-dp1

Nyheder

Seneste kommentarer i nyheder

Seneste kommentarer i forum

Primtal er i polynominal tid