mersenneforum.org improvement of pollard rho ?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-04, 03:48 #1 bhelmes     Mar 2016 52×13 Posts improvement of pollard rho ? A peaceful morning for you, is the following programming code an improvement of the pollard rho algorithm ? I evaluate three functions f(n)=4n²+1, g(n)=2n²-1 and h(n)=2n²+1 multiply the function values and make a gcd, these three functions "cover" at least all primes < n, should mean, you will find any prime < n and therefore you get a result. The same improvement as for the pollard rho could be made (Only one gcd every 1000 multiplication) Code in C++: Code: /*================================================================ 99999989 | 429496652455363033 real 0m56.355s */ #include #include #include #include #include #include typedef __uint64_t uint64; typedef __uint128_t uint128; using namespace std; uint64 gcd (uint64 u, uint64 v) { return (v != 0)?gcd(v, u%v):u; } int main(int argc, char* argv[]) { // uint64 f=uint64(4294967291)*4294966997; uint64 f=uint64(99999989)*4294966997; uint64 a, b, c, d, x, res, m=1; for (uint64 i=1; i<(uint64(1)<<32); i++) { x=i*i; a=4*x+1; b=2*x-1; c=b+2; d=(uint128(a)*b) %f; d*=(uint128(d)*c) %f; res=gcd (d, f); if (res>1) { cout << res << " | " << f; break; } } } Greetings from the factorisation side Bernhard
 2019-10-04, 06:07 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 22×17×139 Posts That's not ok. If gcd(abc%f,f) is not 1, then either gcd(a,f) or gcd(b,f) or gcd(c,f) is not 1. All the multiplication and modular calculus is futile, you are getting much better taking the gcd with each than taking two mulmods and a gcd. Rho makes gcd between a difference and f. Not between a product and f. Think about it! And think why. What you just do it is not Rho, but just blind TF, except you try 3 possible factor candidates at one step. Similar like you want to factor 2993, and you take gcd(3*5*7%2993,2993), then gcd(11*13*17%2993,2993), etc, until you run into something like gcd(31*37*41%2993,2993), or gcd(37*41*43%2993,2993), or gcd(41*43*47%2993,2993) which will factor your number. It would be faster to try all primes to 41, those products (modular or not) bring nothing to the result, with or without them the result is the same. If none of the a, b, c, contain a factor, then a*b*c%f will contain no factor. And vice-versa. The "beauty" of Rho is that even when a and b contain no factors, gcd(a-b, f) may contain factors, and Rho reach the right a and b "reasonably fast". Additionally, this is worse than TF, because a lot of primes will repeat in those quadratic products. Try to use your algorithm to factor a 50-60 digits number that rho can factor in a blink. Edit (minor bug): your code is also wrong in the sense that you may run in the situation when f divides abc, and in that case you do not output a proper factor, but f itself. Last fiddled with by LaurV on 2019-10-04 at 06:37
2019-10-22, 21:58   #3
bhelmes

Mar 2016

52×13 Posts

Quote:
 Originally Posted by LaurV Rho makes gcd between a difference and f. Not between a product and f. Think about it! And think why.

I think i understand now, why the difference is important,
the Äquivalenc classes in which some x, y drops are the key.

Does it make sense to make a similar Rho-algorithm in the complex field ?

Greetings from the algorithm side

Bernhard

I hope that the next Mersenne prime will come soon.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Information & Answers 1 2016-11-30 03:48 siegert81 Factoring 5 2011-06-13 02:58 Random Poster Factoring 4 2010-02-12 03:09 jasong Software 3 2007-11-23 04:06 Kevin Software 1 2002-08-26 07:57

All times are UTC. The time now is 04:10.

Tue May 18 04:10:39 UTC 2021 up 39 days, 22:51, 0 users, load averages: 3.30, 3.83, 3.36