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.
Nuvola apps edu mathematics-p.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
Fattorizzazione
Argomento di scuola secondaria di I grado
Materiamatematica
Dettagli
Dimensione della voce40 864 byte
Progetto Wikipedia e scuola italiana

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.

Metodo forza bruta migliorato[modifica wikitesto]

Nel metodo forza bruta migliorato leverei il riferimento alla radice. Riformulerei facendo riferimento al fatto che tutti i fattori di un numero si trovano eseguendo le divisioni fino a che il dividendo si mantiene minore del quoziente. Nei fatti è la stessa cosa ma così non si richiama un concetto matematico non necessario.--Mattruffoni (msg) 18:16, 24 mag 2020 (CEST)

Non saprei, in questo modo hai una stima esplicita su quanto devi provare. Nell'altro modo non ce l'hai (anche se nei fatti ovviamente la puoi ricavare ed è quella). Magari si può scrivere separando le due cose, cioè il check lo fai sul quoziente, ma poi si scrive che in pratica al più fai radice di n prove.--Mat4free (msg) 13:11, 28 mag 2020 (CEST)

Rimpiazzare la pagina con la versione inglese[modifica wikitesto]

Se lo condividete, rimpiazzzo la pagina con la versione inglese tradotta. Tra l'altro la pagina contiene un falso: non è vero che ogni numero intero è fattorizzabile in infiniti modi. Inolte L'inclusione di un listato di programma informatico (che tra l'altro non dice che linguaggio usa) mi sembra esuli da un'impronta enciclopedica.--ilorac (msg) 14:37, 20 feb 2021 (CET)

@Adriano.caroli. Se traduci la voce in inglese fai sicuramente un'ottima cosa, visto che è molto migliore della nostra. Concordo con te su quel codice (alle volte per le pagine su algoritmi può essere però utile inserirli in pseudocodice). Sulla fattorizzazione invece non direi che è un falso: 6=3*1*2 è una fattorizzazione, semplicemente non è una fattorizzazione in fattori primi.
Ah, se vuoi riscrivere la voce con calma se vuoi puoi usare la tua pagina delle prove.--Sandro_bt (scrivimi) 17:41, 20 feb 2021 (CET)
Un attimo. Per tradurre dall'inglese l'inglese bisogna saperlo, non basta il tool di traduzione Sto (compatibilmente col mio tempo a disposizione) eliminando cose senza senso da Matematica pura. -- .mau. ✉ 18:10, 20 feb 2021 (CET)
La definizione di fattorizzazione in matematica esclude l'1 banale. Ho appena tradotto "Matematica pura" a mano, non conosco Sto.--ilorac (msg) 21:34, 20 feb 2021 (CET)
Questo chi lo dice? A me risulta il contrario. Quanto allo "Sto" direi che manca un punto appena prima e che sia semplicemente il presente del verbo "stare". --Sandro_bt (scrivimi) 22:34, 20 feb 2021 (CET)
Concordo con Sandro_bt su traduzione e fattorizzazioni con 1.--Mat4free (msg) 10:35, 21 feb 2021 (CET)

Mi sono reso conto che la traduzione delle versioni inglesi di "Matematica pura" e "Fattorizzazione", che ho fatto, c'è troppa verbosità e ripetizione. Così come la traduzione che stavo iniziando di "Primitive part-content" e che poi ho smesso. Penso che le voci di matematica richiedano più concisione oltre al fatto di dare un impronta enciclopedica e non di un trattato.

Se siete d'accordo proverei a modificarle in tal senso.--21:38, 6 mar 2021 (CET)

Non saprei, detta così è un po' troppo vaga per dare un assenso. Essere concisi si scontra con essere chiari a volte e a volte invece aiuta, dipende come si organizza il tutto. Poi personalmente non capisco bene che intendi quando parli di differenza tra una "enciclopedia" e un "trattato". Forse potresti modificare alcune sezioni nella tua pagina di prova linkandola qui così da far capire meglio che tipo di modifiche vorresti fare prima di modificare effettivamente la pagina in modo sostanziale.--Mat4free (msg) 00:02, 7 mar 2021 (CET)

Non so come mantenere la pagina di prove, ogni volta la perdo.--08:15, 7 mar 2021 (CET)

Immagino tu sia Adriano.caroli sloggato, in tal caso la tua è: Utente:Adriano.caroli/Sandbox (ma loggati prima di fare modifiche là se no sembra che stai modificando le pagine di un altro).--Sandro_bt (scrivimi) 08:44, 7 mar 2021 (CET) P.S. Vedi anche aiuto:firma, in particole servono quattro "~" non tre (o in alternativa puoi schiacciare il pulsante apposito).

pulsante apposito, qual'è ? Ho provato ad inserire una voce in mie Prove, ma al successivo logon non le ritrovo. Occorre anche li agire sul pulsante Pubblica ?

Sotto la finestra delle modifiche e sotto gli avvisi che dicono di non copiare e simili, c'è una lista di pulsanti di codici e simboli tra cui quello della firma. Ma se non lo trovi puoi semplicemente scriverlo da tastiera. Comunque la firma la devi mettere a fine messaggio non nell'intestazione della modifica.
Per la pagina di prova non saprei dirti perché non la ritrovi. Devi salvarla e pubblicare le modifiche ovviamente. Ma fatto questo là rimane come tutte le altre pagine. Ho creato la pagina di prova sotto la tua utenza, prova a modificare quella che ho creato al link dato da Sandrobt: Utente:Adriano.caroli/Sandbox.--Mat4free (msg) 10:30, 7 mar 2021 (CET)


Pemsavo ad un tasto fisico per la firma. Ho visto che per salvare il sandbox occorre Pubblicarlo. Ho inserito nella sandbox la voce "Fattorizzazione" in cui tra linee orizzontali ci sono 2 testi ripetuti. --ilorac (msg) 14:31, 7 mar 2021 (CET)
Se non metti il link della pagina di prova qui, diventa complicato riuscire a trovarla :) --Mat4free (msg) 15:28, 7 mar 2021 (CET)

Non si possono usare i link precedenti? Comunque ecco Utente:Adriano.caroli/Sandbox copiata da un precedente link.--ilorac (msg) 21:19, 7 mar 2021 (CET)

Si possono usare, ma pensavo fosse un altro perché io qui non vedo niente a parte quello che ho scritto io.--Mat4free (msg) 21:33, 7 mar 2021 (CET)
Ok, ora vedo la pagina giusta, ma non ho capito che modifiche ci sono, mi sembra solo che hai aggiunto delle linee orizzontali,ma non mi sembra ci siano parti modificate.--Mat4free (msg) 00:37, 8 mar 2021 (CET)
Non ho ancora fatto modifiche. Nel mio mess del 7 avevo scritto che ho evidenziato tra righe orizzontali 2 esempi di ripetizioni ridondanti a dimostrazione della troppa verbosità che ho notato nelle versioni inglesi. --ilorac (msg) 11:44, 8 mar 2021 (CET)
Ok, ho capito, avevo inteso male. Concordo che sono ripetizioni, ma sono in sezioni diverse. Uno potrebbe leggere l'intro e poi la sezione dei polinomi ad esempio, oppure solo la sezione dei numeri interi senza leggere l'intro. Se si togliessero andrebbero tolti dall'intro probabilmente, ma con questa filosofia nell'intro non metti niente. Ci sta che nell'intro di una voce si dicano cose poi ripetute e spiegate in modo più ampio e dettagliato magari nella sezione specifica. Penso sia un buon modo di scrivere una enciclopedia e credo sia anche nelle linee guida di wikipedia: partire con una introduzione generale e poi andare nei dettagli nelle sezioni specifiche approfondendo. Ma per farlo delle ripetizioni sono necessaire. Non lo vedo come un problema, anzi secondo me è bene che un po' di ripetizione ci sia, rende più accessibile le voci secondo me.--Mat4free (msg) 13:25, 8 mar 2021 (CET)
Va bene, lasciamolo cosi. Grazie --ilorac (msg) 14:01, 8 mar 2021 (CET)