[C] Implementare l'algoritmo di fattorizzazione rho di Pollard

Sto usando l'algoritmo pollard's rho:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
long long int mcd(long long int r,long long int s){
	if(r%s==0){
		return s;
	}
	else{
		mcd(s,r%s);
	}
}
long long int pot(long long int b, unsigned long long int e,long long int mod)
{
    long long int ris = 1;     
    b=b%mod;
    while(e> 0)
    {
        if (e & 1){
        	ris = (ris*b)%mod;
        }
        e=e>>1;
        b=(b*b)%mod;  
    }
    return ris;
}
int rabin(long long int num,int it){
	long long int d=num-1,x,a;
	int r,i=0,flag=0;
	if(!(num & 1)){
		return 0;
	}
	while(!(d & 1)){
		r++;
		d=d>>1;
	}
	srand((unsigned)time(NULL));
	while(it!=0){
		a=rand()%(num-2)+2;
		x=pot(a,d,num);
		if(!(x==1 || x==num-1)){
			flag=0;
			for(i=0;i<r-1 && flag==0;i++){
				x=(x%num)*(x%num)%num;
				if(x==1){
					return 0;
				}
				if(x==num-1){
					flag++;
				}
			}
			if(flag!=1){
				return 0;
			}
		}
		it--;
	}
	return 1;
}
long long int prho(long long int m){
	long long int p,q,f;
	int c;
	srand((unsigned)time(NULL));
	if(!(m & 1)){
		return 2;
	}
	do{
		p=rand()%(m-4)+2;
		c=rand()%(m-2)+1;
		q=((p%m)*(p%m)+c)%m;
		f=mcd(abs(p-q),m);
		while(f==1){
			p=((p%m)*(p%m)+c)%m;
			q=((q%m)*(q%m)+c)%m;
			q=((q%m)*(q%m)+c)%m;
		    f=mcd(abs(p-q),m);
		    printf("\n%lld,%lld,%lld",p,q,f);
		}
		if(!(f==m)){
			return f;
		}
	}while(1);
} 
int main()
{
    long long int n,fatt;
    int k=5;
    do{
    	printf("Numero:");
    	scanf("%lld",&n);
    }while(n<=3);
    if(rabin(n,k)){
    	printf("Il numero e\' primo");
    }
    else{
    	printf("\n%lld",prho(n));
    }
    printf ("\n\n");
    return 0;
}

All'inizio il programma testa se il numero e primo(rabin()),se non lo è procede con la fattorizzazione(prho()).Il programma spesso riesce a trovare il fattore,ma in alcuni casi entra in un ciclo infinito con p e q che si ripetono ciclicamente. Come posso evitare ciò?