Je število praštevilo?

Je število praštevilo?

Avtor: Suzana Nagode

DEFINICIJA: Praštevilo je naravno število, večje od ena, ki ima natanko dva pozitivna deljitelja in sicer 1 in samega sebe.

Praštevila do 1000:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,97, 101,103,107,109,103,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223, 227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353, 359,367,373,379,383,389,397,401,409,419,421,431,439,443,449,457,461,463,467,479,487,491,499, 503,509,521,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653, 659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821, 823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977, 983,991,997 Tabela praštevil do 7919



Trenutno znano največje praštevilo je , odkril ga je Curtis Cooper. To praštevilo so 25.01.2013 tudi potrdili. največje praštevilo

Velika praštevila uporabljajo v kriptografiji.

Poznamo deterministične in verjetnostne algoritme za preverjanje praštevilskosti. Z determinističnim algoritmom dobimo točen odgovor, pri verjetnostnih algoritmih pa lahko trdimo z določeno verjetnostjo, da je neko število res praštevilo.

Naslednji algoritem spada pod deterministične algoritme.

def prastevilo(n):
    d = 2 #zanimajo nas samo deljitelji od 2 naprej
    while d**2 <= n: 
        if n % d == 0: return False #če d|n, je n sestavljeno število
        d += 1
    return n > 1 #je praštevilo, razen če je n == 1

Deterministična metoda program

Število n delimo z vsemi števili na intervalu [ 2, ], ter zmeraj pogledamo ostanek. Če je ostanek enak nič vsaj za eno od teh števil, pomeni da je to število sestavljeno (False), v nasprotnem primeru pa je preštevilo (True). Na koncu preverimo le še, če je število enako 1, v tem primeru vrnemo False.

ERATOSTENOVO REŠETO

S problemom praštevilskosti so se ukvarjali že v antičnem času.

Najstarejši način ugotavljanja, ali je neko število praštevilo, je Eratostenovo rešeto iz leta 240 p. n. š.

Algoritem:

1. Zapišemo vsa števila razen število 1

2. Naj bo a najmanjše število, ki ni prečrtano. Prečrtajmo vsa števila oblike , kjer je .

Če je (se pravi, da preverjamo večkratnike števil do , ker so vsi večkratniki naslednjih števil že prečrtani. Če bi preverjali še tiste, bi samo izgubljali čas), se vrni na točko 2, sicer končaj. Kar ostane neprečrtano, so vsa praštevila med 2 in n.

Primer: Eratostenovo rešeto (primer uporabe)

Idejo Eratostenovega rešeta lahko zlahka zakodiramo s programskim jezikom Python. Dobimo vsa praštevila do števila, ki nas zanima. Glede na to, da je tema moje seminarske: "Ali je število praštevilo", sem program spremenila tako, da na koncu dobimo rešitev True ali False (je ali ni praštevilo), za število ki nas zanima.

Koda programa:

from math import *

def eratostenovoReseto(n): 
    """funkcija za dano število vrne, ali je n praštevilo ali ne
(True ali False)"""
    stevila = [True]*(n+1)
    stevila[1]= False #stevilo 1 ni praštevilo
    for i in range(2, int(sqrt(n))):
        for j in range(i*i, n+1, i):
            if stevila[j] == True:
                stevila[j] = False #če je sestavljeno, spremenimo 0 v 1
    return stevila[n] 

Eratostenovo rešeto program

Najprej naredimo seznam z vrednostmi True, dolžine n+1 (n+1 zato, da ne upoštevamo indeksa 0). Nato pa številom, ki so sestavljana spremenimo vrednost v False. Številu 1 ga spremenimo že na začetku, saj že po sami definiciji Eratostenovega rešeta upoštevamo števila od 2 naprej. Nato za vsa števila od 2 do gledamo večkratnikele teh in v seznamu za vse večkratnike spremenimo vrednost iz True v False, v primeru, da je vrednost enaka True. Če že ima vrednost False, ga pustimo. Na koncu vrnemo vredost n-tega indeksa v seznamu. Vir:Eratostenovo rešeto

Nekaj primerov uporabe:

>>> eratostenovoReseto(97)
True
>>> eratostenovoReseto(997)
True
>>> eratostenovoReseto(13)
True
>>> eratostenovoReseto(53)
True
>>> eratostenovoReseto(105)
False
>>> eratostenovoReseto(1637)
True
>>> eratostenovoReseto(7687)
True
>>> eratostenovoReseto(6969)
False
>>> 

FERMATOV ALGORITEM

Fermat je v 17. stoletju dokazal, da za vsako praštevilo velja: (mod p) za vsako praštevilo p, ki ne deli a. več o Fermatovem malem izreku

Izrek, ki sledi iz Fermatovega malega izreka:

  • Če je p praštevilo, potem za vsako celo število velja (mod p)
  • Če vzamemo poljubno celo število a, izračunamo , nato odštejemo a. Dobimo število, ki je deljivo s p.

Delovanje algoritma:

V primeru, da je uporabnik vnesel število 1, vrnemo False, saj 1 ni praštevilo.

Nato za k naključnih števil izračunamo (mod p). Če je rezultat različen od nič, izračunamo še največji skupni deljitelj števil a in n. V primeru, da je ta različen od 1, pomeni da število ni praštevilo, vrnemo False. Na koncu, ko smo preverili že za vse a-je in število ni sestavljeno (če bi bilo sestavljeno, bi se algoritem končal že praj) vrnemo True, .

Ker preverimo samo k števil, in ne vseh, je to verjetnostni algoritem. Verjetnost da število ni praštevilo, čeprav dobimo odgovor True, je , se pravi v našem algoritmu na naslednji strani imamo k = 20, je verjetnost napake .

Časovna zahtevnost:



(mod p) se v kodi da napisati na dva načina, in sicer:

ostanek = st n

ali pa:



Pri samem času računanja je zelo velika razlika (dva primera):

>>> časi(6011)

5.8334334221621695 (prvi način)

0.04014428189633684 (drugi način)

>>> časi(34649)

742.3786367356798 (prvi način)

0.26117852779532313 (drugi način)

Pri še večjih številih je algoritem, v katerem računamo ostanek na prvi način neučinkovit, saj potrebujemo preveč časa.

Koda programa:

import random, sys
import time

def gcd(a,b):
    """največji skupni deljitelj"""
    while b > 0:
        a, b = b, a % b
    return a

def Fermat(n,k=20):
    """Določanje ali je število praštevilo z malim Fermatovm izrekom
število korakov == n """
    if n<1:
        raise Exception('To ni naravno število')
    if n==1:
        return False
    a = 0
    while a < k:
        st = (a**(n-1))-1
        ostanek = st%n
        if ostanek != 0:
            if gcd(a,n)!=1:
                return False
            else: pass
        a += 1
    return True

def Fermat1(n,k=20):
    """Določanje ali je število praštevilo z malim Fermatovm izrekom
število korakov == n """
    if n<1:
        raise Exception('To ni naravno število')
    if n==1:
        return False
    a = 0
    while a < k:
        st = pow(a,(n-1),n)
        if st != 0:
            if gcd(a,n)!=1:
                return False
            else: pass
        a += 1
    return True

    

Fermatov algoritem program

SLABOST:

Pri tem algoritmu pride tudi do napak. Pri nekaterih številih dobimo odgovor, da je praštevilo, v resnici pa ni. Ta števila imenujemo Charmichaelova števila.

Primeri uporabe:

>>> 
>>> Fermat1(13)
True
>>> Fermat1(51)
False
>>> Fermat1(48112959837082048697)
True
>>> Fermat1(4093082899)
True
>>> Fermat1(9547848065153773335707495885453566120069130270246768806790708393909999)
True
>>> Fermat1(4093083899)
True
>>> Fermat1(4093085899)
False
>>> 

RABIN - MILLER

Rabin- Millerjev test za preverjanje praštevilskosti je eden najučinkovitejših algoritmov. Leta 1980 je Rabin spremenil Millerjev test. Je verjetnostni algoritem (ne preverimo za vse , ampak npr. samo za 20 a-jev, tako lahko še vedno pride do napake, ampak verjetnost za napako je zelo majhna), s časovno zahtevnostjo , kjer je k število korakov algoritma, n pa je število, za katerega preverjamo praštevilskost.

Ta algoritem deluje tako, da najprej določimo s in d tako, da velja:



Nato -krat izračunamo (mod n). Za vsak k potrebujemo naključno število , nato izračunamo (mod n). Z x-om, ki ga dobimo nato s krat izračunamo (mod n)in preverjamo:

V primeru, da je enak 1 in je različen od in število ni praštevilo. -u priredimo vrednost in spet računamo od začetka.

Na koncu preverimo še, če je različen od , v tem primeru število tudi ni praštevilo, v ostalih primerih pa je praštevilo.

Če dobimo rešitev, da je število praštevilo, lahko trdimo z verjetnostjo , da je sestavljeno. Tako npr. pri k = 20, lahko trdimo, da je verjetnost napake 0.003171%

Več o Rabin Millerjevem testu

Koda programa:

import random, sys
    
def rabinMiller(n,k=20):
    """preverjanje praštevilskosti z Rabin-Millerjevim testom"""
    if n < 1:
        raise Exception ("Število n ni naravno število")
    elif n < 2 or n & 1 == 0: return False
    elif n < 4: return True
    else:
        s, d = 0, n-1
        while d & 1 == 0:
            s, d = s + 1, d >> 1
        for i in range(0,k):
            a = random.randint(2,n-1)
            x = pow(a,d,n)
            for i in range(0,s):
                y = pow(x,2,n)
                if y == 1 and x != 1 and x !=(n-1):
                    return False
                x = y
            if y!=1:
                return False                
        return True

Rabin Miller program

Nekaj primerov uporabe

>>> rabinMiller(1500450271)
True
>>> rabinMiller(27542476619900900873)
True
>>> rabinMiller(5991810554633396517767024967580894321153)
True
>>> rabinMiller(9547848065153773335707495885453566120069130270246768806790708393909999)
True 
>>> rabinMiller(13)
True
>>> rabinMiller(15)
False
>>> rabinMiller(1500450275)
False
>>> 

Poglejmo si še hitrosti računanja

Kateri algoritem uporabiti, pri različno velikih številih?

KVIZ

Drugi korak pri Eratostenovem rešetu, za števila od 2 naprej je: (Števila, ki so odebeljena so prečrtana števila po prvem koraku)

2345678910
111213141516171819
202122232425262728
293031323334353637



2, 4, 6, 8, 10, 12...
3, 6, 9, 12, 15, 18...
6, 9, 12, 15, 18...

Odgovor je napačen! Ponovno

Odgovor je pravilen! Naprej

Kateri zapis predstavlja Mali Fermatov izrek:

(mod p)
(mod p)
(mod p)

Odgovor je napačen! Ponovno

Odgovor je pravilen! Naprej

Kateri od naštetih algoritmov je najhitrejši za zelo velika praštevila?

Eratostenovo rešeto
Rabin-Millerjev algoritem
Deterministična metoda

Odgovor je napačen! Ponovno

Odgovor je pravilen! Naprej

Viri:

0%
0%