La fabbrica dei numeri primi

[hydro]

Io non ho ancora capito se c'è o non c'è


EDIT: Penso di aver capito : in pratica il polinomio di Matijasevic (e quelli simili) sono dei test di primalità, non generano (sempre) numeri primi.

Boh mi sembra tutto abbastanza chiaro: è un polinomio $P(X)$ tale che se $x_0$ è un vettore di interi non negativi, allora $P(x_0)$ è o primo o negativo. Inoltre al variare di $x_0$ tra tutti i vettori di interi non negativi, l'insieme dei $P(x_0)$ contiene quello di tutti i primi. Che c'entra con i test di primalità?

[axpgn]

In quel link viene riportato il polinomio di Jones, Sato, Wada and Wiens, di $25°$ grado in $26$ variabili.
È composto da due fattori: $k+2$ e l'altro .. questo "altro" è composto da $+1$ seguito da una serie di quadrati preceduti dal segno meno ovvero l'unico modo per produrre un risultato non negativo è che siano tutti nulli e quindi che il primo che ne risulta è uguale a $k+2$
In pratica mi serve per testare se $k+2$ è primo

Peraltro, per quel che sapevo, per "polinomio che genera primi" si intende un polinomio che genera SOLO primi (come intendeva esserlo quello famoso di Eulero)

[hydro]

Beh ma ti dice solo che se il polinomio valutato in $[...k...]$ è positivo allora $k$ è primo, non ti dice che se $k$ è primo allora il polinomio valutato in $[..k..]$ è positivo. Quindi non è un di primalità, è qualcosa in meno. "Polinomio che genera primi" è una dicitura estremamente vaga, e comunque (come c'è anche scritto in quel link ed è anche un facile esercizio dimostrare) non esistono polinomi che assumono solo valori primi...

[axpgn]

... non esistono polinomi che assumono solo valori primi...

Appunto, era questo il senso del post di Martino.

[j18eos]

Commenti interessanti,

grazie a tutte\i.