Factoring_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
// Factoring_GMP_int.cpp
// Juhani Kaukoranta 19.8.2019

int main()
{
 	mpz_t n,p,q,pqtulo,r,nolla;
	mpz_init(n);
	mpz_init(p);
	mpz_init(q);
	mpz_init(pqtulo);
	mpz_init(r);
	mpz_init(nolla);
	clock_t t0, t1;       // Time alku,loppu
	cout << "Anna murrettava julkinen RSA-avain n,joka on kahden alkuluvun tulo," << endl;
	cin >> n;
	cout << "Annoit avaimen " << n << endl;
	t0 = clock();        // Timer alku

	mpz_t maks;
	mpz_init(maks);
	mpz_sqrt(maks,n);			// maks = floor(sqrt(n))
	mpz_add_ui(maks,maks,1);	// maks = maks + 1
	mpz_t i;
	mpz_init(i);
	unsigned int found = 0;
	int cmp = 0;
	mpz_set_ui(i,3);
	while(1)
	{
		mpz_mod(r,n,i);			// r jakojäännös,jakaja i
		cmp = mpz_cmp(r,nolla); // cmp = 0 jos jakaja löytynyt
		if (cmp == 0)
		{
			mpz_set(p,i);			//  eka tulontekijä p = i
			mpz_divexact(q,n,i);	// q = n / i
			found = 1;				// tulontekijät p,q löydetty
			break;					// pois while-loopista
		}

		cmp = mpz_cmp(i,maks);
		if (cmp <= 0)
		{
			mpz_add_ui(i,i,2);		// i = i+2 seuraava pariton ehdokas
		}
		else
		{
			found = 0;	// avain n ei ole jaollinen
			break;		// n on alkuluku, poistutaan
		}

	}

	t1 = clock();        // timer loppu
	if (found == 1)
	{
		cout << "tekijät p = " << p << " q = " << q << endl;
		cout << "( Laskenta-aika oli: " << (double)(t1 - t0) / CLOCKS_PER_SEC << " sekuntia )" << endl;
		mpz_mul(pqtulo,p,q);
		cout << "tekijöiden tulo = " << pqtulo << endl;
	} else
	{
		cout << "Annettu avain oli alkuluku - ei voi olla RSA-avain" << endl;
	}

}