Per un dato numero n (sappiamo che n = p^a * q^b, per alcuni numeri primi p, q e alcuni numeri interi a, b) e un numero dato φ (n) (http://en.wikipedia.org/wiki/Euler%27s_totient_function) trova p, q, a e b.Fattorizzazione rapida
Il problema è che n e φ (n) hanno circa 200 cifre, quindi l'algoritmo deve essere molto veloce. Sembra essere un problema molto difficile e completamente non so come usare φ (n).
Come avvicinarsi a questo?
Per n = p^a * q^b, il numero totale è φ(n) = (p-1)*p^(a-1) * (q-1)*q^(b-1). Senza perdita di generalità, p < q.
Quindi, se gcd(n,φ(n)) = p^(a-1) * q^(b-1)p non divide q-1 e gcd(n,φ(n)) = p^a * q^(b-1) se p divide q-1.
Nel primo caso, abbiamo n/gcd(n,φ(n)) = p*q e φ(n)/gcd(n,φ(n)) = (p-1)*(q-1) = p*q + 1 - (p+q), quindi hai x = p*q = n/gcd(n,φ(n)) e y = p+q = n/gcd(n,φ(n)) + 1 - φ(n)/gcd(n,φ(n)). Quindi trovare p e q è semplice: y^2 - 4*x = (q-p)^2, quindi q = (y + sqrt(y^2 - 4*x))/2 e p = y-q. Quindi trovare gli esponenti a e b è banale.
Nel secondo caso, n/gcd(n,φ(n)) = q. Quindi puoi facilmente trovare l'esponente b, dividendo per q finché la divisione non lascia un resto, e quindi ottieni p^a. Dividere φ(n) da (q-1)*q^(b-1) ti dà z = (p-1)*p^(a-1). Quindi p^a - z = p^(a-1) e p = p^a/(p^a-z). Trovare l'esponente a è di nuovo banale.
Quindi rimane da decidere quale caso avete. Hai il caso 2 se e solo se n/gcd(n,φ(n)) è un numero primo.
Per questo, è necessario un test di primalità decente. Oppure, si può supporre che si abbia il caso 1 e, se ciò non funziona, concludere che si ha il caso 2.
Provate a calcolare cosa è n/(n - φ (n)).
Follow up:
n/(n - φ (n)) = pq. Continui a dividere n per pq.
Non è corretto. 'φ (6) = 2',' 6 - φ (6) = 4' non divide nemmeno 6. –
Calcolo che 'n/(n - φ (n)) = pq/(q + p-1) '. Immagino non sia così semplice. –
@ BlueRaja-DannyPflughoeft, giusto funziona. È interessante, qualche suggerimento perché funziona, come dedurre questa formula? – xan
+1 come hai fatto semplicemente –
Fondamentalmente, devi conoscere la formula per il totiario, e che vuoi trovare 'p * q' e' p + q'. Da quel momento in poi, mescoli gli ingredienti fino a quando il risultato desiderato non viene fuori. –
Inoltre c'è il caso 3: 'gcd (n, φ (n)) = p^(a-1) * q^b' –