Barrapunto

Lo que dices es correcto. Sin embargo, que no sepamos en que tiempo t acabará el algoritmo, no es lo mismo que decir que el tiempo de calculo no sea finito.

Si tenemos la certeza de que acabará el calculo en todos los casos, el tiempo de cálculo es finito.

En caso contrario, debería haber algun caso en el que el calculo probabilístico convergiera en el infinito a una probabilidad dada. Sin embargo esto no parece que pueda ocurrir con los algorítmos que se usan (lo siento, no tengo la bibliografía a mano y hace un par de años que estuve tocando este tema). De hecho, una convergencia tal debería indicar que el número no es primo. 8)