Test di primalità

Un test di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo. Non va confuso con un algoritmo di fattorizzazione, che invece ha lo scopo di determinare i fattori primi di un numero: quest'ultima operazione è infatti generalmente più lunga e complessa.

Con la significativa eccezione del metodo delle curve ellittiche (noto come ECPP) e dell'algoritmo AKS, i test di primalità più efficienti oggi utilizzati sono probabilistici, nel senso che danno una risposta certa solo quando rispondono NO (ossia quando dicono che il numero è composto) mentre nel caso di risposta SÌ assicurano soltanto un limite inferiore alla probabilità che il numero sia primo. L'errore dei test può essere però reso piccolo a piacere.

Alcuni test

Il test di primalità basilare, che si basa sulla definizione stessa di numero primo, è il seguente: dato un numero di input n, si verifichi se esiste un intero m compreso tra 2 e n − 1 tale da dividere n. Se n è divisibile per almeno un m allora n è composto, altrimenti è primo. Il limite n-1 può essere abbassato a ${\sqrt {n}}$ , in quanto se tutti i fattori fossero maggiori di questo valore, il loro prodotto sarebbe necessariamente maggiore di n, il che è assurdo. In questo caso particolare, il test di primalità fornisce anche la fattorizzazione del numero.

A partire dal Seicento, sono stati ideati diversi altri algoritmi, tra cui il test di Fermat e il test di Wilson; altri sono stati invece creati per essere usati solamente su particolari classi di numeri: esempi sono il test di Lucas-Lehmer per i numeri di Mersenne, il test di Proth per i numeri nella forma k2ⁿ+1, dove k è dispari e minore di 2ⁿ. Il test di Miller-Rabin è invece probabilistico.

Attualmente il test di uso generale più usato è l'ECPP, basato sulle curve ellittiche.

Complessità computazionale

Il problema di verificare se un numero è primo (detto PRIMES) è di complessità P. Tale risultato è stato raggiunto nel 2002.

In precedenza, era stato provato nel 1977 da Solovay e Strassen che esso era nella classe di complessità co-RP; nel 1992 Adleman e Huang, modificando l'algoritmo di Goldwasser - Kilian, mostrarono che esso era nella classe RP, e di conseguenza nella classe ZPP, intersezione di RP e co-RP.

Nel 2002 Agrawal, Kayal e Saxena fornirono un algoritmo deterministico polinomiale per PRIMES, noto come algoritmo AKS, di complessità $O(log(N)^{12})$ , che si riduce a $O(log(N)^{6})$ se vale la congettura di Sophie Germain.

L'algoritmo è stato migliorato varie volte in passi successivi, e sembra essere stato trovato un algoritmo ibrido di complessità ${\tilde {O}}(log(N)^{4})$ ^[1]. Ciononostante al momento attuale questo algoritmo non comporta significativi vantaggi rispetto ai ben noti metodi probabilistici, né implica alcunché sulla fattorizzazione di un numero (se non nel test di verifica di primalità), e quindi nella crittografia basata sui primi.

Note

^ (EN) Qi Cheng, Primality proving via one round in ECPP and one iteratione in AKS (PDF), su cs.ou.edu. URL consultato l'11.03.2008.

Collegamenti esterni

(EN) Eric W. Weisstein, Primality Test, su MathWorld, Wolfram Research.
Implementazione JAVA dell'algoritmo AKS., su angelusworld.com. URL consultato il 2 gennaio 2011 (archiviato dall'url originale il 7 luglio 2011).

V · D · M

Algebra

Numeri

Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici

Principi fondamentali

Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza

Algebra elementare

Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica

Elementi di Calcolo combinatorio

Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione

Concetti fondamentali di Teoria dei numeri

Primi	Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica
Divisori	Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica

Teoria dei gruppi

Gruppi	Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(F_n) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato
Teoremi	Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti
Sottoinsiemi	Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione
Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo

Teoria degli anelli

Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato

Teoria dei campi

Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius
Estensioni	Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer
Teoria di Galois	Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso

Altre strutture algebriche

Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole

argomenti

Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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

Read other articles:

Kawasan Legasi Beijing

Menghadap ke utara, Kantor Legasi Britania Raya berupa bangunan besar putih khas Eropa di sisi kiri Terusan Kekaisaran, sekitar tahun 1900. Banyak orang Tiongkok tinggal di sekitar Kawasan Legasi Beijing berbaur dengan para diplomat dan pengusaha asing. Peta terperinci Kawasan Legasi Beijing tahun 1912. Kawasan Legasi Beijing (KLB) merupakan daerah legasi (kedutaan kecil) asing di Beijing, Tiongkok antara 1861 sampai 1959. Dalam bahasa Mandarin, kawasan ini disebut Dong Jiaomin Xiang (Hanzi s...

List of NBL1 West champions

NBL1 West awards and honors Championship Champions Individual awards Most Valuable Player Coach of the Year Rookie of the Year (defunct) Grand Final MVP Most Improved Player (defunct) Honours All-NBL1 West First Team All-Defensive Five (defunct) vte The champion teams of the NBL1 West, formerly the State Basketball League (SBL), are determined annually by a grand final weekend hosted by Basketball Western Australia. All grand finals have been played in a one-game championship dec...

Grand Prix sepeda motor Spanyol 2023

Grand Prix Spanyol 2023Detail lombaLomba ke 4 dari 20Grand Prix Sepeda Motor musim 2023Tanggal28–30 April 2023Nama resmiGran Premio MotoGP Guru by Gryfyn de EspañaLokasiCircuito de Jerez-Ángel NietoJerez de la Frontera, Cádiz, SpanyolSirkuitFasilitas balapan permanen4.423 km (2.748 mi)MotoGPPole positionPembalap Aleix Espargaró ApriliaCatatan waktu 1:37.216 Putaran tercepatPembalap Francesco Bagnaia DucatiCatatan waktu 1:37.989 di lap 19 PodiumPertama Francesco Bag...

Vitesse Arnhem

VitesseBerkas:Vitesse logo.svgNama lengkapStichting Betaald Voetbal VitesseJulukanVitas, FC Hollywood aan de Rijn (FC Hollywood dari Rhein)Berdiri14 Mei 1892; 131 tahun lalu (1892-05-14)StadionGelreDomeArnhem(Kapasitas: 25.000)KetuaBert RoetertManajerPeter BoszLigaEredivisie2013–14ke-6, EredivisieSitus webSitus web resmi klub Kostum kandang Kostum tandang Musim ini Stichting Betaald Voetbal Vitesse atau lebih dikenal sebagai Vitesse Arnhem adalah klub sepak bola Belanda yang berba...

Campionato Primavera 3

Campionato Primavera 3Sport Calcio TipoClub FederazioneFIGC Paese Italia OrganizzatoreLega Pro Titoloda definire Aperturasettembre Chiusuraaprile PartecipantiNumero variabile di squadre Formula2 gironi all'italiana (stagione regolare) + eliminazione diretta (play-off promozione) Promozione inCampionato Primavera 2 Retrocessione inCampionato Primavera 4 Sito Internetwww.lega-pro.com StoriaFondazione2020 Numero edizioni3 Detentore Renate Record vittorie Arezzo AlbinoLeffe...

Pudgalavāda

Bagian dari seri tentangBuddhisme Awal Teks Buddhis Teks Buddhis Awal Bhāṇaka Tipiṭaka Nikāya Āgama Teks Buddhis Gandhāra Jataka Avadana Abhidharma Sidang Buddhis Pertama Kedua Ketiga Keempat Buddhisme Awal Buddhisme prasektarian → Aliran Buddhis awal Mahāsāṃghika Ekavyāvahārika Lokottaravāda Gokulika Bahuśrutīya Prajñaptivāda Caitika (Haimavata) Sthavira nikāya (Sthaviravāda) Pudgalavāda Vātsīputrīya Saṃmitīya Sarvāstivāda (Haimavata) (Kāśyapīya) (Mahīśā...

Enrico IV d'Inghilterra

Enrico IV d'InghilterraEnrico IV in un ritratto postumo del 1620, forse basato su un originale oggi perdutoRe d'Inghilterra e Signore d'IrlandaDuca d'Aquitania e GuascognaStemma In carica30 settembre 1399 –20 marzo 1413(13 anni e 171 giorni) PredecessoreRiccardo II SuccessoreEnrico V Nome completoEnrico Bolingbroke Altri titoliDuca di LancasterDuca di HerefordConte di DerbyConte di Northampton NascitaCastello di Bolingbroke, 3 aprile 1367 MorteWestminster, 20 marzo 1413...

Supra-arcade downflows

Sunward-traveling plasma voids observed in the Sun's outer atmosphere This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (November 2015) (Learn how and when to remove this template message) Solar flare observed by TRACE 195 Å on 2002 April 21. SADs can be seen at center frame–note the dark tadpoles descending toward the bright coronal loop arcade.Supra-arcade downflows (S...

Frauds, Myths, and Mysteries

Pseudoarchaeology book Frauds, Myths, and Mysteries 10th edition cover: Petroglyphs in Sego Canyon, Thompson Springs, UtahAuthorKenneth L. FederCountryUnited StatesLanguageEnglishSubjectsScience, Archaeology, Pseudoarchaeology, pseudoscience, skepticism, quackeryPublisherOxford University PressPublication dateDec 23, 2019 (10th Edition)Media typePrint (Paperback)Pages332ISBN9780190096410TextFrauds, Myths, and Mysteries at Internet Archive Frauds, Myths, and Mysteries: Science and Pseudos...

Heilbronn (distrik)

Lambang Peta Data dasar Negara bagian: Baden-Württemberg Regierungsbezirk: Stuttgart Region: Heilbronn-Franken Ibu kota: Heilbronn Wilayah: 1.099,95 km² Penduduk: 329.331 (30 Juni 2005) Kepadatan penduduk: 299 jiwa/km² Pelat nomor kendaraan bermotor: HN Pembagian administratif: 46 Gemeinden Alamat kantor bupati: Lerchenstraße 4074072 Heilbronn Situs web resmi: www.landkreis-heilbronn.de Diarsipkan 2017-05-14 di Wayback Machine. Politik Bupati: Detlef Piepenburg Peta Heilbronn adalah sebu...

Bhutan

Kerajaan Bhutanའབྲུག་རྒྱལ་ཁབ་ Druk Gyalkhap (Dzongkha) Bendera Lambang Lagu kebangsaan: འབྲུག་ཙན་དན་ Druk tsendhen (Himne Kerajaan Naga Petir) Perlihatkan BumiPerlihatkan peta BenderaIbu kota(dan kota terbesar)Thimphu27°28′N 89°38′E / 27.467°N 89.633°E / 27.467; 89.633Bahasa resmi dan bahasa nasionalDzongkhaPemerintahanKesatuan parlementer monarki semi-konstitusional• Druk Gyalpo Jigme Khesar Namg...

ألفريدو ديفينسينزي

ألفريدو ديفينسينزي معلومات شخصية الميلاد 9 يونيو 1907(1907-06-09)بوينس آيرس الطول 1.78 م (5 قدم 10 بوصة) مركز اللعب مهاجم الجنسية الأرجنتين مسيرة الشباب سنوات فريق Estudiantil Porteño المسيرة الاحترافية1 سنوات فريق م. (هـ.) 1925–1927 إستوديانتيل بورتينيو 1928 ريفر بليت 7 (5) 1929–1930 Estudian...

2022 Tanauan local elections

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 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: 2022 Tanauan local elections – news · newspapers · books · scholar · JSTOR (November 2021) (Learn how and w...

David Strathairn

David Russell Strathairn (lahir 26 Januari 1949) merupakan seorang aktor berkebangsaan Amerika Serikat yang memenangkan nominasi Academy Award. Dia dilahirkan di San Francisco. Berkarier di dunia film sejak tahun 1990. David StrathairnDavid Strathairn untuk filmnya, Remember This di Festival Film Montclair Foto Oleh: Frank Schramm, 20 Oktober 2022LahirDavid Russell Strathairn26 Januari 1949 (umur 75)San Francisco, California, Amerika SerikatAlmamaterWilliams CollegePekerjaanAktorTahun...

Ludwig Schlesinger

Ludwig SchlesingerLahir(1864-11-01)1 November 1864TrnavaMeninggal15 Desember 1933(1933-12-15) (umur 69)GiessenNama lainLajos Schlesinger Ludwig Schlesinger (Hungaria: Lajos Schlesinger, Slovak Ľudovít Schlesinger), (1 November 1864 – 15 Desember 1993) adalah seorang matematikawan asal Jerman. Ia dikenal karena risetnya dalam bidang persamaan diferensial linear.[1] Referensi ^ Gottwald, Ilgauds, Schlote Lexikon bedeutender Mathematiker, Bibliographisches In...

Burung hantu

Artikel ini bukan mengenai hantu. Burung hantuRentang fosil: Thanetium – sekarang 60–0 jtyl PreЄ Є O S D C P T J K Pg N kumpulan wajah dari beberapa jenis burung hantu Klasifikasi ilmiah Domain: Eukaryota Kerajaan: Animalia Filum: Chordata Kelas: Aves Ordo: StrigiformesWagler, 1830 Klasifikasi Lihat teks Peta persebaran Sinonim Strigidae sensu Sibley & Ahlquist Burung hantu adalah kelompok burung yang merupakan anggota dari ordo Strigiformes. Burung ini termasuk golongan burung...

List of Archie Comics characters

The following is a list of characters in the Archie Comics universe. Licensed characters like Sonic the Hedgehog and Mega Man are not included in this list. Archie series Main characters Archie Andrews Main article: Archie Andrews The character Archie Andrews, created by John L. Goldwater, Bob Montana and Vic Bloom, first appeared in a humor strip in Pep Comics #22 (December, 1941). Within the context of the strip and the larger series that grew out of it, Archie is a typical teenage boy, at...

Futuro

Para otros usos de este término, véase Futuro (desambiguación).De acuerdo con la representación física del futuro en teoría de la relatividad, para un observador en un instante dado su futuro causal es el conjunto de eventos del espacio-tiempo contenidos en el interior del cono de luz futuro. Según la concepción lineal de tiempo que tienen la mayoría de las civilizaciones humanas, el futuro es la porción de la línea temporal que todavía no ha sucedido. En otras palabras, es una c...

Taekwondo at the 2016 Summer Olympics – Men's 80 kg

Taekwondo competition Men's 80kgat the Games of the XXXI OlympiadVenueCarioca Arena 3Date19 August 2016Competitors16 from 16 nationsMedalists Cheick Sallah Cissé Ivory Coast Lutalo Muhammad Great Britain Oussama Oueslatispace Tunisia Milad Beigi Azerbaijan← 20122020 → Taekwondo at the2016 Summer OlympicsList of practitionersQualificationMenWomen58 kg49 kg68 kg57 kg80 kg67 kg+80 kg+67 kgvte The men's 80 kg taekwondo competition at t...

1301

Calendar year Millennium: 2nd millennium Centuries: 13th century 14th century 15th century Decades: 1280s 1290s 1300s 1310s 1320s Years: 1298 1299 1300 1301 1302 1303 1304 Dante Alighieri (c. 1265–1321) 1301 by topic Leaders Political entities State leaders Religious leaders Birth and death categories Births – Deaths Establishments and disestablishments categories Establishments – Disestablishments Art and literature 1301 in poetry vte 1301 in various calendarsGrego...