mboost-dp1
unknown
#1 - Man har jo indtil videre bare prøvet sig frem til at finde de primtal altså ved se om der er en eller flere tal der går op i et Tal X... Den gåde de snakker om er at finde en formel der kan finde alle de tal eller ikke alle men en formel der kan beregne og se om det er en primtal eller ikke... ved ikke om jeg kunne forklare det...
#2 - Ja lige precis det han påstår at han har....
#2 - Ja lige precis det han påstår at han har....
Det skulle vist være en formular der returner sandt/falsk for det valgte nummer.
Så vidt jeg har forstået, så er den måde man gør det idag at man tjekker alle tal fra 2 op til halvdelen af det valgte nummer, om de går op i tallet.
Dette vil kom til at være MANGE beregnering hvis du f.eks. skal finde ud af om 27456787 er et primtal. Hvis du kan gøre det med EN beregning, så er det jo fedt nok.
Så vidt jeg har forstået, så er den måde man gør det idag at man tjekker alle tal fra 2 op til halvdelen af det valgte nummer, om de går op i tallet.
Dette vil kom til at være MANGE beregnering hvis du f.eks. skal finde ud af om 27456787 er et primtal. Hvis du kan gøre det med EN beregning, så er det jo fedt nok.
#7 Ja. Og du kan nøjes med at tjekke alle primtal op til kvadratroden af det tal du vil tjekke.
(Hvorfor iøvrigt plus 1? Hvis det er afrunding du er bekymret for er problemet ikke så stort. Tallet kan ikke være et produkt af to tal som begge er større end kvadratroden af sig selv, - heller ikke selvom det kun er ,1 større).
Iøvrigt hedder universitetet ikke Perdue men Purdue. Det ligger i Indiana.
(Hvorfor iøvrigt plus 1? Hvis det er afrunding du er bekymret for er problemet ikke så stort. Tallet kan ikke være et produkt af to tal som begge er større end kvadratroden af sig selv, - heller ikke selvom det kun er ,1 større).
Iøvrigt hedder universitetet ikke Perdue men Purdue. Det ligger i Indiana.
Den måde man bruger idag er ikke bare at tjekke alle tal fra 2 og op... Det er alt alt for langsomt. Man bruger derimod Solovay-Strassen eller Miller-Rabin-algoritmerne, som med en hvis sikkerhed kan sige om et tal er et primtal. Men altså ikke helt sikkert - jeg mener at der er 50% sandsynlighed for at det er et primtal. Hvis algoritmerne siger nej, så er man HELT sikker på at tallet ikke er et primtal, men siger de ja er der altså 50% chance. Men kan nu køre disse algoritmer et par gange eller 10 og derved blive noget sikrere (da de benytter tilfældige tal er dette muligt), men aldrig helt sikker.
Jeg har lidt svært ved at se hvordan det skulle være en katastrofe for moderne kryptografi, men den artikel er så også pænt dårlig, IMHO...
Jeg har lidt svært ved at se hvordan det skulle være en katastrofe for moderne kryptografi, men den artikel er så også pænt dårlig, IMHO...
Problemet må gælde for asymmetriske krypterings algoritmer. RSA er et eksempel på dette. Læs mere her: http://en.wikipedia.org/wiki/RSA
i getter rigtig et primtal er et tal som kun 1 og tallet selv går op i, men der er ikke nogen som har kunnet give en formel eller rekkefølge på hvordan disse tal kan findes, lige nu er man nød til at skrive og tælle osv ... en formael ville gøre at man altid kan regne dem ud ..
Lidt links:
dette er hans bevis for at han har ret, og løst gåden.
http://www.math.purdue.edu/ftp_pub/branges/apology...
Lidt fact om ham
http://encyclopedia.thefreedictionary.com/Louis%20...
Egen mening:
Jeg kan godt se problemet nu, hvis han har ret. Det vil betyde at NSA ville kunne aflytte flere end de allerede gør.
Jeg ved at nyere kryptisering er bygget på andre ting, fx bevægelsen af en lavalampe.
Denne bevægelse er så kompelx, pga så mange ukendte faktorer, så hvis denne nyhed ikke er ligesom kold fusion, vil man stadigvæk have en løsning for at beskytte data, men disse nye kryptiserings metoder mangler implementering.
dette er hans bevis for at han har ret, og løst gåden.
http://www.math.purdue.edu/ftp_pub/branges/apology...
Lidt fact om ham
http://encyclopedia.thefreedictionary.com/Louis%20...
Egen mening:
Jeg kan godt se problemet nu, hvis han har ret. Det vil betyde at NSA ville kunne aflytte flere end de allerede gør.
Jeg ved at nyere kryptisering er bygget på andre ting, fx bevægelsen af en lavalampe.
Denne bevægelse er så kompelx, pga så mange ukendte faktorer, så hvis denne nyhed ikke er ligesom kold fusion, vil man stadigvæk have en løsning for at beskytte data, men disse nye kryptiserings metoder mangler implementering.
#4 refererer /korrekt/ til tråden http://newz.dk/forum/item/30114/# idet deBranges har arbejdet med Riemann-hypotesen, som netop er meget tæt forbundet med primtallenes fordeling.
Hvad nyheden angår, så er det ikke en nyhed. deBranges "bevis" er et gammelt (ukorrekt) der er kommet op igen, så vidt jeg ved...
Kryptologi: Alt falder ikke fordi man finder en hurtig algoritme til at primfaktorisere. Der er stadig asymmetriske systemer der ikke bygger på at det er svært at primfaktorisere f.eks. elliptisk kurve-kryptering. Fear not. Vi skal bare skifte RSA ud, det giver nok kun et halvt til et helt år med totalt anarki ;-P
Cheers,
fra en matematiker
Hvad nyheden angår, så er det ikke en nyhed. deBranges "bevis" er et gammelt (ukorrekt) der er kommet op igen, så vidt jeg ved...
Kryptologi: Alt falder ikke fordi man finder en hurtig algoritme til at primfaktorisere. Der er stadig asymmetriske systemer der ikke bygger på at det er svært at primfaktorisere f.eks. elliptisk kurve-kryptering. Fear not. Vi skal bare skifte RSA ud, det giver nok kun et halvt til et helt år med totalt anarki ;-P
Cheers,
fra en matematiker
#18 gunderup
Nej, det er ikke hans endelige forslag. Han har arbejdet på dette længe, men andre har studeret teknikken og fundet ud af, at de huller der er, vil være uhyggeligt svære at lappe. Derfor den lidt lunkne modtagelse af 'beviset' (link kan stadig ses på forsiden af www.mathworld.com).
Mht. internettets 'sammenbrud' er jeg osse ret fortrøstningsfuld. Riemann-hypotesen som sådan kan jeg ikke se gør den store forskel; det er i højere grad teknikken i beviset der kan. Men deBranges teknik har været kendt længe uden at faktoriserings er blevet mere effektiv - så jeg slapper af...
#17 toey
Så vidt jeg lige husker er definitionen på et tal, hvis divisorer alene er tallet selv samt enheder, at det er irreducibelt.
Primtal er tal, der hvis de går op i et produkt af to tal så går det op i mindst et af tallene.
I de hele tal Z er irreducible tal og primtal så det samme ;)
Nej, det er ikke hans endelige forslag. Han har arbejdet på dette længe, men andre har studeret teknikken og fundet ud af, at de huller der er, vil være uhyggeligt svære at lappe. Derfor den lidt lunkne modtagelse af 'beviset' (link kan stadig ses på forsiden af www.mathworld.com).
Mht. internettets 'sammenbrud' er jeg osse ret fortrøstningsfuld. Riemann-hypotesen som sådan kan jeg ikke se gør den store forskel; det er i højere grad teknikken i beviset der kan. Men deBranges teknik har været kendt længe uden at faktoriserings er blevet mere effektiv - så jeg slapper af...
#17 toey
Så vidt jeg lige husker er definitionen på et tal, hvis divisorer alene er tallet selv samt enheder, at det er irreducibelt.
Primtal er tal, der hvis de går op i et produkt af to tal så går det op i mindst et af tallene.
I de hele tal Z er irreducible tal og primtal så det samme ;)
Et bevis kan vel mappes til en algoritme, ellers kan der vel slet ikke være tale om noget krypterings-katastrofe som nyheden lægger op til - altså påvise/afvise/enumerere primtal.
Beviset kan muligvis lægge op til at man kan finde et mønster i distributionen af primtal, men at komme derfra, og til hurtig primtalsfaktorisering er vist et langt spring.
For primtal-noobs som jeg selv, er her en spændende artikel omkring primtal og hvorfor de netop er så interesante:
http://www.maths.ex.ac.uk/~mwatkins/zeta/ss-a.htm
Bemærk f.eks. på side 5 paradoxet af hvor "pæn" distributions-kurven er og så alligevel findes der endnu ingen formel der kan forudsige/enumerere dem!
http://www.maths.ex.ac.uk/~mwatkins/zeta/ss-a.htm
Bemærk f.eks. på side 5 paradoxet af hvor "pæn" distributions-kurven er og så alligevel findes der endnu ingen formel der kan forudsige/enumerere dem!
#14 jeg mener at der er 50% sandsynlighed for at det er et primtal.
Den formulering er lidt upræcist. Det er omvendt. Hvis det ikke er et primtal er der minimum 50% chance for at algoritmen siger det ikke er et primtal. (Jeg er faktisk ikke helt sikker på om det er 25%, 50% eller 75% man har bevist).
Men kan nu køre disse algoritmer et par gange eller 10 og derved blive noget sikrere
Ja, på den måde kan man blive så sikker som man ønsker. Og det er ikke voldsomt dyrt at køre den nogle ekstra gange når man skal bruge et primtal. I praksis vil det først være når man har fundet et primtal, at den kører mere end 5 gange. Så hvis man kører algoritmen 1-5 gange på de første 100 sammensatte tal, så har man nok også råd til at køre den 100 gange for at være tilpas sikker på at det faktisk er et primtal man har fundet.
men aldrig helt sikker.
Jeg mener der kom et nyt resultat for et år eller to siden, som beviste, at man i stedet for tilfældige tal kunne vælge nogle tests på en deterministisk måde og derved opnå 100% sikkerhed for at det var et primtal. Men det var voldsomt kompliceret, og jeg kan ikke huske detaljerne. I praksis bruger man vist stadig randomiserede primtalstests.
Man kan også konstruere primtalsbeviser. Men den gængse måde at bevise at p er et primtal kræver en faktorisering af p-1. (Beviset har en rekursiv struktur, da man skal bevise at faktorerne er primtal, indtil man når ned til passende små faktorer). Så givet et tilfældigt primtal er det ikke trivielt at konstruere beviset. Til gengæld kan man gøre det omvendt og vælge tilfældige primfaktorer til p-1 og så prøve sig frem indtil man finder et primtal med tilhørende bevis.
Jeg har lidt svært ved at se hvordan det skulle være en katastrofe for moderne kryptografi
Ja, det er ikke så afgørende om man kan afgøre, om et givet tal er et primtal. Man har jo længe haft metoder med passende lille fejlsandsynlighed. Det ville være en katastrofe for RSA, hvis man fandt en effektiv algoritme til faktorisering. Men andre algoritmer basserer sig jo på Diffie-Hellman antagelsen og diskrette logaritmer.
Den formulering er lidt upræcist. Det er omvendt. Hvis det ikke er et primtal er der minimum 50% chance for at algoritmen siger det ikke er et primtal. (Jeg er faktisk ikke helt sikker på om det er 25%, 50% eller 75% man har bevist).
Men kan nu køre disse algoritmer et par gange eller 10 og derved blive noget sikrere
Ja, på den måde kan man blive så sikker som man ønsker. Og det er ikke voldsomt dyrt at køre den nogle ekstra gange når man skal bruge et primtal. I praksis vil det først være når man har fundet et primtal, at den kører mere end 5 gange. Så hvis man kører algoritmen 1-5 gange på de første 100 sammensatte tal, så har man nok også råd til at køre den 100 gange for at være tilpas sikker på at det faktisk er et primtal man har fundet.
men aldrig helt sikker.
Jeg mener der kom et nyt resultat for et år eller to siden, som beviste, at man i stedet for tilfældige tal kunne vælge nogle tests på en deterministisk måde og derved opnå 100% sikkerhed for at det var et primtal. Men det var voldsomt kompliceret, og jeg kan ikke huske detaljerne. I praksis bruger man vist stadig randomiserede primtalstests.
Man kan også konstruere primtalsbeviser. Men den gængse måde at bevise at p er et primtal kræver en faktorisering af p-1. (Beviset har en rekursiv struktur, da man skal bevise at faktorerne er primtal, indtil man når ned til passende små faktorer). Så givet et tilfældigt primtal er det ikke trivielt at konstruere beviset. Til gengæld kan man gøre det omvendt og vælge tilfældige primfaktorer til p-1 og så prøve sig frem indtil man finder et primtal med tilhørende bevis.
Jeg har lidt svært ved at se hvordan det skulle være en katastrofe for moderne kryptografi
Ja, det er ikke så afgørende om man kan afgøre, om et givet tal er et primtal. Man har jo længe haft metoder med passende lille fejlsandsynlighed. Det ville være en katastrofe for RSA, hvis man fandt en effektiv algoritme til faktorisering. Men andre algoritmer basserer sig jo på Diffie-Hellman antagelsen og diskrette logaritmer.
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.
- Forside
- ⟨
- Forum
- ⟨
- Nyheder
Gå til bund