Prímteszt

Prímteszten a matematikában vagy informatikában olyan (determinisztikus) algoritmust vagy indeterminisztikus (például valószínűség-elméleti) módszereket is megengedő eljárást értünk, melynek ismeretében bármely adott egész számról, vagy csak bizonyos típusú számokról (véges sok lépésben) el tudjuk dönteni, hogy prímszám-e, vagy pedig összetett. Ettől lényegesen különböző és sokkal nehezebb feladat egy adott szám prímtényezőinek a megtalálása (prímfelbontás).

A következőkben csak a pozitív számok prímteszteléséről fogunk szólni, hisz egy negatív szám akkor és csak akkor prím, ha ellentettje, mint egész szám, szintén prím.

Tetszőleges számok tesztelése

Naiv módszer

A legegyszerűbb módszer a következő: az adott egész számot sorra elosztjuk a nála határozottan kisebb pozitív egész számokkal. Ha van ezek között olyan, 1-től különböző szám, ami az adott egész számnak osztója, akkor a szám nem prím; ellenben viszont, ha nincs, akkor ez a szám egy prímszám.

Egy nagyon primitív pszeudokód formájában a következőképp „algoritmizálhatjuk” ezt:

  1. legyen s=2; és olvassuk be a tesztelendő n egész számot,
  2. ha n=0 vagy n=1, akkor sem nem prím, sem nem összetett; STOP; ha n>2, menjünk 3).-ra
  3. Képezzük az m=<n mod s> maradékot; ha ez 0 és m<n, akkor n nem prím, STOP; ha m=n, akkor n prím, STOP; ha pedig az előző esetek egyike sem teljesül, ekkor tehát m<n és m nem nulla, legyen s=s+1, és menjünk 3).-ra.

Az eljárás elég lassú, de a tárhely növelésével gyorsítható. Ez azon alapul, hogy nem kell a számnál kisebb összes természetes egésszel osztanunk, hanem nyilván elegendő ezt csak a nála kisebb prímekkel megtenni. Ehhez készíteni kell egy prímszámtáblázatot, ami például az eratoszthenészi szita módszerén vagy más szitálási eljárásokon alapulhat. A számokat elég a négyzetgyökükig vizsgálni, hiszen a szorzás kommutatív művelet.

Wilson-prímteszt

Ennek a prímtesztnek, legalábbis ma, csak elméleti jelentősége van; a Wilson-tételen alapul:

n prím.

Azonban ennek használatához az n! faktoriális függvényt kellene számolni, erre viszont jelenleg nincs hatékony eljárás.

Fermat-prímteszt

Ha p prím, akkor osztható p-vel, ahol p nem osztója a-nak.

A Solovay–Strassen-teszt

Egy adott páratlan n számról a következőképpen döntjük el, hogy prím-e: választunk véletlenszerűen egy 0<b<n egész számot. Ezután kiszámítjuk az euklideszi algoritmus segítségével a (b, n) legnagyobb közös osztót. Ha ez egynél nagyobb, akkor készen vagyunk: n összetett szám. Ha nem, akkor kiszámítjuk egyrészt n-nel vett legkisebb abszolút értékű maradékát, másrészt a : Jacobi-szimbólum értékét. Ha n prím, akkor a két értéknek, az Euler-kritérium értelmében, meg kell egyezni. Fontos megjegyezni, hogy noha a Jacobi-szimbólum n prímfelbontása segítségével van definiálva, értéke anélkül is gyorsan kiszámítható. Ha n összetett, akkor legfeljebb 1/2 annak a valószínűsége, hogy véletlen b-re ez a két érték megegyezik. Ezért sokszor ismételjük a fenti próbát véletlenszerűen választott b értékekkel. Ha a két szám akár csak egyszer is eltér, akkor biztosak lehetünk benne, hogy n összetett. Ha viszont mindig megegyeznek, akkor igen nagy valószínűséggel prím.

A Miller–Rabin-teszt

Legyen n a tesztelendő páratlan szám, , t páratlan. Legyen 0<b<n.

vagy van olyan , hogy .

Ha n prímszám, akkor a fenti állítás minden b-re teljesül; ha n összetett, akkor ez legfeljebb a b-k egynegyedére igaz. Ezért véletlenszerűen választunk b értékeket, és ha mondjuk 100 egymásutáni választásra igaz a fenti állítás, akkor n nagy valószínűséggel prím.

(Sokan félreértelmezik a fentieket, és úgy gondolják, hogy sok teszt szükséges. Nem veszik figyelembe, hogy ha n összetett, ami nagyon ritkán fordul elő egy nagyobb, véletlenszerűen választott páratlan számnál - ha az átmegy a teszten. Pl. 2^64-ig 31894014 db (b=2) álprím és 4,25656*10^17 prímszám van, tehát kevesebb, mint 2^(-32) valószínűséggel összetett - pedig csak egy teszt.)

A BPSW-teszt

Kidolgozói, névadói: Robert Baillie, Carl Pomerance, John L. Selfridge, és Samuel S. Wagstaff, Jr.

Jelenleg (2013 július) a leghatékonyabb valószínűségi prímteszt: nem bizonyítja egy szám prím voltát, ha átmegy a teszten, de erősen valószínűsíti: P=99,9999...%. Ellenben bizonyítja az összetettségét, ha bukik rajta.

A BPSW-teszt két teszt kombinációja: egy Miller–Rabin-teszt (b=2, ld. előbb), és egy Lucas-Selfridge teszt. Utóbbinak a lényege, hogy ha n osztója az első Lucas-sor n+1. elemének, azaz

akkor n prím vagy Lucas-álprím.

A BPSW-teszt fő erejét az a tény adja, hogy a rész-teszteknek különböző típusú álprímjei vannak, melyeknek nincs eddig ismert közös eleme, tehát nem ismerünk még olyan összetett számot, amelyik átmenne mindkét teszten. Bizonyított, hogy 264-ig (kb.18 trillió) nincs BPSW-álprím.

Pomerance feltételezi, hogy végtelen sok álprímje van ennek a tesztnek is. Zhuo Chen és John Greene megadott egy 21248 (376 jegyű szám!) elemű számhalmazt, melyben 740 álprím is lehet.

A BPSW-teszt még sokkal erősebbé tehető[1] Lucas-V teszttel, jelentős plusz számítások nélkül:

ahol V a 2. Lucas sor, Q pedig a teszt Selfridge Method A* -gal kiválasztott (=> D, P, Q) paramétere.

Az AKS-algoritmus

2002 augusztusában három indiai matematikus – Manindra Agrawal, Neeraj Kayal és Nitin Saxena – polinomiális prímtesztet talált ki. Ez a prímek következő karakterizációján alapul: Legyen természetes szám, r olyan n-nél kisebb természetes szám, hogy n rendje r-rel osztva nagyobb, mint ( n)2. n pontosan akkor prím, ha:

1. n nem teljes hatvány,
2. n-nek nincs prímtényezője, ami ,
3. teljesül minden egész számra.

Speciális alakú számok tesztelése (Pepin-teszt)

Speciális alakú számokra vannak speciális prímtesztek. Például, ha alakú Fermat-szám (n≥ 1), úgy N prím pontosan akkor, ha

További információk

Jegyzetek

  1. Baillie, Robert, Samuel S. (2021. március 22.). „Strengthening the Baillie-PSW primality test”. Mathematics of Computation 90 (330), 1931–1955. o. DOI:10.1090/mcom/3616. ISSN 0025-5718. 

Források

Read other articles:

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Januari 2023. Rumah tradisional Kedah adalah rumah tradisional masyarakat Kedah. Bentuknya hampir sama dengan rumah tradisional Perlis. Perbedaannya hanya pada susunan ruangannya. Rumah ini juga berbentuk memanjang. Bagian bumbungnya berbentuk panjang dan mendatar. ...

 

تحتاج هذه المقالة كاملةً أو أجزاءً منها لإعادة الكتابة حسبَ أسلوب ويكيبيديا. فضلًا، ساهم بإعادة كتابتها لتتوافق معه. (أبريل 2019) اللغة الفارسية الاسم الذاتي (بالفارسية: فارسی)‏    الناطقون 45000000 (لغة أم) (2007)52939220 (2015)70000000 (2019)[1]  الدول  إيران أفغانستان طاجيكس�...

 

Chronologies Données clés 1596 1597 1598  1599  1600 1601 1602Décennies :1560 1570 1580  1590  1600 1610 1620Siècles :XIVe XVe  XVIe  XVIIe XVIIIeMillénaires :-Ier Ier  IIe  IIIe Chronologies thématiques Art Architecture, Arts plastiques (Dessin, Gravure, Peinture et Sculpture), Littérature et Musique classique   Ingénierie (), Architecture et ()   Politique Droit   Religion (,)   Science Santé et médecine &...

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

 

Radio station in Evansville, Indiana WEOAEvansville, IndianaBroadcast areaEvansville, IndianaFrequency1400 kHzBranding98.5 WEOAProgrammingFormatUrban contemporaryAffiliationsPremiere NetworksOwnershipOwnerBLS Entertainment Inc.HistoryFirst air date1936Former call signsWEOA (1936–1961)WROZ (1961–1986)WIKY (1986–1992)WJPS (1992–1997)Call sign meaningEvansville On the AirTechnical informationFacility ID61042ClassCPower1,000 wattsTranslator(s)98.5 W253BF (Evansville)100.7 W264DM...

 

Species of flowering plant Vendayam and Vendhayam redirect here. For the 2011 film, see Vengayam. Fenugreek Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Clade: Rosids Order: Fabales Family: Fabaceae Subfamily: Faboideae Genus: Trigonella Species: T. foenum-graecum Binomial name Trigonella foenum-graecumL.[1] Fenugreek greens Fenugreek (/ˈfɛnjʊɡriːk/; Trigonella foenum-graecum) is an annual plant in the family Fabaceae, wi...

Highest level of formally licensed sailor This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Master mariner – news · newspapers · books · scholar · JSTOR (July 2014) (Learn how and when to remove this message) A master mariner is a licensed mariner who holds the highest grade of seafarer qualification; namely, ...

 

Peta infrastruktur dan tata guna lahan di Komune Belval.  = Kawasan perkotaan  = Lahan subur  = Padang rumput  = Lahan pertanaman campuran  = Hutan  = Vegetasi perdu  = Lahan basah  = Anak sungaiBelval merupakan sebuah komune di departemen Vosges yang terletak pada sebelah timur laut Prancis. Lihat pula Komune di departemen Vosges Referensi INSEE lbsKomune di departemen Vosges Les Ableuvenettes Ahéville Aingeville Ainvelle Allarmont Ambacourt Ameuvelle...

 

Practice of hunting wolves by humans This article is about hunting of wolves by humans. For the hunting of animals by wolves, see Wolf § Hunting and feeding behaviours. For the novel, see Wolf Hunting. Tapestry depicting a Florentine wolf hunt (c. 14th century), Uffizi Gallery, Florence, Italy Wolf hunting is the practice of hunting wolves. Wolves are mainly hunted for sport, for their skins, to protect livestock and, in some rare cases, to protect humans.[1] Wolves have b...

This article's factual accuracy may be compromised due to out-of-date information. Please help update this article to reflect recent events or newly available information. (February 2012) In the United States, each state maintains its own system of state highways.[a] This is a list of the longest state highways in each state. As of 2007[update], the longest state highway in the nation is Montana Highway 200, which is 706.624 miles (1,137.201 km) long. The shortest of the...

 

Coastal bay in Tanzania Manza BayGhuba la Manza (Swahili)Manza BayLocation in TanzaniaLocation Tanzania, Tanga Region, Mkinga DistrictGroupPemba ChannelCoordinates4°56′35″S 39°9′20″E / 4.94306°S 39.15556°E / -4.94306; 39.15556TypeBayEtymologyManza wardOcean/sea sourcesIndian OceanDesignationProtected waterbodyMax. length9 km (5.6 mi)Max. width8 km (5.0 mi)IslandsKwale IslandSettlementsKwale and Tawalani Manza Bay (Ghuba la Manz...

 

Remote administration and web conferencing software A major contributor to this article appears to have a close connection with its subject. It may require cleanup to comply with Wikipedia's content policies, particularly neutral point of view. Please discuss further on the talk page. (February 2021) (Learn how and when to remove this message) TeamViewerTeamViewer Remote 15 on Windows 11Developer(s)TeamViewer SEStable release(s) [±]Windows (desktop app)15.29.4 / 26 April 2022...

2005 novel by Alicia Gaspar de Alba Desert Blood: The Juárez Murders AuthorAlicia Gaspar de AlbaLanguageEnglishGenremystery, thrillerPublisherArte Publico PressPublication date2005 (first edition)Publication placeUnited StatesMedia typePrintPages346 p.ISBN1558854460OCLC1298730962 Desert Blood: The Juarez Murders is a 2005 mystery thriller by author Alicia Gaspar de Alba based on the violence, kidnapping and femicides that occurred in Ciudad Juarez in 1998. Plot Ivon Villa, a lesbian pro...

 

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Tourism in Romania – news · newspapers · books · scholar · JSTOR (October 2019) (Learn how and when to remove this message) Tourism in RomaniaWebsitehttps://romaniatourism.com/ Number of arrivals Romania's tourism sector had a direct contribution of EUR 5.21 b...

 

  لمعانٍ أخرى، طالع نفر (توضيح). 32°7′37″N 45°13′51″E / 32.12694°N 45.23083°E / 32.12694; 45.23083 نفر موقع اليونيسكو للتراث العالمي   الدولة العراق  المعايير (iii) معيار تقدير القيمة العالمية الاستثنائية  [لغات أخرى]‏،  و(vi) معيار تقدير القيمة العالمية الاستثنائية&#...

Council area of Scotland This article is about a municipal district in Scotland. For other uses, see Midlothian (disambiguation). Edinburghshire redirects here. For other uses, see Edinburghshire (disambiguation). Place in ScotlandMidlothianMidlowdenMeadhan Lodainn Coat of armsCouncil logoCoordinates: 55°53′39″N 3°04′07″W / 55.89417°N 3.06861°W / 55.89417; -3.06861Sovereign stateUnited KingdomCountryScotlandLieutenancy areaMidlothianAdmin HQDalkeithGovernme...

 

History United States NameUSS LST-549 BuilderMissouri Valley Bridge and Iron Company, Evansville, Indiana Laid down4 January 1944 Launched25 February 1944 Sponsored byMrs. E. A. Oberhuber Commissioned5 April 1944 Decommissioned28 February 1946 Stricken5 December 1947 Honors andawardsFour battle stars for World War II FateSold for scrapping 23 May 1948 General characteristics Class and typeLST-542-class tank landing ship Displacement 1,490 long tons (1,514 t) light 4,080 long tons (4,145...

 

Это обзор почтовых марок и истории почты Британской Восточной Африки. Британия имела интересы в этом регионе ещё в 1824 году. Известно, что миссионеры обосновались здесь в 1844 году. В 1887 году Императорская британская восточноафриканская компания получила концессию на упра�...

American animal rights activist Jerry VlasakBorn1958 (age 65–66)NationalityAmericanOccupationAnimal rights activistSpouse Pamelyn Ferdin ​ ​(m. 1986; div. 2008)​ Jerry Vlasak (born c. 1958)[1] is an American animal rights activist and former trauma surgeon. He is a press officer for the North American Animal Liberation Press Office,[2] a former director of the Animal Defense League of Los Angeles, and a former advisor ...

 

Psychoactive chemical OpioidDrug classChemical structure of morphine, the prototypical opioid.[1]Class identifiersUsePain reliefATC codeN02AMode of actionOpioid receptorExternal linksMeSHD000701Legal statusIn Wikidata Opioids are a class of drugs that derive from, or mimic, natural substances found in the opium poppy plant. Opioids work in the brain to produce a variety of effects, including pain relief. As a class of substances, they act on opioid receptors to produce morphine-like e...