Raskeste prim-sjekk? (Programmering)

[Aleks855]

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?

[Gustav]

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]

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

[Aleks855]

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.

[Aleks855]

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!

[Nebuchadnezzar]

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.

Code: Select all

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

[Aleks855]

Code: Select all

if n in _known_primes or n in (0, 1):
        return True

Sann for 0 og 1?

[Nebuchadnezzar]

Tok koden for Rosetta, sjekket ikke så nøye :p