20191004, 03:48  #1 
Mar 2016
2^{4}·3·7 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 <iostream> #include <math.h> #include <stdio.h> #include <time.h> #include <string.h> #include <stdlib.h> 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*x1; c=b+2; d=(uint128(a)*b) %f; d*=(uint128(d)*c) %f; res=gcd (d, f); if (res>1) { cout << res << "  " << f; break; } } } Bernhard 
20191004, 06:07  #2 
Romulan Interpreter
Jun 2011
Thailand
2^{3}·1,193 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 viceversa. The "beauty" of Rho is that even when a and b contain no factors, gcd(ab, 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 5060 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 20191004 at 06:37 
20191022, 21:58  #3  
Mar 2016
2^{4}×3×7 Posts 
Quote:
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 Rhoalgorithm in the complex field ? Greetings from the algorithm side Bernhard I hope that the next Mersenne prime will come soon. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Trial Divison Improvement  carpetpool  Information & Answers  1  20161130 03:48 
A new Fermat Factorization improvement?  siegert81  Factoring  5  20110613 02:58 
Possible improvement of quadratic sieve  Random Poster  Factoring  4  20100212 03:09 
snewpgen improvement very much appreciated :)  jasong  Software  3  20071123 04:06 
Possible idea for improvement  Kevin  Software  1  20020826 07:57 