Fermat, test di
Fermat, test di in teoria dei numeri, è un test di non primalità, vale a dire una sorta di prova che, dato un numero intero, permette (ma non sempre) di stabilire se esso non è primo. [...] Il test si basa sul piccolo teorema di Fermat, secondo il quale, se p è un numero primo e se a è un qualsiasi numero intero, allora vale la congruenza ap ≡ a(modp). In modo equivalente, se un numero n ...
Leggi Tutto
elemento primo
elemento primo in algebra, generalizzazione del concetto di → numero primo. La generalizzazione a un qualunque dominio di integrità A obbliga a distinguere due concetti, la irriducibilità [...] e la primalità:
• un elemento a di A non nullo e non invertibile è irriducibile se ammette solamente divisori banali, cioè invertibili o a esso associati (→ elementi associati);
• un elemento p di A non nullo e non invertibile è primo se, comunque si ...
Leggi Tutto
numero primo
numero primo numero intero maggiore di 1 che ammette solo divisori banali, cioè 1 e sé stesso. Questa proprietà, che nell’ambito dei numeri interi coincide con quella di primalità, va più [...] in generale sotto il nome di irriducibilità. In modo equivalente si può definire numero primo un numero intero maggiore di 1 che ogniqualvolta divide un prodotto a ⋅ b allora divide almeno uno dei due ...
Leggi Tutto
Mihailescu
Mihăilescu Preda (Bucarest 1955) matematico rumeno. Dopo gli studi di algebra e informatica a Zurigo, ha lavorato all’università di Paderborn in Germania. Ha dato importanti contributi in [...] algebra e teoria dei numeri, interessandosi in particolare di matematica discreta e di test di primalità. I suoi studi in algebra relativi agli anelli ciclotomici (→ ciclotomia) lo hanno condotto a dimostrare nel 2002 la congettura di → Catalan. Dal ...
Leggi Tutto
Fermat, pseudoprimo di
Fermat, pseudoprimo di o numero pseudoprimo, in algebra, se a è un fissato intero positivo, uno pseudoprimo di Fermat in base a è un intero positivo n che verifica la congruenza [...] an ≡ a (mod n). Un numero composto che sia uno pseudoprimo di Fermat in qualsiasi base è detto numero di → Carmichael. Gli pseudoprimi di Fermat nascono in relazione al test di non primalità di Fermat (→ Fermat, test di). ...
Leggi Tutto
Informatica
Giorgio Ausiello
Carlo Batini
Vittorio Frosini
(App. IV, ii, p. 189; V, ii, p. 704)
Mentre negli anni 1937-38 venivano pubblicati l'ultimo volume della Enciclopedia Italiana e l'App. I, [...] ora un algoritmo probabilistico che, dato n, genera a caso m (1〈m〈n) e verifica se esso è un certificato della non primalità di n. Una risposta positiva si verifica solo se n è composto; una risposta negativa si può verificare se n è primo oppure se ...
Leggi Tutto
Carmichael, numero di
Carmichael, numero di in teoria dei numeri, numero intero positivo composto n che, per ogni intero positivo a, soddisfa la relazione an ≡ a (modn) (si legga: an congruo a modulo [...] il test di Fermat, in ogni base a, non ha termine; la loro esistenza impedisce che tale test venga usato per dimostrare la primalità di un numero (→ Fermat, test di). Un numero n è un numero di Carmichael se e solo se è privo di fattori quadratici ...
Leggi Tutto
Mersenne, successione di
Mersenne, successione di espressione con cui si indica la successione di numeri naturali Mn = 2n − 1. I numeri che compaiono all’interno della successione di Mersenne sono detti [...] sono perciò 4, 14, 194, ... Sulla base di tale criterio è possibile costruire un algoritmo che permette di verificare la primalità di un numero di Mersenne con una quantità di calcoli che è compatibile con la potenza attuale dei calcolatori; il più ...
Leggi Tutto
Fermat, piccolo teorema di
Fermat, piccolo teorema di in algebra, stabilisce che, se p è un numero primo, allora per ogni numero intero a vale la congruenza ap ≡ a(modp). In modo equivalente, il teorema [...] di Eulero-Fermat: se a e b sono numeri coprimi, allora aφ(b) ≡ 1 (modb), dove φ(b) è la funzione toziente di Eulero. Il piccolo teorema di Fermat permette di stabilire un importante test di non primalità, detto test di Fermat (→ Fermat, test di). ...
Leggi Tutto
Lucas, successione di
Lucas, successione di successione i cui termini, indicati con Ln (detti numeri di Lucas), sono definiti dall’equazione alle differenze Ln = Ln−1 + Ln−2 a partire dalle condizioni [...] vale la relazione F2n = Fn ⋅ Ln; si ha inoltre L2n = Ln 2 − 2(−1)n, relazione che permette di calcolare rapidamente i numeri di Lucas di indice n = 2k, utili nella verifica della primalità dei numeri di Mersenne (→ Mersenne, successione di). ...
Leggi Tutto
primalita
primalità s. f. [lat. mod. primalitas, der. del lat. primus «primo»; cfr. fr. primauté]. – 1. Nella filosofia di T. Campanella (1568-1639), ciascuno dei principî o proprietà trascendentali dell’essere, e cioè la potenza, la sapienza...