---

Jeg har et stort tal jeg gerne vil faktorisere. Det drejer sig om et
120-cifret tal, som jeg ved består af netop to primfaktorer på hver 60
cifre, elles ved jeg ikke noget om tallet. Jeg har fundet ud af, at jeg nok
skal bruge GNFS til at knække dette tal med, og nu vil jeg gerne høre om der
er nogen der har noget erfaring med denne algoritme

Jeg kender ikke noget til kørselstider, så hvis jeg har sat mig en umulig
opgave for, vil jeg blive glad for hvis nogen kan fortælle mig det. Hvis det
ikke er en håbløs opgave, hvor lang tid kan jeg så regne med at skulle bruge
hvis jeg har 4 PC'ere (500-1200 MHz) til rådighed?

-----
Jes Hansen

---

Hej Anders

Det skulle ikke være noget problem. Se her på et nært beslægtet problem:

30.09.2002 64-bit kryptering knækket.
Efter flere år er der nu fundet en vinder i en konkurrence om, hvem
der kunne knække en besked krypteret med en 64-bit nøgle af typen
RC5-64.
http://www.ing.dk/apps/pbcs.dll/article?Avis=IG&Dato=20020930&Kategori=IT&Lopenr=209300003&Ref=AR
Citat: "...Koden blev efter 1757 dage knækket af et af verdens største
grid-computer projekter "distributed.net", som via internettet har
anvendt over 300.000 computeres regnekraft igennem de sidste fire år...."

September 26, 2002, Distributed Team Collaborates to Solve Secret-Key
Challenge.
Contest designed to keep the cryptographic community updated on new
achievements and help organizations maintain highest levels of security:
http://www.rsasecurity.com/company/news/releases/pr.asp?doc_id=1400%20

mvh/Glenn

Anders Frederiksen wrote:
> Jeg har et stort tal jeg gerne vil faktorisere. Det drejer sig om et
> 120-cifret tal, som jeg ved består af netop to primfaktorer på hver 60
> cifre, elles ved jeg ikke noget om tallet. Jeg har fundet ud af, at jeg nok
> skal bruge GNFS til at knække dette tal med, og nu vil jeg gerne høre om der
> er nogen der har noget erfaring med denne algoritme
>
> Jeg kender ikke noget til kørselstider, så hvis jeg har sat mig en umulig
> opgave for, vil jeg blive glad for hvis nogen kan fortælle mig det. Hvis det
> ikke er en håbløs opgave, hvor lang tid kan jeg så regne med at skulle bruge
> hvis jeg har 4 PC'ere (500-1200 MHz) til rådighed?
>
> -----
> Jes Hansen
>
>

---

In <3E219B2A.4040907@c.dk> Glenn Moeller-Holst <glenn@c.dk> writes:

>Hej Anders

>Det skulle ikke være noget problem. Se her på et nært beslægtet
>problem:

Hmm, jeg har et problem med at genkende ironi mandag morgen.
Mon du mener det her eller ej. En 64-bit nøgle svarer ca til
et 32 cifret tal. 120 cifre svarer til en 360 bits-nøgle.
Mit bedste gæt er at det er helt udenfor rækkevidde medmindre
ham, der har valgt tallet har dummet sig (der er nogle tal, der
er sværere at knække end andre, også selv om alle er produktet
af to 60 cifrede primtal).

>30.09.2002 64-bit kryptering knækket.
>Efter flere år er der nu fundet en vinder i en konkurrence om, hvem
>der kunne knække en besked krypteret med en 64-bit nøgle af typen
>RC5-64.
>http://www.ing.dk/apps/pbcs.dll/article?Avis=3DIG&Dato=3D20020930&Kategor=
>i=3DIT&Lopenr=3D209300003&Ref=3DAR

Sæt dig ned og håb på at nogen finder en smart måde at faktorisere
på inden din plads på plejehjemmet går videre til den næste

Jeg kan ikke lige huske om NF metoden er den, hvor man får brug
for en supercomputer til sidste del af opgaven, men under alle
omstændigheder tror jeg at 120 cifre er i praksis uknækkelig.

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

Glenn Moeller-Holst <glenn@c.dk> writes:

> 30.09.2002 64-bit kryptering knækket.
> Efter flere år er der nu fundet en vinder i en konkurrence om, hvem
> der kunne knække en besked krypteret med en 64-bit nøgle af typen
> RC5-64.

Ja, men det var ved udtømmende søgning af alle nøgler. Det har ikke
noget med faktorisering at gøre. Man vil helt sikkert kunne
faktorisere et 64 bit tal som er produkt af to primtal meget
hurtigere.

--
Jacob - www.bunk.cc
Time sure flies when you don't know what you're doing.

---

Jacob Bunk Nielsen wrote :

> Glenn Moeller-Holst <glenn@c.dk> writes:
>
>> 30.09.2002 64-bit kryptering knækket.
>> Efter flere år er der nu fundet en vinder i en konkurrence om, hvem
>> der kunne knække en besked krypteret med en 64-bit nøgle af typen
>> RC5-64.
>
> Ja, men det var ved udtømmende søgning af alle nøgler. Det har ikke
> noget med faktorisering at gøre. Man vil helt sikkert kunne
> faktorisere et 64 bit tal som er produkt af to primtal meget
> hurtigere.

Hvis der yderligere er information om primtallene - fx om 2p-1 indeholder
mange små faktorer, så kan man af den vej få lidt hjælp til at vælge den
bedste algoritme. Hvis dette ikke er tilfældet, så er GNFS nok det bedste
bud.



--
Jesper Stocholm - http://stocholm.dk

Svar til gruppen og ikke til mig privat !
Skriv under det du svarer på - www.usenet.dk/netikette/citatteknik.html

---

Hej Anders

Jeg undskylder, hvis du ikke umiddelbart kunne se af mit tidligere svar,
at det var ironisk ment, at du kunne faktorisere et 120-cifret (bits?),
med 4 PC'ere.

Faktorisering af tal bestående af store primtal (mere end ca.40-56 bit),
anses en svær opgave. Grunden er at faktorisering i dag anses for et NP
(Non-Polynomial) problem. Det kræver derfor en eksponentiel lang tid at
faktorisere tal, i dets ukendte faktorer.

Det ser faktisk ud som om at GNFS reducerer eksponenten så meget at det
er indenfor mulighederne grænser at faktorisere tal med 60 bits
faktorer. Her er nogle relevante adresser:

RSA Number:
http://mathworld.wolfram.com/RSANumber.html
Citat: "...On Feb. 2, 1999, a group led by H. te Riele completed
factorization of RSA-140 into two 70-digits primes. Primality of the
factors was proved using two different methods. The factorization was
found using the number field sieve factorization method, and beat the
130-digit record (for RSA-130) set on April 10, 1996. The amount of
computer time spent on this factorization is estimated to be equivalent
to 2000 MIPS years...."

Number Field Sieve:
http://mathworld.wolfram.com/NumberFieldSieve.html
"......"

Er du mere nysgerrrig, så anvend følgende søgninger:

http://www.google.com/search?q=%22general+number+field+sieve%22

eller

http://www.google.com/search?q=GNFS

CiteSeer er rigtigt godt sted at finde datalogi relaterede 'draft' papirer:
http://citeseer.nj.nec.com/context/168610/223075

http://citeseer.nj.nec.com/directory.html

Søgninger foretages her:
http://citeseer.nj.nec.com/cs

mvh/Glenn

Anders Frederiksen wrote:
> Jeg har et stort tal jeg gerne vil faktorisere. Det drejer sig om et
> 120-cifret tal, som jeg ved består af netop to primfaktorer på hver 60
> cifre, elles ved jeg ikke noget om tallet. Jeg har fundet ud af, at jeg nok
> skal bruge GNFS til at knække dette tal med, og nu vil jeg gerne høre om der
> er nogen der har noget erfaring med denne algoritme
>
> Jeg kender ikke noget til kørselstider, så hvis jeg har sat mig en umulig
> opgave for, vil jeg blive glad for hvis nogen kan fortælle mig det. Hvis det
> ikke er en håbløs opgave, hvor lang tid kan jeg så regne med at skulle bruge
> hvis jeg har 4 PC'ere (500-1200 MHz) til rådighed?
>
> -----
> Jes Hansen
>
>

---

Scripsit Glenn Moeller-Holst <glenn@c.dk>

> Faktorisering af tal bestående af store primtal (mere end ca.40-56 bit),
> anses en svær opgave.

Det er let nok at faktorisere store primtal. Her er en
konstanttidsalgoritme:

fn x => [x]

Den er naturligvis kun garanteret at virke kun når inddata *er* et
stort primtal. (I min praktiske erfaring synes den også at virke på
små primtal, men det har jeg ikke bevist).

--
Henning Makholm "Joyce! May! Wayne! Carol! Majored!"

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Glenn Moeller-Holst <glenn@c.dk>
>
> > Faktorisering af tal bestående af store primtal (mere end ca.40-56 bit),
> > anses en svær opgave.
>
> Det er let nok at faktorisere store primtal.

Det ved vi, men han sagde altså "tal *bestående* af store primtal".
Ikke særlig præcist, men ikke nødvendigvis det samme som "store
primtal".

> Her er en konstanttidsalgoritme:
>
> fn x => [x]
>
> Den er naturligvis kun garanteret at virke kun når inddata *er* et
> stort primtal.

Har du en ML-fortolker med bignums? :)

> (I min praktiske erfaring synes den også at virke på
> små primtal, men det har jeg ikke bevist).

Induktion! Virker på to. Virker på tre. Så passer det nok for resten
også.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

Scripsit Lasse Reichstein Nielsen <lrn@hotpop.com>
> Henning Makholm <henning@makholm.net> writes:
> > Scripsit Glenn Moeller-Holst <glenn@c.dk>

> > > Faktorisering af tal bestående af store primtal (mere end ca.40-56 bit),
> > > anses en svær opgave.

> > Det er let nok at faktorisere store primtal.

> Det ved vi, men han sagde altså "tal *bestående* af store primtal".

Ak. Jeg går lige ud og graver mig ned. Vælt nu ikke møblementet før
jeg kommer tilbage.

--
Henning Makholm "We can build reactors, we can melt
ice. Or engineers can be sent north for
re-education until they *do* understand ice."

---

Henning Makholm wrote:
>
> Den er naturligvis kun garanteret at virke kun når inddata *er* et
> stort primtal. (I min praktiske erfaring synes den også at virke på
> små primtal, men det har jeg ikke bevist).

Nej, det ser heller ikke ud til at dit bevis sådan uden videre kan
generaliseres til også at omfatte små primtal. Heldigvis er langt de
fleste (nemlig næsten alle) primtal store.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>

> Heldigvis er langt de fleste (nemlig næsten alle) primtal store.

Hm, hvilket mål på mængden af primtal bruger du til at nå den
konklusion?

--
Henning Makholm "Hele toget raslede imens Sjælland fór forbi."

---

Henning Makholm wrote:
>
> > Heldigvis er langt de fleste (nemlig næsten alle) primtal store.
>
> Hm, hvilket mål på mængden af primtal bruger du til at nå den
> konklusion?

Ups ...

Jeg brugte vel det mål m der fastlægges ved at m({p}) er 1 hvis p er
stor, og 0 ellers. Altså tællemålet hvor man ser bort fra småting.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Jeppe Stig Nielsen wrote :

> Nej, det ser heller ikke ud til at dit bevis sådan uden videre kan
> generaliseres til også at omfatte små primtal. Heldigvis er langt de
> fleste (nemlig næsten alle) primtal store.

Det var skisme da en sjov udtalelse ... at de fleste primtal er "store" :).
I forhold til hvad ?

--
Jesper Stocholm - www.stocholm.dk - www.asp-faq.dk
** De andre siger, at han er 16 **
Svar venligst til gruppen og ikke til mig privat !
Skriv under det du svarer på - www.usenet.dk/netikette/citatteknik.html

---

Scripsit Jesper Stocholm
> Jeppe Stig Nielsen wrote :

> > Heldigvis er langt de fleste (nemlig næsten alle) primtal store.

> I forhold til hvad ?

Én, mange.

--
Henning Makholm "Al lykken er i ét ord: Overvægtig!"

---

Jesper Stocholm <er.det.virkeligt.nødvendigt.at.medtage.min.emailadresse.i.svar.på.mine.indlæg?@stocholm.invalid> writes:

> > Nej, det ser heller ikke ud til at dit bevis sådan uden videre kan
> > generaliseres til også at omfatte små primtal. Heldigvis er langt de
> > fleste (nemlig næsten alle) primtal store.
>
> Det var skisme da en sjov udtalelse ... at de fleste primtal er
> "store" :). I forhold til hvad ?

Der er uendeligt mange store primtal, men kun endeligt mange små (for
alle meningsfulde definitioner af "stor" og "lille").

---

Soeren Sandmann wrote :

> Jesper Stocholm
> <er.det.virkeligt.nødvendigt.at.medtage.min.emailadresse.i.svar.på.mine
> .indlæg?@stocholm.invalid> writes:
>
>> > Nej, det ser heller ikke ud til at dit bevis sådan uden videre kan
>> > generaliseres til også at omfatte små primtal. Heldigvis er langt
>> > de fleste (nemlig næsten alle) primtal store.
>>
>> Det var skisme da en sjov udtalelse ... at de fleste primtal er
>> "store" :). I forhold til hvad ?
>
> Der er uendeligt mange store primtal, men kun endeligt mange små (for
> alle meningsfulde definitioner af "stor" og "lille").

Jowjow, men der findes jo også eksempler på legemer, hvor det slet ikke
giver mening at tale om stor/lille, mindre/mindst. Derfor afhænger
"meningsfulde definitioner" jo ikke alene af øjnene, der ser - men mindst
lige så meget af det betragtede legeme/ring.

[ok - jeg ved godt, at det var lidt ud ad en tangent]

Giv mig i øvrigt lige en konkret anvendelsesmulighed af dit svar - dvs
ikke blot til brug i talteoretiske betragtninger om endelighed kontra
uendelighed, tællelighed kontra utællelighed etc.

ja, se jeg blev lidt forvirret over, at denne tråd foregår i to fora -
det havde jeg lige overset [1].

[1] FUT er sat til dk.edb.programmering (hvor jeg synes det er mest
interessant at diskutere konkrete implikationer af valg af
faktoriseringsalgoritmer).



--
Jesper Stocholm - http://stocholm.dk
if you are competing with the darknet, you must compete on the darknet's
own terms: that is convenience and low cost rather than additional
security. ( http://crypto.stanford.edu/DRM2002/darknet5.doc )

---

In <Xns9302E4529DF7spamstocholmdk@130.226.1.34> Jesper Stocholm <er.det.virkeligt.nødvendigt.at.medtage.min.emailadresse.i.svar.på.mine.indlæg?@stocholm.invalid> writes:

>Jeppe Stig Nielsen wrote :

>> Nej, det ser heller ikke ud til at dit bevis sådan uden videre kan
>> generaliseres til også at omfatte små primtal. Heldigvis er langt de
>> fleste (nemlig næsten alle) primtal store.

>Det var skisme da en sjov udtalelse ... at de fleste primtal er "store" :).
>I forhold til hvad ?

De fleste primtal er stoerre end enhver konstant vaerdi, du kan komme
op med.

/Martin

---

Martin Moller Pedersen wrote:
>
> De fleste primtal er stoerre end enhver konstant vaerdi, du kan komme
> op med.

Til gengæld er der sikkert længe til nogen kommer op med et konkret
primtal der er større end 2^(2^(2^(2^(2^2)))). (Men fjern ét trin i
dette potenstårn, og du får en grænse som allerede blev overskredet
for godt tyve år siden.)

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Scripsit tusk@daimi.au.dk (Martin Moller Pedersen)

> De fleste primtal er stoerre end enhver konstant vaerdi, du kan komme
> op med.

Jo, men det er ikke det samme som "næsten alle".

--
Henning Makholm "Jeg har tydeligt gjort opmærksom på, at man ved at
følge den vej kun bliver gennemsnitligt ca. 48 år gammel,
og at man sætter sin sociale situation ganske overstyr og, så
vidt jeg kan overskue, dør i dybeste ulykkelighed og elendighed."

---

Henning Makholm wrote:
>
> > De fleste primtal er stoerre end enhver konstant vaerdi, du kan komme
> > op med.
>
> Jo, men det er ikke det samme som "næsten alle".

Nu er den målteoretiske betydning af »næsten alle« jo ikke særligt
interessant i et typisk, tælleligt målrum. Så kan vi ikke bare ind-
føre et kort udtryk for »alle undtagen endeligt mange«?
Vi har dog udtrykket »alle fra et vist trin«.

Vi har også brug for et udtryk der betyder »så mange at forholdet
mellem antallet under en vis grænse N og antal mulige går mod 1 når
N går mod uendelig«. Hvis vi brugte »næsten alle« i denne betydning,
kunne vi fx sige at næsten alle naturlige tal er sammensatte tal.

Det sidste skulle måske hedde »asymptotisk alle«.

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

In <yah65srlxoh.fsf@tyr.diku.dk> Henning Makholm <henning@makholm.net> writes:

>Scripsit tusk@daimi.au.dk (Martin Moller Pedersen)

>> De fleste primtal er stoerre end enhver konstant vaerdi, du kan komme
>> op med.

>Jo, men det er ikke det samme som "næsten alle".

Hvis P(x) er antallet af primtal mindre end x og Q(x) er antallet
af primtal stoerre end x, saa er

Saa er Q(x) uendelig mange gange stoerre end P(x).

/Martin

---

Martin Moller Pedersen wrote:
>
> Q(x) er antallet af primtal stoerre end x,

Så Q har værdimængden {+oo} ...

--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

---

Glenn Moeller-Holst <glenn@c.dk> writes:

> Faktorisering af tal bestående af store primtal (mere end ca.40-56
> bit), anses en svær opgave. Grunden er at faktorisering i dag anses
> for et NP (Non-Polynomial) problem.

Nej, det er ikke grunden, det er en konsekvens af at det er et svært
problem. Bemærk at det aldrig er bevist at primtalsfaktorisering er i
NP.

Er du i øvrigt også venlig at læse og efterleve hvad der står på
<http://usenet.dk/netikette/citatteknik.html>.

--
Jacob - www.bunk.cc
One person's error is another person's data.

---

Jacob Bunk Nielsen <spam@bunk.cc> writes:

> Glenn Moeller-Holst <glenn@c.dk> writes:
>
> > Faktorisering af tal bestående af store primtal (mere end ca.40-56
> > bit), anses en svær opgave. Grunden er at faktorisering i dag anses
> > for et NP (Non-Polynomial) problem.
>
> Nej, det er ikke grunden, det er en konsekvens af at det er et svært
> problem.

Det kunne læse som grunden til at det *anses* for en svær opgave, og
så er det jo rigtigt.

NP står i øvrigt for "Nondeterministic Polynomial" og er klassen af
(familier af) afgørlighedsproblemer (problemer med ja/nej svar) der
kan afgøres af en nondeterministisk Turingmaskine i polynomiel tid
(phew).

Specielt står det *ikke* for "non-polynomial". Det er dog rigtigt at
manglen på nondeterministiske Turingmaskiner i praksis betyder at vi
ikke kender effektive, polynomielle algoritmer.

> Bemærk at det aldrig er bevist at primtalsfaktorisering er i
> NP.

Pedanteri: NP er en klasse af problemer med ja/nej svar, så
primtalsfaktorisering er naturligvis ikke i den.

Lidt mere generelt, så kan faktorisering klares af en
nondeterministisk Turingmaskine i polynomiel tid, og den NP-algoritme
man har til at vise at et tal er sammensat finder netop faktorerne som
del af opgaven med at svare ja eller nej. Det er nok det man sædvanligvis
tænker på når man siger at faktorisering er i NP, og det er bevist.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

Scripsit Lasse Reichstein Nielsen <lrn@hotpop.com>

> > Bemærk at det aldrig er bevist at primtalsfaktorisering er i
> > NP.

> Pedanteri: NP er en klasse af problemer med ja/nej svar, så
> primtalsfaktorisering er naturligvis ikke i den.

Men man kan omformulere spørgsmålet, så det *bliver* en serie af
ja/nej-spørgsmål?

Er der netop 4 faktorer?
Er bit nummer 5 i den tredjestørste faktor et 1?
Og så videre.

Alle disse problemer er efter min bedste overbevisning i NP.

--
Henning Makholm "Den nyttige hjemmedatamat er og forbliver en myte.
Generelt kan der ikke peges på databehandlingsopgaver af
en sådan størrelsesorden og af en karaktér, som berettiger
forestillingerne om den nye hjemme- og husholdningsteknologi."

---

Henning Makholm <henning@makholm.net> writes:

> Men man kan omformulere spørgsmålet, så det *bliver* en serie af
> ja/nej-spørgsmål?
>
> Er der netop 4 faktorer?
> Er bit nummer 5 i den tredjestørste faktor et 1?
> Og så videre.
>
> Alle disse problemer er efter min bedste overbevisning i NP.

Det er de klart, da en non-deterministisk TM kan starte med at
skrive de rigtige faktorer ud, kontrollere at de er rigtige,
og så svare på spørgsmålet.

Man kan endda nøjes med polynomielt mange spørgsmål, hvilket
også er vigtigt.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

Scripsit Jacob Bunk Nielsen <spam@bunk.cc>

> Bemærk at det aldrig er bevist at primtalsfaktorisering er i NP.

Engang i efteråret gik der rygter om at der var fundet en polynomiel
primtalstest. Hvis det er rigtigt (jeg skrev artiklen ud, men forstod
den ikke godt nok til at stole på den uden videre), følger det let
at primtalsfaktorisering er NP.

For det er jo let at tjekke i polynomiel tid om en en påstået liste af
faktorer faktisk ganger sammen til det ønskede produkt.

--
Henning Makholm "Hvorfor skulle jeg tale som en slave og en tåbe? Jeg
ønsker ikke, at han skal leve evigt, og jeg ved, at han ikke
kommer til at leve evigt, uanset om jeg ønsker det eller ej."

---

Henning Makholm <henning@makholm.net> writes:

> Scripsit Jacob Bunk Nielsen <spam@bunk.cc>
>
> > Bemærk at det aldrig er bevist at primtalsfaktorisering er i NP.
>
> Engang i efteråret gik der rygter om at der var fundet en polynomiel
> primtalstest. Hvis det er rigtigt (jeg skrev artiklen ud, men forstod
> den ikke godt nok til at stole på den uden videre), følger det let
> at primtalsfaktorisering er NP.
>
> For det er jo let at tjekke i polynomiel tid om en en påstået liste af
> faktorer faktisk ganger sammen til det ønskede produkt.

Jeg må indrømme at jeg har svært ved at se, hvordan du udfra "For det
er jo let at tjekke i polynomiel tid om en en påstået liste af
faktorer faktisk ganger sammen til det ønskede produkt." og det nu
veletablerede faktum at man kan kontrollere om n er et primtal eller
sammensat i polynomiel tid, konkluderer at prim_faktorisering_ er
NP-svært. At man "nemt" kan afgøre om et tal er primtal eller ej
betyder umiddelbart intet for hvor nemt eller svært det i tilfælde af
"ej" er at finde en liste med primfaktorer(ne); men det er nemt at
kontrollere om listen er rigtig.

Mvh
Rasmus Villemoes

--

---

Scripsit Rasmus Villemoes <burner+usenet@imf.au.dk>
> Henning Makholm <henning@makholm.net> writes:

> > Engang i efteråret gik der rygter om at der var fundet en polynomiel
> > primtalstest. Hvis det er rigtigt (jeg skrev artiklen ud, men forstod
> > den ikke godt nok til at stole på den uden videre), følger det let
> > at primtalsfaktorisering er NP.

> Jeg må indrømme at jeg har svært ved at se, hvordan du udfra "For det
> er jo let at tjekke i polynomiel tid om en en påstået liste af
> faktorer faktisk ganger sammen til det ønskede produkt." og det nu
> veletablerede faktum at man kan kontrollere om n er et primtal eller
> sammensat i polynomiel tid, konkluderer at prim_faktorisering_ er
> NP-svært.

Det konkluderer jeg heller ikke. Jeg konkluderer kun at det er i NP.

> At man "nemt" kan afgøre om et tal er primtal eller ej betyder
> umiddelbart intet for hvor nemt eller svært det i tilfælde af "ej"
> er at finde en liste med primfaktorer(ne); men det er nemt at
> kontrollere om listen er rigtig.

Hvilket jo netop er definitionen på NP.

--
Henning Makholm "We will discuss your youth another time."

---

Glenn Moeller-Holst <glenn@c.dk> writes:

> Jeg undskylder, hvis du ikke umiddelbart kunne se af mit tidligere
> svar, at det var ironisk ment, at du kunne faktorisere et 120-cifret
> (bits?), med 4 PC'ere.

Det tal Anders er interesseret i har, når det er skrevet i
titalssystemet, 120 cifre. Det er ikke bare et 120bits tal, tilgengæld
vides det er tallet er et produkt af to primtal med 60 cifre.

Tallet er 403.973[108 udeladte cifre]137.003

--
Peter Makholm | We constantly have to keep in mind why natural
peter@makholm.net | languages are good at what they're good at. And to
http://hacking.dk | never forget that Perl is a human language first,
| and a computer language second