Factoring_PollardRho_GMP_int.cpp

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <gmp.h>
#include <stdlib.h>

using namespace std;

// n julkinen avain, p ja q sen laskettavat tekijät
// n, p ja q ovat arbitrary precision integers (GMP:n mpz_t)
// mahdollistaa yli 64-bittisten kokonaislukujen käytön
// Pollard Rho-algoritmi laskee avaimen n ekatekijän p
// jonka jälkeen jakolasku antaa tokatekijän q
// PollardRho algorithm - Wikipedia style
// Juhani Kaukoranta 21.8.2019

mpz_t p,q,n,pqtulo;


clock_t t0, t1;					// timer alku, loppu

void f(mpz_t x)
{
	mpz_mul(x,x,x);			// x = x**2
	mpz_add_ui(x,x,1);		// x**2 + 1
	mpz_mod(x,x,n);			// x = (x**2 + 1) mod n
}

void PollardRho(mpz_t n)
{
	mpz_t x, y, res ;
	mpz_init(x);
	mpz_init(y);
	mpz_init(res);
	mpz_set_ui(x,2);			// x = 2
	mpz_set_ui(y,2);			// y = 2
	mpz_set_ui(p,1);			// p = 1



	int cmp = 0;
	cmp = mpz_cmp_ui(p,1);		// cmp = 0 jos p = 1
	while(cmp == 0)
	{
		f(x);					// x = f(x)
		f(y);					// y = f(y)
		f(y);					// y = f(f(y))
		mpz_sub(res,x,y);		// res = x - y
		mpz_gcd(p,res,n);		// p = gcd(x-y,n)
		cmp = mpz_cmp_ui(p,1);		// cmp = 0 jos p = 1
	}
	if (p == n) {
		cout << "Ei tekijöitä, avain ilmeisesti alkuluku" << endl;
	} else {
			mpz_divexact(q,n,p);	// q = n // p
	}
}

int main()
{
	mpz_init (p);
	mpz_init (q);
	mpz_init (pqtulo);
	mpz_init (n);

	cout << "Anna julkinen RSA-avain n, joka on kahden alkuluvun tulo: " << endl;
	cin >> n;
	switch (mpz_probab_prime_p(n,25)) {
		case 2:
			cout << "n varmasti alkuluku - Bad and Ugly!" << endl;
			break;
		case 1:
			cout << "n luultavasti alkuluku - Bad and Ugly!" << endl;
			break;
		case 0:
			cout << "n varmasti ei alkuluku - Good!" << endl;
	}
	t0 = clock();		// timer alku
	PollardRho(n);
	t1 = clock();		// timer loppu
	cout << "( Laskenta-aika oli: " << (double)(t1 - t0) / CLOCKS_PER_SEC << " sekuntia )" << endl;
	cout << "Alkulukutekijä p = " << p << endl;
	cout << "Alkulukutekijä q = " << q << endl;
	mpz_mul(pqtulo,p,q);
	cout << "Tekijöiden tulo = " << pqtulo << endl;
	return(0);
}