quick help, pollards rho

[gijunior]

I wonder if anyone can help me. below is code from my pollards rho attempt (for the integer factoring fans out there). However, im not getting the desired result. I believe its my implementation of the Euclidean algorithm as a method for gcd but im not sure.

I get an answer of -1 when n is 319 and -31 when n is 2759.

If anyone can help itd be greatly appreciated. Cheers

#include <math.h>
#include <stdlib.h>
#include <stdio.h>



int gcd(int a, int b){


if (b == 0){
return a;
}
else{

gcd(b, a % b);
}

}

int pollardsrho(int n){

int d, x, y, c, p, q, fy;
d = 1;
x = 2;
y = 2;
c = 1;

while (d == 1){

x = (((x*x)+c) % n); //f(x) = x^2 + c mod n
fy = (((y*y)+c) % n);
y = (((fy*fy)+c) % n);

d = gcd((x-y), n);


if (d<n)
p = d;

}

printf("p = %d\n", p);
}



int main(void){

int n = 319;

pollardsrho;

}

 

[DaveSinkula]

Only cursory searching led me to this:

http://en.wikipedia.org/wiki/Pollard's_rho_algorithm

(link appears to break at apostrophe)

And at a quick glance I noticed the use of absolute value. Would this produce your expected outcomes?

d = gcd([blue]abs[/blue](x-y), n);

 

[gijunior]

/*
* pollard.c
*
*
* Created by Andrew Roberts on 31/01/2006.
* Copyright 2006 __MyCompanyName__. All rights reserved.
*
*/

#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include "gmp.h"




void pollardsrho(mpz_t n){

mpz_t d, x, y, c, p, q, fy, ans, gcd, abs;
int compValue,compValue2;
mpz_init(d);
mpz_init(fy);
mpz_set_ui(d, 1);/*d=1;*/
mpz_init(x);
mpz_set_ui(x, 2);
mpz_init;
mpz_set_ui(y, 2); /*y = 2;*/
mpz_init(c);
mpz_set_ui(c, 1);/*c = 1;*/
mpz_init(ans);
mpz_init(abs);
mpz_init(gcd);
compValue = mpz_cmp_ui(d, 1);

while (compValue == 0){

/*x = (((x*x)+c) % n); //f(x) = x^2 + c mod n*/
mpz_mul(x,x,x);
mpz_add(x,x,c);
mpz_mod(x,x,n);

/*fy = (((y*y)+c) % n);*/
mpz_mul(fy,y,y);
mpz_add(fy,fy,c);
mpz_mod(fy,fy,n);


/*y = (((fy*fy)+c) % n);*/
mpz_mul(fy,fy,fy);
mpz_add(fy,fy,c);
mpz_mod(y,fy,n);

mpz_sub(ans,x,y);
mpz_abs(abs,ans);
gmp_printf("abs = %Zd\n", abs);
gmp_printf("n = %Zd\n", n);
mpz_gcd(gcd,abs, n);



compValue2 = mpz_cmp(d,n);

if (compValue2!=0){

}
mpz_set(d, gcd);



}

gmp_printf("p = %Zd\n", d);
}



int main(void){

mpz_t n;
mpz_init_set_str(n,"319" , 10);

pollardsrho;

}