Raskeste prim-sjekk? (Programmering)

Det er god trening å prate matematikk. Her er det fritt fram for alle. Obs: Ikke spør om hjelp til oppgaver i dette underforumet.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Gjennom noen Project Euler-oppgaver blir man nødt til å avgjøre om enkelte enorme tall er primtall.

En kjapp og naiv sjekk er å prøve å dividere tallet $n$ med alle tall $2\ldots n-1$, som deretter kan videre forbedres ved å gjøre enkelte observasjoner, som at man ikke trenger å sjekke lengre enn til $\sqrt n$ og man trenger kun å sjekke oddetall etter $2$. Så divisjon med $2, 3, 5, 7, \ldots, \sqrt{n-1}$.

Men jeg merker at til tross for at man her kun tester ett tall, så er det enda kjappere å bruke Eratosthenes' sil. Kjappere, men med større minnebruk.

https://no.wikipedia.org/wiki/Eratosthenes%27_sil

Er det noen som er kjent med enda raskere sjekker? Eventuelt forbedringer på den naive fremgangsmåten?
Bilde
Gustav
Tyrann
Tyrann
Innlegg: 4555
Registrert: 12/12-2008 12:44

https://en.wikipedia.org/wiki/AKS_primality_test

Edit: Virker som AKS ikke er en god metode i praksis. En modifisert versjon AKS, av Lenstra og Pomerance, skal visst være rask: https://www.math.dartmouth.edu/~carlp/P ... xity12.pdf . Ellers virker det som probabilistiske tester er raske, som Miller-Rabin og Baillie-PSW https://en.wikipedia.org/wiki/Baillie%E ... ality_test, for å vise at tall er sammensatte.
Leonhard_Euler
Noether
Noether
Innlegg: 24
Registrert: 26/03-2018 18:50

Jeg har ikke et svar, men jeg lurte på hvorfor man ikke trenger å sjekke lengre enn til [tex]\sqrt{n}[/tex] ?
[tex]\ln(-1)=i\pi[/tex]
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Leonhard_Euler skrev:Jeg har ikke et svar, men jeg lurte på hvorfor man ikke trenger å sjekke lengre enn til [tex]\sqrt{n}[/tex] ?
Kort sagt:

Vi vet at $n = \sqrt n \cdot \sqrt n$.

Derfor vet vi også at dersom det finnes en primfaktor $ p_1 > \sqrt n$, så må denne ganges med et primtall $p_2 < \sqrt n$.

Dermed vet vi at hvis vi ikke finner noen primfaktorer $p < \sqrt n$ som deler $n$, så finner vi heller ingen som er større, så vi kan slutte å lete når vi har nådd, og sjekka $\sqrt n$.

Jeg ville vært overraska dersom dette holdt som et bevis, men det var bare en formulering av ideen.
Bilde
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Gustav skrev:https://en.wikipedia.org/wiki/AKS_primality_test

Edit: Virker som AKS ikke er en god metode i praksis. En modifisert versjon AKS, av Lenstra og Pomerance, skal visst være rask: https://www.math.dartmouth.edu/~carlp/P ... xity12.pdf . Ellers virker det som probabilistiske tester er raske, som Miller-Rabin og Baillie-PSW https://en.wikipedia.org/wiki/Baillie%E ... ality_test, for å vise at tall er sammensatte.
Jeg dykka litt ned i hullet selv før jeg nå så editen. Det virker som en lett implementerbar metode, men ikke blant de kjappe.

Skal ta en titt på de andre du nevner. Takk!
Bilde
Nebuchadnezzar
Fibonacci
Fibonacci
Innlegg: 5648
Registrert: 24/05-2009 14:16
Sted: NTNU

Enkleste og beste opp til relativt store tall er bare å kjøre Miller-Rabbin. Koden under er deterministisk frem til 341550071728321 også er den probabilistisk.

Kode: Velg alt

def _try_composite(a, d, n, s):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2**i * d, n) == n-1:
            return False
    return True # n  is definitely composite
 
def is_prime(n, _precision_for_huge_n=16):
    if n in _known_primes or n in (0, 1):
        return True
    if any((n % p) == 0 for p in _known_primes):
        return False
    d, s = n - 1, 0
    while not d % 2:
        d, s = d >> 1, s + 1
    # Returns exact according to http://primes.utm.edu/prove/prove2_3.html
    if n < 1373653: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3))
    if n < 25326001: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))
    if n < 118670087467: 
        if n == 3215031751: 
            return False
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7))
    if n < 2152302898747: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
    if n < 3474749660383: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
    if n < 341550071728321: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
    # otherwise
    return not any(_try_composite(a, d, n, s) 
                   for a in _known_primes[:_precision_for_huge_n])
 
_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Kode: Velg alt

if n in _known_primes or n in (0, 1):
        return True
Sann for 0 og 1?
Bilde
Nebuchadnezzar
Fibonacci
Fibonacci
Innlegg: 5648
Registrert: 24/05-2009 14:16
Sted: NTNU

Tok koden for Rosetta, sjekket ikke så nøye :p
"Å vite hva man ikke vet er og en slags allvitenhet" - Piet Hein
https://s.ntnu.no/Integralkokeboken
Lektor - Matematikk, Fysikk og Informatikk
Svar