---

Hej alle

Jeg spørger i både dk.edb.programmering og dk.videnskab med fut
til dk.edb.programmering.

Jeg kender den 'banale' måde at tjekke primtal på:
Prøv med divisorer op til og med kvadratroden af tallet. Hvis én
af dem går op, er det ikke et primtal.

Jeg skrev et program til min TI-89 til at tjekke mersenneprimtal,
og så tænkte jeg at jeg ville speede skidtet op ved at skrive det
i C på min pc. Jeg gik dog hurtigt over til Python i stedet.

Stor var min overraskelse da pc'en (på 0,9 GHz) stod og knoklede
løs på den håbløse opgave at tjekke divisorer op til 10^9 for at
kontrollere 2^61-1, mens TI-89 for længst havde meddelt at
2^107-1 var et primtal og var ved at kontrollere endnu større
potenser. Nu kikkede jeg igen. 2^127 er også et mersenneprimtal.

Findes der en hurtigere algoritme end den jeg kender? Godt nok
kan TI måske implementere en del kode i hardware, måske enda helt
nede i mikrokoden, men alligevel ...

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

Bertel Lund Hansen skrev

> Jeg kender den 'banale' måde at tjekke primtal på:
> Prøv med divisorer op til og med kvadratroden af tallet. Hvis én
> af dem går op, er det ikke et primtal.

> [...]

> Findes der en hurtigere algoritme end den jeg kender? Godt nok
> kan TI måske implementere en del kode i hardware, måske enda helt
> nede i mikrokoden, men alligevel ...

Har du minimeret antallet af operationer i løkken til 3 additioner
(inkl. 2 test) og 1 division?

Der kan også være en del at hente ved at lægge fx. primtalsdivisorer op
til fx. 1000 i en tabel og først skifte til at teste med ulige divisorer
når disse er "brugt op".


Mvh,
--
Filip Larsen

---

"Bertel Lund Hansen" <nospamius@lundhansen.dk> skrev i en meddelelse news:7ja990t2k2m6cconbrbfd91d5qvo5a0pvi@news.stofanet.dk...
>
> Findes der en hurtigere algoritme end den jeg kender? Godt nok
> kan TI måske implementere en del kode i hardware, måske enda helt
> nede i mikrokoden, men alligevel ...
>
Er det Lucas-Lehmer. Den kører hurtigere end et blink
med øjet hos mig (i BASIC).

Mvh
Martin

---

Martin Larsen wrote:
>
> Er det Lucas-Lehmer. Den kører hurtigere end et blink
> med øjet hos mig (i BASIC).

Nej, jeg tror Bertel afprøver alle tal indtil kvadratroden af det
testede tal for at se om der er en divisor. Den metode er under alle
omstændigheder ekstremt ineffektiv.

For alle tal findes der mere effektive metoder end den foreslåede.

Men specielt for Mersenne-tal 2^p - 1 hvor eksponenten er et primtal,
findes der altså en simpel, hurtig test, Lucas-Lehmer-testen:
http://primes.utm.edu/notes/proofs/LucasLehmer.html

For at tjekke om 2^61-1 er primtal, skal man altså blot gøre sådan:

S := 4
GENTAG (61-2) gange
S := ( S^2 - 2 modulo 2305843009213693951 )
SLUT(GENTAG)
HVIS S=0 (modulo 2305843009213693951)
UDSKRIV "Primtal"
ELLERS
UDSKRIV "Sammensat tal"
SLUT(HVIS)

Løkken skal kun gennemløbes 59 gange.

--
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)

---

Bertel Lund Hansen <nospamius@lundhansen.dk> writes:

> Jeg kender den 'banale' måde at tjekke primtal på:
> Prøv med divisorer op til og med kvadratroden af tallet. Hvis én
> af dem går op, er det ikke et primtal.
>
> Findes der en hurtigere algoritme end den jeg kender?

Ja. Den metode, du beskriver, kræver tid, der er eksponentiel i
antallet af cifre i tallet. Der findes metoder, der er polynomielle i
antallet af cifre. De fleste af disse er probabilistisk polynomielle
(dvs., at tiden med meget stor sandsynlighed er polynomiel, men at man
i særlige tilfælde kan ryge op i eksponentiel tid), men i 2002 blev en
algoritme, der er garanteret polynomiel for alle tal publiceret. Se
http://mathworld.wolfram.com/AKSPrimalityTest.html eller
http://encyclopedia.thefreedictionary.com/Cyclotomic%20AKS%20test .

Selv om man altså i polynomiel tid kan afgøre om et tal er primisk,
kendes der ingen polynomiel algoritme til at finde primfaktorerne i
ikke-primiske tal. Det er dog ikke bevist, at der ikke findes en
sådan algoritme (det er en af de store åbne problemer i
kompleksitetsteori).

   Torben

---

"Torben Ægidius Mogensen" wrote:
>
> Ja. Den metode, du beskriver, kræver tid, der er eksponentiel i
> antallet af cifre i tallet. Der findes metoder, der er polynomielle i
> antallet af cifre. De fleste af disse er probabilistisk polynomielle
> (dvs., at tiden med meget stor sandsynlighed er polynomiel, men at man
> i særlige tilfælde kan ryge op i eksponentiel tid), men i 2002 blev en
> algoritme, der er garanteret polynomiel for alle tal publiceret. Se
> http://mathworld.wolfram.com/AKSPrimalityTest.html eller
> http://encyclopedia.thefreedictionary.com/Cyclotomic%20AKS%20test .

Fra den første side linkes der jo også til ophavsmændene selv i Indien:
http://www.cse.iitk.ac.in/news/primality.html


--
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)