mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-10-04, 03:48   #1
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52×13 Posts
Default 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*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
bhelmes is offline   Reply With Quote
Old 2019-10-04, 06:07   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×17×139 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2019-10-22, 21:58   #3
bhelmes
 
bhelmes's Avatar
 
Mar 2016

52×13 Posts
Default

Quote:
Originally Posted by LaurV View Post

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.
bhelmes is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trial Divison Improvement carpetpool Information & Answers 1 2016-11-30 03:48
A new Fermat Factorization improvement? siegert81 Factoring 5 2011-06-13 02:58
Possible improvement of quadratic sieve Random Poster Factoring 4 2010-02-12 03:09
snewpgen improvement very much appreciated :) jasong Software 3 2007-11-23 04:06
Possible idea for improvement 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.