Divisió per tentativa

La divisió per tentativa és l'algoritme de factorización de sancers més senzill i fàcil d'entendre.

Descripció

Donat un sancer compost n (a lo llarc d'este artícul, n serà «el sancer a factorizar»), la divisió per tentativa consistix en intentar dividir n entre tot número primo menor o igual a √n. Si es troba un número que és divisor de n, en divisió sancera, eixe número és un factor de n.

És possible determinar un llímit per als factors primers. Suponga's que $P(i)$ és el i-ésimo primer, de modo que $P(1)=2$, $P(2)=3$, $P(3)=5$ etc. Llavors el valor de l'últim número primo provat com un possible factor de n seria $P(i)$ lloc que $P(i+1{)}^2>n$; si fora igual voldria dir que $P(i+1)$ és un factor. Encara que tot açò està molt be, normalment l'inconvenient d'inspeccionar un n concret per a determinar el valor correcte de i és més costós que simplement provar en l'únic candidat innecessari $P(i+1)$ que estaria inclós en la tentativa en tots els $P(i)$ tals que $P(i)\le \sqrt{n}$. Pot la raïl quadrada de n ser sancera, llavors és un factor i n és un quadrat perfecte, pero no és esta una manera bona de trobar-los.

La divisió per tentativa garantisa trobar un factor de n, ya que comprova tots els factors primers possibles de n. Per tant, si l'algoritme no troba cap factor, és una prova de que n és primer.

Complexitat computacional

En el pijor cas, la divisió per tentativa és un algoritme costós. Si s'escomença en 2 i es va pujant fins a la raïl quadrada de n, l'algoritme requerix

$\pi (2^{n/2})\approx \frac{2^{n/2}}{\left(\frac{n}{2}\right)\ln 2}$

tentatives, a on $\pi (x)$ és la funció contador de cosins, el número de cosins menors que x. En lo anterior no s'ha tingut en conte la sobrecàrrega del test de primalidad per a obtindre els número primo candidats a ser factors. Si s'utilisa una variant sense el test de primalidad, senzillament dividint per tot número impar menor que la raïl quadrada de n, ya siga primer o no, pot aplegar a necessitar-se al voltant de

$\frac{\sqrt{n}}{2}$

tentatives, que per a un n gran és pijor.

Açò significa que per a un n en factors primers grans de tamanys similars (com aquells empleats en la criptografia asimètrica), la divisió per tentativa és computacionalment impracticable.

No obstant, per a un n en a lo manco un factor menut, la divisió per tentativa pot ser un método ràpit per a trobar eixe factor menut. Val la pena percatarse de que per a un n aleatori, existix un 50% de provabilitat de que 2 siga un factor de n, un 33% de provabilitat de que 3 siga un factor, i aixina successivament. Es pot observar que el 88% de tots els sancers positius té un factor menor que 100, i que el 91% té un factor menor que 1000.

Vore també

• Factorización de sancers