Test di Miller-Rabin

Il test di primalità di Miller-Rabin è un test di primalità, ossia un algoritmo per determinare se un numero intero è primo. La sua versione originale, dovuta a Gary Miller, è deterministica, ma dipende dall'ipotesi di Riemann generalizzata, un'importante congettura matematica tuttora aperta. L'algoritmo è stato successivamente modificato da Michael Rabin che ne ha ottenuto una versione probabilistica simile al test di Fermat e al test di Solovay-Strassen.

Definizione

Sia n un numero intero positivo dispari e non primo. I numeri positivi b<n tali che M.C.D.(b,n)=1, e tali che n sia uno pseudoprimo di Eulero forte in base b sono non più di un quarto di tutti i numeri positivi b<n tali che M.C.D.(b,n)=1.

Questo è il test di primalità che stavamo presentando:

Se fisso un intero dispari n>1, lo posso scrivere come , con t dispari. Il test T si sintetizza nei seguenti:

  1. scegliamo a caso un intero b, con 1<b<n, e calcoliamo M.C.D.(b, n);
  2. se M.C.D.(b, n) > 1, allora n non è primo, ed abbiamo finito;
  3. se M.C.D.(b, n) = 1, calcoliamo b (mod n). Se b ≡ +1 (mod n) oppure b ≡ -1 (mod n), n è primo oppure è pseudoprimo forte in base b;
  4. se non vale che b ≡ +1 (mod n) oppure b ≡ -1 (mod n), calcoliamo b (mod n). Se b ≡ -1 (mod n), allora n è pseudoprimo forte in base b;
  5. se non vale che b ≡ -1 (mod n), passiamo a b, e a tutte le altre potenze di 2, moltiplicate per t. Se tutti i b, per r=1,..., s-1, non sono mai congrui a -1 modulo n, allora non è un primo. Altrimenti n è uno pseudoprimo forte in base b.

Per tutti gli altri test {T}, m∈, la definizione è analoga:

  1. scegliamo a caso un intero b, con 1<b<n, e calcoliamo M.C.D.(b, n);
  2. se M.C.D.(b, n) > 1, allora n non è primo, ed abbiamo finito;
  3. se M.C.D.(b, n) = 1, calcoliamo b (mod n), e procediamo come nel primo test. In questo modo troviamo che n non è primo, oppure che n è pseudoprimo forte in base b.

Considerazioni finali sul test

Si può subito notare che, a differenza dei Test di Fermat e Test di Wilson, qui i calcoli sono minori in numero e molto più semplici, e si può dimostrare che il livello di complessità computazionale è polinomiale, mentre gli altri due presentano una difficoltà computazionale esponenziale. Per quanto riguarda l'affidabilità, anch'essa è molto buona in questo test. Infatti, nonostante sia un test probabilistico, quando effettuiamo il test T, sappiamo che la probabilità che n non sia primo e sia uno pseudoprimo forte in base b è minore di 1/4, e, quindi, la probabilità che n non sia primo ma passi i test T, T, ... , T è minore di , ossia piccolissima rispetto a quella del Test di Fermat.

Assumendo l'Ipotesi di Riemann generalizzata, il test di Miller-Rabin si può facilmente modificare in modo da diventare un vero test di primalità e l'algoritmo ad esso associato avrebbe costo [1].

Note

  1. ^ (EN) Gary Miller, Riemann's Hypothesis and Tests for Primality, in J. Comput. System Sci., vol. 13, n. 3, 1976, pp. 300-317. (PDF)

Voci correlate

Altri progetti

Collegamenti esterni

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

Read other articles:

Adrien Rabiot Rabiot with France in 2018Informasi pribadiNama lengkap Adrien Thibault Marie Rabiot[1]Tanggal lahir 3 April 1995 (umur 28)[2]Tempat lahir Saint-Maurice, FranceTinggi 188 m (616 ft 10 in)[3]Posisi bermain Central midfielderInformasi klubKlub saat ini JuventusNomor 25Karier junior2001–2003 Créteil2003–2004 Alfortville2004–2008 Créteil2008 Manchester City2008–2009 Pau FC2009–2010 Pôle Espoirs2010–2012 Paris Saint-GermainK...

 

 

Keuskupan Agung CzęstochowaArchidioecesis CzestochoviensisArchidiecezja CzęstochowskaBasilika Katedral Keluarga Kudus di CzęstochowaLokasiNegara PolandiaStatistikLuas6.925 km2 (2.674 sq mi)Populasi- Total- Katolik(per 2013)827.990820,721 (99.1%)InformasiRitusRitus LatinPendirian28 Oktober 1925KatedralBazylika Archikatedralna Świętej Rodziny(Basilika Katedral Keluarga Kudus)Kepemimpinan kiniPausFransiskusUskup agungWacław DepoSufraganKeuskupan Rado...

 

 

Silver Bauhinia Star Silver Bauhinia Star (Hanzi tradisional: 銀紫荊星章, SBS) adalah peringkat kedua dalam urutan dari Bauhinia Star di Hong Kong.[1] Gelar ini diberikan kepada perseorangan yang memberikan kontribusi terbaik dalam bidang pelayanan untuk masyarakat dan/atau pekerjaan-pekerjaan bersifat sosial atau nirlaba untuk waktu yang sangat lama. Pemberian penghargaan ini diciptakan sejak tahun 1997 untuk menggantikan sistem penghargaan yang mengacu ke Britania Raya dari Ker...

Soyuz MS-13Soyuz MS-13 mendekati ISS.Jenis misiMisi berawak menuju ISSOperatorRoskosmosCOSPAR ID2019-041ASATCAT no.44437Durasi misi200hr 16jam 44mntFrekuensi orbit3,216 Properti wahanaWahana antariksaSoyuz-MSJenis wahana antariksaSoyuz-MS 11F747ProdusenRKK Energia AwakJumlah awak3AwakAleksandr SkvortsovLuca ParmitanoAwak peluncuranAndrew R. MorganAwak pendaratanChristina KochTanda panggilCliff Awal misiTanggal luncur20 Juli 2019, 16:28:21 UTC [1]Roket peluncurSoyuz-FGTempat peluncuran...

 

 

Role-playing game terminology This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (December 2022) (Learn how and when to remove this template message) This article possibly contains synthesis of materia...

 

 

Constituency of Bangladesh's Jatiya Sangsad Khulna-3Constituencyfor the Jatiya SangsadDistrictKhulna DistrictDivisionKhulna DivisionElectorate226,281 (2018)[1]Current constituencyCreated1973PartyAwami LeagueMember(s)Monnujan Sufian Khulna-3 is a constituency represented in the Jatiya Sangsad (National Parliament) of Bangladesh since 2008 by Monnujan Sufian of the Awami League. Boundaries The constituency encompasses Khulna City Corporation wards 1 through 15, and two union parishads o...

2014 single by Mia Martina featuring Waka Flocka FlameBeastSingle by Mia Martina featuring Waka Flocka Flamefrom the album Mia Martina ReleasedSeptember 16, 2014Recorded2014GenrePop, danceLength3:09Label CP Songwriter(s) Martine Johnson Breyan Isaac Juaquin Malphurs Producer(s)Breyan IsaacMia Martina singles chronology HFH (Heart Fucking Hurts) (2014) Beast (2014) Waka Flocka Flame singles chronology Tell Daddy'(2014) Beast(2015) Game On(2015) Beast is a song recorded by Canadian sing...

 

 

Metropolis Part I is an EP by American electronic music trio The M Machine. It was released on April 24, 2012,[1] and is the first part of a two-part concept album describing the story of a dystopian city known as Metropolis, as described by the digital liner notes available on their website. It was released on Owsla. The songs A King Alone and Faces feature vocals from the band members, while Shadow in the Rose Garden features vocals from Kelly Koval, which themselves are sampled fro...

 

 

Art museum in Raleigh, North Carolina Contemporary Art Museum, Raleigh Contemporary Art Museum of Raleigh (CAM Raleigh) is a multimedia contemporary art gallery in Raleigh, North Carolina. CAM Raleigh has no permanent collection but offers exhibitions of works by artists with regional, national, and international recognition.[1] The museum characterizes itself by the statements We seek the most contemporary art and design. We work to curate it in a way that's always fresh. We create a...

Les MisérablesPoster film Les MisérablesSutradaraTom HooperProduserTim BevanEric FellnerDebra HaywardCameron MackintoshDitulis olehWilliam NicholsonAlain BoublilClaude-Michel SchönbergHerbert KretzmerBerdasarkanLes Misérablesoleh Alain Boublil dan Claude-Michel SchönbergLes Misérablesoleh Victor HugoPemeranHugh JackmanRussell CroweAnne HathawayAmanda SeyfriedEddie RedmaynePenata musikClaude-Michel SchönbergSinematograferDanny CohenPenyuntingMelanie Ann OliverChris DickensPerusaha...

 

 

Artículo principal: Georgia en la Copa Mundial de Rugby Georgia Asociación Georgian Rugby Union Confederación Rugby Europe Participación 6ta Entrenador Levan Maisashvili Capitán Merab Sharikadze Máximo anotador Luka Matkava (13) Más tries Luka Ivanishvili, Beka Gigashvili, Aka Tabutsadze, Tengiz Zamtaradze, Davit Niniashvili, Vano Karkadze, Merab Sharikadze (1) La Selección de rugby de Georgia fue uno de los 20 participantes de la Copa Mundial de Rugby de 2023 que se realizó en ...

 

 

周處除三害The Pig, The Snake and The Pigeon正式版海報基本资料导演黃精甫监制李烈黃江豐動作指導洪昰顥编剧黃精甫主演阮經天袁富華陳以文王淨李李仁謝瓊煖配乐盧律銘林孝親林思妤保卜摄影王金城剪辑黃精甫林雍益制片商一種態度電影股份有限公司片长134分鐘产地 臺灣语言國語粵語台語上映及发行上映日期 2023年10月6日 (2023-10-06)(台灣) 2023年11月2日 (2023-11-02)(香�...

Stock caricature of a Chinese laborer seen in cartoons of the 19th century John Confucius John Chinaman was a stock caricature of a Chinese laborer seen in cartoons of the 19th century.[1] Also referenced by Mark Twain and popular American songs of the period,[2] John Chinaman represented, in western society, a typical persona of China. He was typically depicted with a long queue and wearing an Asian conical hat. History John Chinaman minstrel songs from the 1850s presented Ch...

 

 

VégèceFonctionFonctionnaire (en)BiographieDécès Vers 450Nom dans la langue maternelle Publius Flavius Vegetius RenatusÉpoque Bas-Empire romainActivités Écrivain, historien, médecin, poète, militaire, haut fonctionnaireGens FlaviiŒuvres principales Epitoma rei militarismodifier - modifier le code - modifier Wikidata Végèce (Publius Flavius Vegetius Renatus) est un écrivain romain de la fin du IVe et de la première moitié du Ve siècle de l’ère chrétienne, auteur de troi...

 

 

British toilet tissue brand For the French comedian, see Andrex (actor). AndrexProduct typeToilet paperOwnerKimberly-ClarkCountryUnited KingdomIntroduced1942; 82 years ago (1942)MarketsUnited Kingdom, Hong KongPrevious ownersSt Andrew MillsBowater-ScottRegistered as a trademark inEU[1]Websitewww.andrex.co.uk The Andrex Puppy, seen here in a British advertisement from 1994. Andrex is a British brand of toilet roll. It is owned by the American company Kimberly-Clark.&#...

River in Hunterdon County, New Jersey This article is about the river. For the community, see Spruce Run, New Jersey. Spruce RunSpruce Run near the Spruce Run ReservoirShow map of Hunterdon County, New JerseyShow map of New JerseyShow map of the United StatesLocationCountryUnited StatesStateNew JerseyCountyHunterdonPhysical characteristicsSourceSchooley's Mountain • coordinates40°45′48″N 74°51′23″W / 40.76333°N 74.85639°W / 40.76333; -7...

 

 

Parliamentary constituency in the United Kingdom, 1918–1983 GallowayFormer County constituencyfor the House of Commons1918–1983SeatsOneCreated fromKirkcudbrightshire and WigtownshireReplaced byGalloway and Upper Nithsdale Galloway was a county constituency in the Galloway area of Scotland. It elected one Member of Parliament (MP) to the House of Commons of the Parliament of the United Kingdom, by the first past the post voting system. It was created for the 1918 general election, and abol...

 

 

Review of the event 2012 Libertarian National Convention2012 presidential election Nominees Johnson and GrayConventionDate(s)May 2–6, 2012CityLas Vegas, NevadaVenueRed Rock Resort Spa and CasinoChairRuth Bennett (WA)Keynote speakerMichael CloudNotable speakersTheodora Tonie Nathan Edward Clark Mary RuwartCandidatesPresidential nomineeGary Johnson of New MexicoVice presidential nomineeJim Gray of CaliforniaVotingTotal delegates593Votes needed for nomination297‹ 2010 · 2014&...

一中同表,是台灣处理海峡两岸关系问题的一种主張,認為中华人民共和国與中華民國皆是“整個中國”的一部份,二者因為兩岸現狀,在各自领域有完整的管辖权,互不隶属,同时主張,二者合作便可以搁置对“整个中國”的主权的争议,共同承認雙方皆是中國的一部份,在此基礎上走向終極統一。最早是在2004年由台灣大學政治学教授張亞中所提出,希望兩岸由一中各表�...

 

 

NASA spacecraft for exoplanetology (2009–2018) This article is about the space telescope. For the style of refracting telescope invented by Johannes Kepler, see Keplerian telescope. KeplerArtist's impression of the Kepler telescopeMission typeSpace telescopeOperatorNASA / LASPCOSPAR ID2009-011A SATCAT no.34380Websitewww.nasa.gov/keplerMission durationPlanned: 3.5 years Final: 9 years, 7 months, 23 days Spacecraft propertiesManufacturerBall Aerospace & TechnologiesLaunch mass1,0...