Logo
Unionpedia
Comunicazione
Disponibile su Google Play
Nuovo! Scarica Unionpedia sul tuo dispositivo Android™!
Scaricare
l'accesso più veloce di browser!
 

Test di primalità

Indice Test di primalità

Un test di primalità è un algoritmo che, applicato ad un numero intero, ha lo scopo di determinare se esso è primo.

22 relazioni: Algoritmo, Algoritmo AKS, Algoritmo ECPP, Curva ellittica, Divisore, Fattorizzazione, Numero intero, Numero primo, Numero primo di Mersenne, Numero primo di Sophie Germain, P (complessità), RP (complessità), Teorema di Proth, Teoria della complessità computazionale, Test di Fermat, Test di Lucas-Lehmer, Test di Miller-Rabin, Test di Wilson, ZPP (complessità), 1977, 1992, 2002.

Algoritmo

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari in un tempo ragionevole.

Nuovo!!: Test di primalità e Algoritmo · Mostra di più »

Algoritmo AKS

L'algoritmo AKS (dalle iniziali dei tre ideatori, i matematici indiani Manindra Agrawal, Neeraj Kayal e Nitin Saxena) è un test di primalità di complessità polinomiale.

Nuovo!!: Test di primalità e Algoritmo AKS · Mostra di più »

Algoritmo ECPP

L'ECPP (dall'inglese Elliptic Curve Primality Proving) è un test di primalità basato sulle curve ellittiche.

Nuovo!!: Test di primalità e Algoritmo ECPP · Mostra di più »

Curva ellittica

In matematica, una curva ellittica è una curva algebrica proiettiva liscia di genere 1 definita su un campo K, sulla quale viene specificato un punto O. Inoltre, ogni curva ellittica possiede una legge di composizione interna (generalmente indicata con il simbolo +) rispetto alla quale essa è un gruppo abeliano con elemento neutro O; di conseguenza, le curve ellittiche sono varietà abeliane di dimensione 1.

Nuovo!!: Test di primalità e Curva ellittica · Mostra di più »

Divisore

Nella matematica, un intero b è un divisore di un intero a se esiste un intero c tale che a.

Nuovo!!: Test di primalità e Divisore · Mostra di più »

Fattorizzazione

In matematica la fattorizzazione è la riduzione in fattori: fattorizzare un numero intero positivo n significa trovare un insieme di numeri interi positivi \ tali che il loro prodotto sia il numero originario (n.

Nuovo!!: Test di primalità e Fattorizzazione · Mostra di più »

Numero intero

I numeri interi (o numeri interi relativi o, semplicemente, numeri relativi) sono formati dall'unione dei numeri naturali (0, 1, 2,...) e dei numeri interi negativi (−1, −2, −3,...), costruiti ponendo un segno “−” davanti ai naturali.

Nuovo!!: Test di primalità e Numero intero · Mostra di più »

Numero primo

In matematica, un numero primo (in breve anche primo) è un numero intero positivo che abbia esattamente due divisori distinti.

Nuovo!!: Test di primalità e Numero primo · Mostra di più »

Numero primo di Mersenne

In matematica un numero primo di Mersenne è un numero primo esprimibile come: M_p.

Nuovo!!: Test di primalità e Numero primo di Mersenne · Mostra di più »

Numero primo di Sophie Germain

Un numero primo di Sophie Germain è un numero primo p tale che 2p+1 è anch'esso un numero primo.

Nuovo!!: Test di primalità e Numero primo di Sophie Germain · Mostra di più »

P (complessità)

Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.

Nuovo!!: Test di primalità e P (complessità) · Mostra di più »

RP (complessità)

Nella teoria della complessità computazionale, RP (Randomized Polynomial time, "tempo polinomiale randomizzato") è la classe di complessità dei problemi decisionali eseguiti su una macchina di Turing probabilistica.

Nuovo!!: Test di primalità e RP (complessità) · Mostra di più »

Teorema di Proth

In teoria dei numeri, il teorema di Proth è un test di primalità per i numeri di Proth.

Nuovo!!: Test di primalità e Teorema di Proth · Mostra di più »

Teoria della complessità computazionale

In informatica, la teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema.

Nuovo!!: Test di primalità e Teoria della complessità computazionale · Mostra di più »

Test di Fermat

Il test di Fermat è un test di primalità basato sul piccolo teorema di Fermat.

Nuovo!!: Test di primalità e Test di Fermat · Mostra di più »

Test di Lucas-Lehmer

Il test di Lucas-Lehmer è una verifica della primalità dei primi di Mersenne.

Nuovo!!: Test di primalità e Test di Lucas-Lehmer · Mostra di più »

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.

Nuovo!!: Test di primalità e Test di Miller-Rabin · Mostra di più »

Test di Wilson

Il test di Wilson per la primalità di un numero intero positivo n deriva direttamente dal teorema di Wilson.

Nuovo!!: Test di primalità e Test di Wilson · Mostra di più »

ZPP (complessità)

Nella teoria della complessità computazionale, ZPP (Zero-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore zero") è la classe di complessità dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà.

Nuovo!!: Test di primalità e ZPP (complessità) · Mostra di più »

1977

Nessuna descrizione.

Nuovo!!: Test di primalità e 1977 · Mostra di più »

1992

Nessuna descrizione.

Nuovo!!: Test di primalità e 1992 · Mostra di più »

2002

È stato proclamato l'Anno internazionale delle montagne.

Nuovo!!: Test di primalità e 2002 · Mostra di più »

UscenteArrivo
Ehi! Siamo su Facebook ora! »