Test di Lucas-Lehmer-Riesel

In matematica, il test di Lucas-Lehmer-Riesel è un test di primalità per i numeri della forma N = k2ⁿ − 1, con 2ⁿ > k. Il test è stato elaborato da Hans Riesel e si basa sul test di primalità di Lucas-Lehmer. È il più veloce algoritmo deterministico noto per verificare la primalità dei numeri della suddetta forma. Similmente, il test di Brillhart-Lehmer-Selfridge è il più veloce per i numeri della forma N = k2ⁿ + 1.

L'algoritmo

L'algoritmo è molto simile al test di Lucas-Lehmer, ma con un punto iniziale variabile dipendente dal valore di k.

Definiamo la successione {u_i}, ponendo:

u_{i}=u_{i-1}^{2}-2,\,

per ogni i > 0.

Allora, per un valore di partenza u₀ scelto opportunamente (si veda la sezione seguente), si ha che N è primo se e solo se esso divide u_n−2.

Trovare il valore di partenza

Se k = 1 e n è primo, allora ci troviamo di fronte ad un numero di Mersenne e possiamo prendere u₀ = 4.
Se $n\equiv 3{\pmod {4}}$ , allora possiamo prendere $u_{0}=3$ .
Se $k=3$ , e $n\equiv 0{\pmod {4}}$ oppure $n\equiv 3{\pmod {4}}$ , allora $u_{0}=5778$ .
Se $k\equiv 1{\pmod {6}}$ oppure $k\equiv 5{\pmod {6}}$ , e N non è divisibile per 3, allora possiamo prendere $u_{0}=(2+{\sqrt {3}})^{k}+(2-{\sqrt {3}})^{k}$ .
Altrimenti, ci troviamo nel caso in cui k è un multiplo di 3, ed è più difficile selezionare il valore giusto di $u_{0}$ .

Software LLR

L'LLR è un programma in grado di effettuare dei test di Lucas-Lehmer-Riesel. Il programma è stato elaborato da Jean Penné. Vincent Penné ha modificato il programma, rendendolo capace di effettuare test via Internet. Il software è utilizzato sia dai ricercatori di numeri primi sia da alcuni progetti sul calcolo distribuito, inclusi Riesel Sieve e PrimeGrid.

Voci correlate

Test di Lucas-Lehmer

Collegamenti esterni

Hans Riesel, Lucasian Criteria for the Primality of N = h·2ⁿ − 1, in Mathematics of Computation, vol. 23, n. 108, American Mathematical Society, 1969, pp. 869–875, DOI:10.2307/2004975.
Download Jean Penné's LLR, su pagesperso-orange.fr.

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

Read other articles:

Bachorza Manor

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

امدقيقة (لودر)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) قرية امدقيقة - قرية - تقسيم إداري البلد اليمن المحافظة محافظة أبين المديرية مديرية لودر ال...

Concours Eurovision de la chanson junior 2018

Concours Eurovision de la chanson junior 2018 #LightUp Dates Finale 25 novembre 2018 Retransmission Lieu Minsk-Arena, Minsk Biélorussie Présentateur(s) Zinaïda Kouprianovitch Evgueni Perline Helena Meraai Superviseur exécutif Jon Ola Sand Télédiffuseur hôte BTRC Ouverture Défilé des finalistes Entracte Wings par Polina BogusevichTous les candidats interprétant Light Up Participants Nombre de participants 20 Débuts Kazakhstan Pays de Galles Retour Azerbaïdjan ...

Amal Clooney

Amal ClooneyClooney pada 2018LahirAmal Alamuddin3 Februari 1978 (umur 46)Beirut, LebanonKebangsaanInggrisLebanon]]Almamater St Hugh's College, Oxford New York University School of Law PekerjaanBarrister-at-lawTahun aktif2000–sekarangSuami/istriGeorge Clooney (m. 2014)Anak2 Amal Clooney (née Alamuddin; Arab: أمل علم الدينcode: ar is deprecated ; lahir 3 Februari 1978)[1] adalah seorang barrister Lebanon-Inggris di Doughty Street C...

Presiden Republik Irlandia

Presiden IrlandiaUachtarán na hÉireanncode: ga is deprecated (Irlandia)Lambang IrlandiaLambang KepresidenanPetahanaMichael D. Higginssejak 11 November 2011GelarPresiden (A Uachtaráin) atau Yang Mulia (A Shoilse)StatusKepala negaraKediamanÁras an UachtaráinKantorDublinDicalonkan olehAnggota Oireachtas atau dewan lokalDitunjuk olehPemungutan suara populer langsungoleh Pemungutan suara instant-runoffMasa jabatanTujuh tahun(dapat diperbarui sekali)PendahuluGubernur Jenderal ...

Argilète

Cet article est une ébauche concernant la Rome antique. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Forum Romain avant César Tabularium Aedes Concordae Basilica Opimia Aedes Saturni Basilica Sempronia Aedes Castrorum Atrium Vestae Regia Basilique Æmilia Lacus Curtius Curia Hostilia Basilica Porcia Comitium Rostres Via Sacra Vicus Tuscus Vicus Iugarius Lacus Iuturnae Tullianum Argiletum Sacellum Cloacinæ ...

Jerada

Cet article est une ébauche concernant une localité marocaine. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Jerada Jrada / ⵊⵔⴰⴷⴰ جْرادة Administration Pays Maroc Région Oriental Province Jerada Démographie Population 43 916 hab. (2004) Géographie Coordonnées 34° 18′ 42″ nord, 2° 09′ 49″ ouest Localisation Géolocalisation sur la carte...

Council on Environmental Quality

U.S. presidential advisory committee on environmental policy Council on Environmental QualityAgency overviewFormed1969Headquarters730 Jackson Place, Washington D.C.Agency executiveBrenda Mallory, ChairParent agencyExecutive Office of the PresidentChild agencyOffice of the Federal Environmental ExecutiveWebsiteCouncil on Environmental Quality Council on Environmental Quality building at 730 Jackson Place in Washington, D.C. The Council on Environmental Quality (CEQ) is a division of the Execut...

世界政區索引

此條目可能包含不适用或被曲解的引用资料，部分内容的准确性无法被证實。 (2023年1月5日)请协助校核其中的错误以改善这篇条目。详情请参见条目的讨论页。各国相关主題列表索引国内生产总值石油储量国防预算武装部队（军事）官方语言人口統計人口密度生育率出生率死亡率自杀率谋杀率失业率储蓄率识字率出口额进口额煤产量发电量监禁率死刑国债 ...

KMGH-TV

ABC affiliate in Denver KMGH-TVDenver, ColoradoUnited StatesChannelsDigital: 7 (VHF)Virtual: 7BrandingDenver 7ProgrammingAffiliations7.1: ABC7.2: Ion Mystery7.3: LaffOwnershipOwnerE. W. Scripps Company(Scripps Broadcasting Holdings LLC)Sister stationsKCDO-TV, KSBS-CD, KOAA-TVHistoryFirst air dateNovember 1, 1953(70 years ago) (1953-11-01)Former call signsKLZ-TV (1953–1972)Former channel number(s)Analog: 7 (VHF, 1953–2009)Digital: 17 (UHF, 1999–2009)Former affiliationsCBS (1953...

إيستون (كاليفورنيا)

لمعانٍ أخرى، طالع إيستون (توضيح). إيستون الإحداثيات 36°39′01″N 119°47′27″W / 36.650277777778°N 119.79083333333°W / 36.650277777778; -119.79083333333 تقسيم إداري البلد الولايات المتحدة[1] التقسيم الأعلى مقاطعة فريسنو خصائص جغرافية المساحة 7.799479 كيلومتر مربع (1 أبريل 20...

Abducted: The Carlina White Story

2012 American film Abducted: The Carlina White StoryWritten byElizabeth HunterDirected byVondie Curtis-HallStarringAunjanue EllisKeke PalmerSherri ShepherdRoger CrossTheme music composerTerence BlanchardCountry of originUnited StatesCanadaOriginal languageEnglishProductionProducersMary MartinCraig PiligianAlan GasnerRunning time90 minutesProduction companyPilgrim Studios[1]Original releaseNetworkLifetimeReleaseOctober 6, 2012 (2012-10-06) Abducted: The Carlina White Sto...

هيئة البرمجيات الترفيهية ذاتية التنظيم

هيئة البرمجيات الترفيهية ذاتية التنظيمالشعارمعلومات عامةالاختصار USK (بالألمانية) البلد ألمانيا التأسيس 1994 النوع عمل تجاري المقر الرئيسي برلين ألمانيا مواقع الويب usk.de… (الإنجليزية)usk.de (الألمانية) المنظومة الاقتصاديةالصناعة تقديرات العاب الحاسوبأهم الشخصياتالمال�...

Ornithocheirus

Ornithocheirus Periode Kapur Awal, 105–100 jtyl PreЄ Є O S D C P T J K Pg N ↓ Holotipe O. simus, CAMSM B54428, dan spesimen CAMSM B54552 (holotipe sinonim juniornya, O. platyrhinus)TaksonomiFilumChordataKelasReptiliaOrdoPterosauriaFamiliOrnithocheiridaeGenusOrnithocheirus Seeley, 1870 Tata namaSinonim takson Pterodactylus simus Owen, 1861 Criorhynchus simus Owen, 1874 Ornithocheirus platyrhinus Seeley, 1870 Spesies †O. simus (Owen, 1861) Ornithocheirus (dari bahasa Yunani Ku...

Lauren Lapkus

American actress and comedian Lauren LapkusLapkus in May 2016BornDorthea Lauren Allegra Lapkus (1985-09-06) September 6, 1985 (age 38)Evanston, Illinois, U.S.EducationEvanston Township High SchoolAlma materDePaul UniversityOccupation(s)Actress, comedianYears active2005–presentSpouses Chris Alvarado (m. 2014; div. 2016) Mike Castle (m. 2018) Children2Websitelaurenlapkus.com Dorthea Lauren Allegr...

2020年夏季奥林匹克运动会阿根廷代表团

2020年夏季奥林匹克运动会阿根廷代表團阿根廷国旗IOC編碼ARGNOC阿根廷奧林匹克委員會網站www.coarg.org.ar（西班牙文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員189參賽項目26个大项旗手開幕式：圣地亚哥·兰赫和塞西莉亞·卡蘭薩（帆船）[1]閉幕式：佩德羅·伊巴拉（曲棍球）[2]獎牌榜排名第...

Marko Dević

Ukrainian footballer Marko DevićМарко Девић Dević in 2014Personal informationFull name Marko Dević[1]Date of birth (1983-10-27) 27 October 1983 (age 40)Place of birth Belgrade, SR Serbia,SFR YugoslaviaHeight 1.85 m (6 ft 1 in)Position(s) Attacking midfielder / ForwardYouth career Zvezdara OFK BeogradSenior career*Years Team Apps (Gls)2001–2002 Zvezdara 14 (2)2002–2003 Železnik 19 (1)2003–2004 Radnički Beograd 16 (1)2004 Voždovac 14 (4)2005–2...

Juan Pacheco

Castilian noble of Portuguese descent For the Mexican long-distance runner, see Juan Pacheco (runner). For the Dominican-American musician, see Johnny Pacheco. Cross of the Order of Santiago. Juan Pacheco, 1st Duke of Escalona (1419 – 1 October 1474), better known as Juan Pacheco, Marquess of Villena, was a Castilian noble of Portuguese descent who rose to power in the last years of the reign of Juan II of Castile and came to dominate the government of Castile during the reign of Juan I...

Arthur Mullard

British actor (1910–1995) Arthur MullardCover of Mullard's 1977 autobiographyBornArthur Ernest Mullord(1910-09-19)19 September 1910Islington, London, EnglandDied11 December 1995(1995-12-11) (aged 85)Islington, London, EnglandOccupation(s)Actor, singerYears active1939–1995Spouse Florence Rose (m. 1939; died 1961)Children3Military careerAllegianceUnited KingdomBranchBritish ArmyRankWarrant officerUnitRoyal ArtilleryWarSecond Worl...

Syens

Syens Vue du village. Armoiries Administration Pays Suisse Canton Vaud District Broye-Vully Localité(s) Bressonnaz Communes limitrophes Moudon, Vulliens, Vucherens, Hermenches, Rossenges Syndic Alexandre George NPA 1510 No OFS 5688 Démographie Gentilé Syensois Populationpermanente 163 hab. (31 décembre 2022) Densité 65 hab./km2 Langue Français Géographie Coordonnées 46° 38′ 46″ nord, 6° 46′ 43″ est Altitude 598 m Superficie ...

/profillengkap.com/index.php/article/Kazakh Naval Forces

Badas, Badas, Kediri

The Choirboys (film)

WVRW

Pasawahan, Banjaranyar, Ciamis

Jiamusi

Howrah

San Baltazar Chichicapam

NASASpaceFlight.com

Template talk:2019 NCAA Men's Basketball Consensus All-Americans

Big Sky (American TV series)

Cardia (Thrace)