package algoritmos;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Vector;

import ialgoritmos.IFatoracao;

public class Pollard implements IFatoracao {
	private int numero;

	public Pollard(int numero) {
		this.numero = numero;
	}

	public String fatora() {
		String retorno = "";
		retorno = retorno + "------------rho POLLARD--------------" + "</br>";
		long semente = System.currentTimeMillis();
		Random random = new Random(semente);
		List<Long> modulos = new ArrayList<Long>();
		int i = 0;
		long x0 = random.nextInt((int) numero - 1);
		long y = x0;
		long k = 2;
		long d = 0;
		long x1 = 0;
		int itera = 0;
		while (true) {
			itera++;
			i = i + 1;
			x1 = ((long) (Math.pow(x0, 2) - 1) % numero);
			d = (int) Metodos.mdc(Math.abs(y - x1), numero);
			x0 = x1;
			if (d != 1 && d != numero) {
				retorno = retorno + d + " é divisor de " + numero + " " + itera
						+ " ITERAÇÕES!" + "</br>";

				break;
			} else if (i == k) {

				y = x1;
				k = 2 * k;
			}
		}
		retorno = retorno + "-------------------------------------" + "</br>";

		return retorno;
	}

}
