Alkulukutestit

Tarkoitin, eli 'iff'-testejä. Lisäinfoa kaivataan. En pysty pureutumaan riittävästi matemaattiseen kirjallisuuteen, jotta asiaa voisi tutkia tarkemmin ja internetlähteet antavat monesti epätarkkoja selostuksia.

Kiitän vastauksista.

Gäyss kirjoitti:

Tarkoitin, eli 'iff'-testejä. Lisäinfoa kaivataan. En pysty pureutumaan riittävästi matemaattiseen kirjallisuuteen, jotta asiaa voisi tutkia tarkemmin ja internetlähteet antavat monesti epätarkkoja selostuksia.

Kiitän vastauksista.

Esim. ns. Fermat'n pieni teoreema toimii alkuluvuille, mutta sen avulla ei ilmeisesti voi automaattisesti todentaa alkulukuja. Sama pätee sen suppeammalle muodolle (eli kiinalaisten versiolle aiheesta).

Lähteet:
http://en.wikipedia.org/wiki/Fermat's_little_theorem
http://mathworld.wolfram.com/FermatsLittleTheorem.html

Gäyss kirjoitti:

Tarkoitin, eli 'iff'-testejä. Lisäinfoa kaivataan. En pysty pureutumaan riittävästi matemaattiseen kirjallisuuteen, jotta asiaa voisi tutkia tarkemmin ja internetlähteet antavat monesti epätarkkoja selostuksia.

Kiitän vastauksista.

Alkulukutesteiksi sanotaan menetelmiä jotka eivät suorita luvun tekijöihin jakoa ja silti selvittävät onko kyseessä alkuluku vai ei.

Ne jaetaan deterministisiin ja probabilistisiin
ensimmäiset ovat ne mitä sinä haet

Ja seuraavia algoritmeja löytyy:
-Lucas-Lehmer-testi
-Elliptisten käyrien alkulukutesti (elliptic curve primality proving) (paras tunnettu)
-Agrawal-Kayal-Saxena-alkulukutesti tai AKS-alkulukutesti (algoritmi joka osoitti että alkulukutesti on laskentavaativuudeltaan luokassa P, eikä vain NP)


probabilistisia on
-Rabin-Millerin testi
-Lucasin testi

ffffffffffs kirjoitti:

Alkulukutesteiksi sanotaan menetelmiä jotka eivät suorita luvun tekijöihin jakoa ja silti selvittävät onko kyseessä alkuluku vai ei.

Ne jaetaan deterministisiin ja probabilistisiin
ensimmäiset ovat ne mitä sinä haet

Ja seuraavia algoritmeja löytyy:
-Lucas-Lehmer-testi
-Elliptisten käyrien alkulukutesti (elliptic curve primality proving) (paras tunnettu)
-Agrawal-Kayal-Saxena-alkulukutesti tai AKS-alkulukutesti (algoritmi joka osoitti että alkulukutesti on laskentavaativuudeltaan luokassa P, eikä vain NP)


probabilistisia on
-Rabin-Millerin testi
-Lucasin testi

Kiitän...

Olen pahasti koukussa ko. lukuihin, ilmeisesti tarttuvaa...;

ffffffffffs kirjoitti:

Alkulukutesteiksi sanotaan menetelmiä jotka eivät suorita luvun tekijöihin jakoa ja silti selvittävät onko kyseessä alkuluku vai ei.

Ne jaetaan deterministisiin ja probabilistisiin
ensimmäiset ovat ne mitä sinä haet

Ja seuraavia algoritmeja löytyy:
-Lucas-Lehmer-testi
-Elliptisten käyrien alkulukutesti (elliptic curve primality proving) (paras tunnettu)
-Agrawal-Kayal-Saxena-alkulukutesti tai AKS-alkulukutesti (algoritmi joka osoitti että alkulukutesti on laskentavaativuudeltaan luokassa P, eikä vain NP)


probabilistisia on
-Rabin-Millerin testi
-Lucasin testi

Onko elliptisten käyrien alkulukutesti paras tunnettu? Mielestäni asymptoottisesti nopein testi, joka toimii mielivaltaiselle positiiviselle kokonaisluvulle, on yleinen lukukuntaseula -testi. Elliptisten käyrien testillä saa kuitenkin parinkymmenen desimaalin pituiset alkutekijät nopeasti selville.

mahtimatemaatikko kirjoitti:

Onko elliptisten käyrien alkulukutesti paras tunnettu? Mielestäni asymptoottisesti nopein testi, joka toimii mielivaltaiselle positiiviselle kokonaisluvulle, on yleinen lukukuntaseula -testi. Elliptisten käyrien testillä saa kuitenkin parinkymmenen desimaalin pituiset alkutekijät nopeasti selville.

Yleinen lukukuntaseula on tekijöihinjakamismenetelmä, ei alkulukutesti.

Uunokki kirjoitti:

Yleinen lukukuntaseula on tekijöihinjakamismenetelmä, ei alkulukutesti.

Näin luulen itsekin.

Olen ymmärtänyt, että eräällä testillä on ko. 'joss' - ominaisuus: jos alkuluvulle N pätee

(N-1)! 1 = 0 (mod N),

on kyseessä alkuluku.

Gäyss kirjoitti:

Näin luulen itsekin.

Olen ymmärtänyt, että eräällä testillä on ko. 'joss' - ominaisuus: jos alkuluvulle N pätee

(N-1)! 1 = 0 (mod N),

on kyseessä alkuluku.

Kyseessähän on Wilsonin lause: luku n>1 on alkuluku joss
(n-1)! = -1 (mod n).
Tästähän saisi aikaan alkulukutestin, mikäli kertoman (n-1)! laskenta olisi tehokasta. Täten Wilsonin lause on alkulukutestauksessa lähinnä kuriositeetti.

Al-Haytham kirjoitti:

Kyseessähän on Wilsonin lause: luku n>1 on alkuluku joss
(n-1)! = -1 (mod n).
Tästähän saisi aikaan alkulukutestin, mikäli kertoman (n-1)! laskenta olisi tehokasta. Täten Wilsonin lause on alkulukutestauksessa lähinnä kuriositeetti.

Oheinen linkki jo lienee tuttu kaikille:
http://mathworld.wolfram.com/topics/PrimalityTesting.html

Mielenkiintoista sinänsä, että varsinaisia molempiin suuntiin toimivia testejä ei ole kovin montaa. Ja tuon kertoman laskeminen on todellinen ongelma isoille luvuille.

Gäyss kirjoitti:

Oheinen linkki jo lienee tuttu kaikille:
http://mathworld.wolfram.com/topics/PrimalityTesting.html

Mielenkiintoista sinänsä, että varsinaisia molempiin suuntiin toimivia testejä ei ole kovin montaa. Ja tuon kertoman laskeminen on todellinen ongelma isoille luvuille.

Kertomaa ei välttämättä ehkä tarvitse laskea, sillä kyseessä on kertoma modulo jokin luku.

Tosin ei kai tunneta muuta menetelmää kuin kertoa lukuja peräkkäin ja ottaa välissä jakojäännös, toistaiseksi? (koskaan?)

fffffs kirjoitti:

Kertomaa ei välttämättä ehkä tarvitse laskea, sillä kyseessä on kertoma modulo jokin luku.

Tosin ei kai tunneta muuta menetelmää kuin kertoa lukuja peräkkäin ja ottaa välissä jakojäännös, toistaiseksi? (koskaan?)

En tiedä kuinka tehokas tämä on laskemaan kertoman moduloita, mutta kaava löytyy osoitteesta http://planetmath.org/encyclopedia/FactorialModulePrimePowers.html

mahtimatemaatikko kirjoitti:

En tiedä kuinka tehokas tämä on laskemaan kertoman moduloita, mutta kaava löytyy osoitteesta http://planetmath.org/encyclopedia/FactorialModulePrimePowers.html

Tuossa tuloksessa oletetaan, että p on alkuluku, joten suoraan alkulukutestauksessa tuota tulosta ei voi käyttää.