Ottimizzazione-factoring $ \ le_p $ decisione-factoring

Question

Ottimizzazione factoring:
Ingresso: $ N \ in \ mathbb {N} $
Uscita: Tutti i fattori primi di $ N $

Decisione factoring:
Ingresso: $ N, k \ in \ mathbb {N} $
Uscita: La vera se e solo se $ N $ ha un fattore primo di al massimo $ k $

Come posso risolvere il problema di ottimizzazione in tempo polinomiale se il problema decisionale è polinomialmente risolvibile?

Answer 1

È necessario per ottenere un polinomio algoritmo in $ n $ dove $ n = \ log N $ è la dimensione del vostro ingresso, vale a dire la rappresentazione binaria di $ N $ (algoritmi ingenuo fattorizzazione sono $ O (N ^ 2) $ che è ovviamente esponenziale).

Dato dec(k, x) risolvere il problema decisionale factoring, scriviamo una procedura per trovare il più piccolo divisore primo di $ x $ usando una dicotomia per mantenere logaritmica il numero di passi.

sp(x):
  min = 2
  max = x - 1
  while (max >= 1 + min):
    k = floor ((min + max) / 2)
    if dec(k, x):
      max = k
    else:
      min = k + 1
  if x % (min + 1) == 0:
    return (min + 1)
  else if x % min == 0:
    return min
  else:
    return 1

La procedura sopra chiamate dec $ O (\ log x) $ volte e trovare il più piccolo numero primo che divide $ x $, o 1 se non esiste. Ora possiamo tranquillamente definire la seguente funzione di factoring:

factor(x):
  p = sp(x)
  if (p == 1):
    print x
  else:
    print p
    factor(x / p)

Factor è chiamato meno di $ \ log x $ volte (dal momento che $ p = 2 $) in modo che il numero di chiamate al dec è delimitata da $ \ log ^ 2 x $ volte su valori inferiori a $ x $. Se la complessità della dec è polinomiale, diciamo delimitate da una crescente $ P (n) $, quindi la complessità della factor è ancora polinomiale, delimitata da $ n ^ 2P (n) $.

Answer 2

È possibile utilizzare la versione scelta per la ricerca di fattori di $ N $ manipolando $ k $. Dato l'ingresso alla versione ottimizzazione, si può chiedere se ha un fattore primo minore o uguale a $ 2 $, $ 3 $, ..., $ \ sim \ sqrt {N} $. Diciamo che si ottiene il prima risposta a $ k_ {1} $, allora perché non ha detto di sì prima, $ k_ {1} $ deve essere un fattore di $ N $, in modo che possiamo notare che questo verso il basso, e ricominciare dal $ \ frac {N} {k_ {1}} $.

Idealmente ci piacerebbe testare solo i numeri primi fino a $ \ sim \ sqrt {N} $, ma non importa se ci prova i compositi così, come noi colpiremo i loro fattori primi prima, così abbiamo' ll mai ottenere una risposta sì per un composito.

Poi, per ogni singola ricerca Siamo solving al massimo $ \ sqrt {N} $ problemi di decisione, e ad ogni passo (fino a quando abbiamo finito) stiamo riducendo $ N $ a meno di $ \ frac {N } {2} $, quindi se siamo in grado di risolvere il problema della decisione in PTIME (dire $ O (n ^ {c}) $ per qualche costante $ C $), siamo in grado di fare il tutto in qualcosa di più o meno come $ O (n ^ {c + 1/2} \ log n) $.