Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

quick help, pollards rho

Status
Not open for further replies.

gijunior

Programmer
Feb 2, 2006
21
GB
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(n);

}
 
/*
* 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(y);
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(n);

}
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top