Fattorizzazione

di il
10 risposte

Fattorizzazione

Ho voluto aprire questo thread per comunicarvi intanto che proprio ieri sul forum mersenneforum org , nella sezione miscellaneous math , nel thread " Formubla-bla..." dal post num. 95 al 107 , abbiamo scoperto io ovvero Godzilla , e Science_man_88 qualcosa di veramente straordinario sulla fattorizzazione . È una formula molto semplice ovvero dato il prodotto di due numeri primi siamo riusciti a determinare entro due limiti min e max con precisione uno dei due fattori .

Questo per dire che in questo modo si riduce notevolmente il tempo per numeri molto grandi , l'unico problema è che se un numero è di 6 cifre avremo sei limiti min e sei limiti max ovvero 1/10 , 1/100 ,1/1000 , 1/10000, 1/100000 , 1/1000000 , quindi in rapporto alle cifre del prodotto.

Se a qualcuno interessa sappiate che un modo c'è.

10 Risposte

  • Re: Fattorizzazione

    maxilrosso ha scritto:


    Spiega


    magari con un esempio:
    ti do 137171
    Hai aperto il vaso di pandora ... ora chi ci salva ?
  • Re: Fattorizzazione

    137171/0,33 =4156881

    (137171*3)/0,33 = 1247009

    Il fattore più piccolo si trova tra 1-4 , 4-12 , 12-41 , 41-124 , 124-415 , 415-1247 , 1247-4156 ecc.
  • Re: Fattorizzazione

    137171/0,33 =4156881 N1

    (137171*3)/0,33 = 1247009 N2

    In pratica ho preso le cifre di N1 e N2 progressivamente.
  • Re: Fattorizzazione

    @alesia, come si dice? Quando il gioco si fa duro, i duri iniziano a giocare.

    Questo e' il prodotto di 2 primi, non banali ( ma ancora trattabili):

    17356242295880748005164489409

    e questo e' un'altro (con numeri un PO' piu' grossi ;- ) ):

    14501168076704526548692432984366071325619693038447000828398162307010629914645726618683396533753603455336408677294717

    Dammi il range dei due fattori O di uno dei due.

    Il problema dove sta'? Il range serve solo se permette di identificare il fattore.
    Con numeri piccoli, dato il range, si puo' fare una ricerca sequenziale, ma con numeri GRANDI, anche avere il range non serve a nulla, perche' una ricerca sequenziale e' impraticabile.

    Il sistema ha senso SOLO se puo' essere applicato a numeri ARBITRARIAMENTE grandi e permette di identificare un fattore in tempi che sono RAGIONEVOLI (secondi/minuti/ore).

    Ora, se il sistema e' in grado di identificare uno dei fattori (e quindi anche tutti gli altri) in tempi troppo lunghi, e' chiaro che la sua utilita' e' tendente a zero.
  • Re: Fattorizzazione

    migliorabile ha scritto:


    @alesia, come si dice? Quando il gioco si fa duro, i duri iniziano a giocare.

    Questo e' il prodotto di 2 primi, non banali ( ma ancora trattabili):

    17356242295880748005164489409

    e questo e' un'altro (con numeri un PO' piu' grossi ;- ) ):

    14501168076704526548692432984366071325619693038447000828398162307010629914645726618683396533753603455336408677294717

    Dammi il range dei DUE fattori

    Ovviamente io so esattamente quali sono i fattori e so per certo che sono primi
    Basta dividere il numero (prodotto) per 0,33 per avere il N1 mentre per avere N2 bisogna moltiplicare il numero (prodotto) per 3 e poi dividere per 0,33 . Se riesci a darmi N1 e N2 ti do i range , ma comunque dal primo esempio che ho fatto si capisce benissimo.
  • Re: Fattorizzazione

    Basta leggere questo commento nella discussione sul forum citato

    I think you should forget this thread for a while, then go to Nick's theory thread, read all what is written there for a while, try to solve all the exercises, follow with the other chapters yet unpublished, and in a year or two, you may understand why your efforts in this thread (to find a magic factorization formula) are not only futile, but also hilarious.
  • Re: Fattorizzazione

    migliorabile ha scritto:



    Il problema dove sta'? Il range serve solo se permette di identificare il fattore.
    Con numeri piccoli, dato il range, si puo' fare una ricerca sequenziale, ma con numeri GRANDI, anche avere il range non serve a nulla, perche' una ricerca sequenziale e' impraticabile.

    Il sistema ha senso SOLO se puo' essere applicato a numeri ARBITRARIAMENTE grandi e permette di identificare un fattore in tempi che sono RAGIONEVOLI (secondi/minuti/ore).

    Ora, se il sistema e' in grado di identificare uno dei fattori (e quindi anche tutti gli altri) in tempi troppo lunghi, e' chiaro che la sua utilita' e' tendente a zero.
    Beh però invece di provare a caso mi affido ai range che la formula mi rivela. È giusto che tende a 0 ma è sempre0,0001 mai 0.
  • Re: Fattorizzazione

    oregon ha scritto:


    Basta leggere questo commento nella discussione sul forum citato

    I think you should forget this thread for a while, then go to Nick's theory thread, read all what is written there for a while, try to solve all the exercises, follow with the other chapters yet unpublished, and in a year or two, you may understand why your efforts in this thread (to find a magic factorization formula) are not only futile, but also hilarious.
    Tentar non nuoce , è meglio questo
  • Re: Fattorizzazione

    aleasia ha scritto:


    Basta dividere il numero (prodotto) per 0,33 per avere il N1 mentre per avere N2 bisogna moltiplicare il numero (prodotto) per 3 e poi dividere per 0,33 . Se riesci a darmi N1 e N2 ti do i range , ma comunque dal primo esempio che ho fatto si capisce benissimo.
    Non sono io che devo darti i range, se tu che lo devi fare.

    Sia M il numero in questione, prodotto dei primi P1 e P2: M = P1*P2

    Come dici tu, per calcolare N1 DIVIDO M per 0.33, ma facciamo di meglio, lo DIVIDIAMO per 1/3 (siamo nel mondo degli INTERI, ma lo estendiamo, al momento, ai RAZIONALI, operazione RAGIONEVOLMENTE lecita), cioe' lo moltiplichiamo per 3 (nel tuo caso sarebbe stato 33/100, ma perche' non 333/1000, 3333/10000, 3333333333/1000000000, possiamo tranquillamente semplificare a 1/3), quindi

    N1 = M/(1/3) = M*3 = P1*P2*3 -> quindi N1 e' una STIMA SUPERIORE per uno dei due fattori. Ma va!

    Per calcolare N2 MOLTIPLICO M per 3 e poi lo DIVIDO per 1/3, cioe' lo MOLTIPLICO di nuovo per 3

    N2 = M*3/(1/3) = M*3*3 = M*9 = P1*P2*9 -> quindi anche N2 e' una STIMA SUPERIORE per uno dei due fattori. Ma va!

    Ed ora, dato N1 e N2 che non sono altro che M*3 e M*9, che ci faccio?
  • Re: Fattorizzazione

    Nel 1882 Carl Louis Ferdinand von Lindemann ha posto la pietra tombale sul girone infernale dei quadratori di cerchi con riga e compasso, dimostrando la trascendenza del p. Nonostante questo, per decenni (e perfino oggi!) legioni di dilettanti continuano ottusamente a cercare "il metodo" assolutamente impossibile.

    C'è da chiedersi per quanti decenni ancora altre armate Brancaleone di dilettanti continueranno stancamente a baloccarsi con presunti algoritmi di fattorizzazione per i primi giganti che valgono meno di una banconota da tre euro.

    Questo ennesimo thread viene chiuso come tutti gli altri. I motivi per cui la questione è priva di senso matematicamente sono già stati spiegati in abbondanza, con tanto di ottimi riferimenti bibliografici.
Devi accedere o registrarti per scrivere nel forum
10 risposte