Discussione:Fattorizzazione

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Crystal Clear app ksirtet.pngQuesta voce rientra tra gli argomenti trattati dal progetto tematico sottoindicato.
Puoi consultare le discussioni in corso, aprirne una nuova o segnalarne una avviata qui.
Math.svgMatematica
Monitoraggio fatto.svgLa voce è stata monitorata per definirne lo stato e aiutarne lo sviluppo.
Ha ottenuto una valutazione di livello minimo (gennaio 2011).
CSeri problemi relativi all'accuratezza dei contenuti. Importanti aspetti del tema non sono trattati o solo superficialmente. Altri aspetti non sono direttamente attinenti. Alcune informazioni importanti risultano controverse. Potrebbero essere presenti uno o più avvisi. (che significa?)
CSeri problemi di scrittura. Linguaggio comprensibile, ma con stile poco scorrevole. Strutturazione in paragrafi carente. (che significa?)
DGravi problemi relativi alla verificabilità della voce. Molti aspetti del tema sono completamente privi di fonti attendibili a supporto. Presenza o necessità del template {{F}}. (che significa?)
DGravi problemi relativi alla dotazione di immagini e altri supporti grafici nella voce. Mancano molti file importanti per la comprensione del tema, alcuni essenziali. (che significa?)
Monitoraggio effettuato nel gennaio 2011


Nuvola apps korganizer.svg ...da fare in Fattorizzazione

aggiorna cache · modifica Annota in questo spazio le cose da fare per migliorare la voce o segui i suggerimenti già indicati.

  1. Riorganizzare
  2. migliorare la parte su forza bruta
  3. I miglioramenti alla forza bruta sono ben altri, oltre quello riportato
  4. prendere magari spunto da "Understanding brute force" di Bernstein
  5. inserire implementazione IBM di Shor

Secondo me l'ultimo paragrafo è da modificare pesantemente: da come è scritto sembra dire che ora/oggi/adesso il problema della fattorizzazione è in P... e solo "sotto l'ipotesi della possibilità di costruire computer quantistici" (ipotesi che ben pochi condividono) Lapo Luchini 08:28, Ott 26, 2004 (UTC)

In breve: Se l'ipotesi di Riemann è vera, è possibile fattorizzare in P. I computer quantistici in grado di implementare Shor esistono in prototipo alla IBM, che io sappia a 7 qubit, dal 2001 Articolo. Da prima (1999) esistono versioni a 3 e 5 qubit. Vedi anche in inglese --BW Insultami 10:02, Ago 5, 2005 (CEST)

Secondo me il punto essenziale non è se esistono o meno "piccoli computer quantistici" ma che a tutt'oggi si vedono problemi "insormontabili" che pongono forti limiti alla scala di questi esemplari. Intendo dire: il giorno stesso che è stato inventato il transistor era già possibile prendere dei normali fili di rame e unirne assieme 2, 3, 5, 100 e fare, lì per lì, un circuito elementare di qualunque tipo si volesse (unico problema, avrebbe magari occupato una stanza). Qua invece la cosa mi sembra (non sono un fisico!) diversa, dato non basta avvicinare due "computer da 3 qubit" per ottenerne uno da 6… e perché usare i computer quantistici in sé sia giustificabile bisogna poter fattorizzare numeri di almeno 1024 bit… e questo, oggi come oggi (ripeto, la poca fisica quantistica che ho studiato per il corso di Fisica3 del Poli non mi è in questo caso certo sufficiente: sarei ben felice di essere smentito) scale di questo genere non sono solo "difficili da implementare", più che altro non si ha neanche la più pallida idea di come si potrebbe fare. --Lapo Luchini 16:55, Ago 12, 2005 (CEST)

Concordo col fatto che questa pagina sia una vera ciofega (soprattutto se paragonata alla pagina inglese). Ma e' possibile mai che tra tutti gli informatici italiani non ce ne sia 1 in grado di esporre l'argomento in modo rigoroso e completo ? Mi domando come mai, eppure in Italia di geni informatici ne abbiamo (vedi ad esempio: http://www.datatime.eu/concorsopoli/).

criteri di divisibilità[modifica wikitesto]

il rollback alle modifiche dell'anonimo è semplicemente dovuto al fatto che i criteri di divisibilità non hanno uso nella fattorizzazione (a parte che perché limitarsi all'11? e quale sarebbe il criterio di divisibilità per 7?) -- .mau. ✉ 11:02, 17 apr 2006 (CEST)

C'e` un criterio pratico di divisibilita` per 7 di n. Scusa se non uso le notazioni matematiche, non le ho mai usate qui. Nota che NON e` utile per calcolare n modulo 7, ma solo per verificare se n mod 7 = 0.
Se n ha 1 cifra, allora e` banale ;-)
Se n ha piu` cifre, separo la meno significativa dal resto. Ad esempio, se n = 1234, lo separo in n1 = 123 e n2 = 4. Se e solo se ( n1 - 2 x n2 ) mod 7 = 0 allora anche n mod 7 = 0. Ribadisco che NON e` vero che ( n1 - 2 x n2 ) mod 7 = n mod 7.
Se n1 - 2 x n2 ha piu` di 1 cifra, proseguo ricorsivamente.
Esempio: 1234 e` multiplo di 7? Non so. 123 - 2x4 = 123 - 8 = 115. 115 e` multiplo di 7? Boh... calcolo 11-5x2=1... allora 1234 NON e` multiplo di 7.
Altro esempio: 1239 (che sappiamo essere 177x7). Calcoliamo 123 - 9x2= 123-18=105. 105 e` multiplo di 7? Boh, proviamo: 10 - 5x2 = 10 - 10 = 0; ergo 1239 e` multiplo di 7.
Trovai questo criterio (senza dimostrazione) su un libro molto vecchio. Non e` difficile dimostrarlo.
Ovviamente non serve a molto se devo fattorizzare, una volta che so che un numero e` multiplo di 7 devo comunque dividere per 7 ;-)
--Lou Crazy 04:53, 18 apr 2006 (CEST)
P.S. Ho trovato una cosa matematica che io so e .mau. no! Evviva! Peccato che sia una cosa che non serve quasi a nulla ;-)
Beh, lo conoscevo sotto altra forma (io la chiamo legge 132), ma non è che ne valga la pena. Se è solo per quello, ne so anche uno per il 13 :-) -- .mau. ✉ 07:51, 18 apr 2006 (CEST)
Acci e poi denti... e perche` la chiami legge 132? Sono d'accordo che serve a poco... immagino che quella per il 13 usi un metodo dello stesso genere ma piu` incasinato; vero? --Lou Crazy 20:49, 18 apr 2006 (CEST)
più o meno, è la legge (-1)34. Magari le aggiungo a Criteri di divisibilità... -- .mau. ✉ 21:54, 18 apr 2006 (CEST)
Ma non c'e` ancora una voce Criteri di divisibilità! --Lou Crazy 03:26, 19 apr 2006 (CEST)


e allora la faccio! -- .mau. ✉ 07:47, 19 apr 2006 (CEST)

Il criterio di divisibilita` per 7 che hai indicato su quella pagina e` diverso dal mio, ma ha il vantaggio di dare il modulo... meglio cosi`! --Lou Crazy 04:44, 21 apr 2006 (CEST)
secondo me ci si limita all'11 perché non esistono criteri di divisibilità per numeri maggiori di 11. in mancanza di un criterio specifico per il numero, si ricorre al criterio generale che è la funzione (presunta) generatrice dei numero primi.

divisibilità e fattorizzazione[modifica wikitesto]

purtroppo non solo non è nota tale funzione, ma nemmeno è noto un criterio per validarla/falsificarla diverso da quello empirico, di porre n sempre più grandi e vedere se la funziona ritorna sempre dei numeri primi.le prove si concentrano su "alcune funzioni" candidate.con queste vengono generati i numeri di 100.000 e più cifre con le quali i laboratori fanno a gara a chi trova il più grande numero primo.

se un numero non è divisibile per 2 e per 3, sicuramente non lo è per 6. perciò è inutile provare tutti i criteri di divisibilità. servono solo i criteri dei numeri primi da 1 a 11; ossia 2,3,5,7,11 (nonservono 4,6,9,10). dopodiché si prova a vedere se il numero inziale è divisibile per numerio primi maggiori di questri numerim per i quali non c'è un criterio di divisibilità.sicuramente il numero inziale non è divisibile per multipli di 2,3,5,7,11, non avendo superato i criterri di divisibilità.

per generare i numeri primi uso la funzione generatrice e parto da n=2, incrementando di 1. il numero iniziale se non èdivisibile per 2, non lo è nemmeno per i multipli di 2. ciò non vale però per i numeri primi generati da 2: il numero inziale può non essere divisibile per un numero primo genrato da 2, ma può essere divisibile per un numero primo generato con n= a un multiplo intero di 2.

i test di primalità non fanno fattorizzazione, ma appunto solo primalità: dicono se il numero è primo oppure no, ma in caso non sia primo non dicono nulla sui fattori. I criteri di divisibilità invece aiutano a fattorizzare: se N è divisibile per 11, lo possiamo scrivere come 11*N'. -- .mau. ✉ 11:49, 25 mag 2006 (CEST)
le due cose sono complemetari.provati tutti i numeri minori di quello iniziale se non riesco con la (presunta) generatrice dei numeri primi a tirare fuori un numero uguale a quello inziale, ciò significa che il numero non è primo.

questo serve a capire se la fattorizzazione è corretta; se il test di primalità dice che non è un numero primo, e non ho trovato alcun fattore, vuol dire che è sbagliata la fattorizzazione. se il numero è primo i test di primalità non dicono nulla sui fattori, ma gwenerano fattori "candidati".dopo aver provato i criteri di divisibilità fino a 11,per fattorizzare il numero iniziale è necessario provare tutti i numeri primi da 13 fino al numero dato.per trovare questi numeri primi uso la funzione generatrice:se il numero è maggiore di 11 e minore di quello inziale, lo provo come divisore e vedo se la divisione non ha resto.se sì,il numero primo trovato è un fattore di scomposizione di quello iniziale.