OliForum Matematico

Mettere a punto un meccanismo di <br>fattorizzazione rapido ed efficente<br>
<BR>___________________________________
<BR>
<BR>Forma 1:<br><pre>
<BR>Inseriamo il numero N.
<BR>Con un ciclo FoR controlliamo se i numeri che vanno da 2 a maxint(N/2) dividono N.
<BR></pre>
<BR>___________________________________<br>
<BR>
<BR>Un open-source di giorno toglie il medico di torno.<br>
<BR>___________________________________<br>
<BR>
<BR>
<BR>

Perché n/2?
<BR>
<BR>radq(n) non va meglio?
<BR>
<BR>Per k da 2 a int(radq(n))
<BR>e poi si impone n=n/k se n/k è intero
<BR>
<BR>No?

Forma 2:
<BR>
<BR>nseriamo il numero N.
<BR>Con un ciclo FOR controlliamo se i numeri che vanno da 2 a maxint(sqrt(N)) dividono N.
<BR>
<BR>Estremamente inefficiente <IMG SRC="images/forum/icons/icon_frown.gif">

Dipende dai numeri che vuoi fattorizzare! Se sono piccoli e` efficientissimo! Certo puo` essere migliorato eliminando subito il fattore 2 (in base 2, basta togliere gli ultimi zeri se ci sono) e facendo il ciclo solo sui dispari... o cose del genere...
<BR>Forma 3:
<BR><pre>
<BR>Leggi N
<BR>se l\'ultima cifra binaria e` 0 {
<BR> toglila(N:=N/2) e scrivi \"2x\" }
<BR>Poni I:=3; (II:=9)
<BR>finche\' I non supera la radice di N (II<N) {
<BR> finche\' I divide N {
<BR> dividi per I(N:=N/I) e scrivi I\"x\"}
<BR> Inctementa I (I:=I+2, II:=II+4I-4);}
<BR>Se N e` il quadrato di I (II=N){
<BR> scrivi I\"x\"I
<BR>} altrimenti {
<BR> scrivi N }
<BR></pre>
<BR>Cosi\' e` veloce anche con numeri grandi, purche\' abbiano solo fattori piccoli <IMG SRC="images/forum/icons/icon_smile.gif"> come succede molto spesso!
<BR>
<BR>Resta complicato trattare numeri composti di solo due fattori entrambi grandi (non per nulla son fatti cosi\' quelli usati in crittografia)... qualche trucchetto c\'e`, ma per ora non ve li dico <IMG SRC="images/forum/icons/icon_razz.gif"> [addsig]

Il problema in un certo senso è quello di sapere se un numero è primo dentro l\'algoritmo per scomporre in fattori primi, in modo da cercare di dividere solo per numeri primi... un po\' quello che Parerga ha fatto per p=2...Si potrebbe per esempio usare il Piccolo di Fermat:
<BR>a^(p-1)=1 mod p se p primo
<BR>con un po\' di a, per es. 2, 3, 5... in modo da eliminare più \"pseudoprimi\" che si può.(Jacopo) <IMG SRC="images/forum/icons/icon_smile.gif">

Sì, questo topic risale alla notte dei tempi... comunque ecco un metodo che può essere utile.
<BR>Sia N il numero da fattorizzare e sia P² il più piccolo quadrato maggiore di N.
<BR>Consideriamo i numeri (P+1)²-N, (P+2)²-N,...,
<BR>(P+k)²-N. Appena incontreremo un quadrato in questa sequenza avremo che x²-N=y² ovvero N=(x-y)(x+y).
<BR>Esempio: prendiamo il numero 4717. P² vale allora 69²=4761. Abbiamo allora la sequenza
<BR>44, 183, 324 e dunque 4717=71²-18²=53*89
<BR>
<BR>Quando questo metodo è più efficace? E quando minimamente?
<BR>