"Better than pseudo-random" iterator for Pollard's Rho?

mickfrancis · 2014-12-11, 13:23

I wonder if anyone could answer a question I have regarding iterator functions used in Pollard's Rho algorithm:

As I understand it, the aim is to use a function that is as psuedo-random as possible; this is assumed in the complexity analyses that have been carried out. It should also be computationally cheap for obvious reasons.

However, there are functions that we could consider that have shorter cycle (and tail) lengths than a perfectly (psuedo-)random one. An absurd example is the function that generates numbers spaced at a multiple of a factor (p) of N:

Code:

    p = getSmallestFactor(N);
    function f(x) = (x + p) % N;

This would loop (mod p) immediately and Pollard's Rho would find the factor. This would, of course completely defeat the object, as we are factorizing in order to find a factor.

My question is this: Are there 'better than psuedo-random' iterators that could be used, whose cycle-shortening benefits out-weigh their additional cost?

I have been playing with a class of function (that doesn't know about factors of N) that does produce shorter cycles. Unfortunately, the cost outweighs the benefits:

Suppose we have an array of distinct non-zero values C[0], C[1], ... and corresponding functions f(0), f(1), ... where f(i) is the 'standard' iterator using C[i] as the constant:

Code:

    function f(i)(x) = (x^2 + C[i]) % N;

If o represents function composition and we define function F(m) by:

Code:

    function F(m) = (m == 0) ? f(0) : f(m) o F(m-1);

then

Code:

    F(0) is the 'standard' iterator using C[0] as constant:
        x -> (x^2 + C[0]) % N

    F(1) is the function that iterates twice (with different C values):
        x -> ((x^2 + C[0])^2 + C[1]) % N
           = (x^4 + 2C[0]x^2 + C[0]^2 + C[1]) % N

    F(m)(x) generates a monic polynomial in x of degree 2^(m+1), with coefficients of x^i being non-zero iff i is even.

In tests, with N = 18868629790280349989518009992987136785227164415079137 (C53) with factor 7777774777777 (P13), I get the cycle lengths and times shown below. This is a Java implementation, so not that fast. The right-most set of values used x^1024 rather than x^2.

Code:

+------------+---------------------++---------------------++---------------------------++---------------------------+
|            | C[i] = i + 1        || C[i] = RANDOM()     || C[i] = 16384 + 16777216 i || C[i] = 16384 + 16777216 i |   
|            |                     ||                     ||                           ||    exp=1024               |
|            +-----------+---------++-----------+---------++-----------+---------------++-----------+---------------+   
|      m     | cycle len | time (s)|| cycle len | time (s)|| cycle len | time (s)      || cycle len | time (s)      |   
+------------+-----------+---------++-----------+---------++-----------+---------------++-----------+---------------+   
|          0 | 2537770   |    4    ||  1742273  |    9    ||    9408   |     5         ||  6073387  |     10        |
|          1 | 1149581   |    4    ||   559885  |   25    ||  784504   |     5         ||  2370108  |      8        |
|          2 |   85333   |   10    ||   168663  |    1    || 1217979   |     7         ||  1852565  |      7        |
|          3 | 1254046   |    7    ||  2800001  |   26    ||  573250   |     4         ||   411681  |      2        |
|          4 |  437527   |   10    ||   135296  |    7    ||  203384   |    10         ||  1012270  |     11        |
|          5 | 1218369   |   10    ||   682778  |    9    || 3235934   |    28         ||   226494  |      5        |
|          6 | 1026505   |    7    ||   437593  |   21    ||  365988   |     8         ||   195009  |     12        |
|          7 |  750226   |    8    ||   451631  |   13    ||  229190   |     2         ||   503277  |      4        |
|          8 |  418334   |    5    ||   294776  |   26    || 1294949   |    18         ||  1409182  |     17        |
|          9 |  349321   |   35    ||   375245  |    7    ||   52603   |     9         ||   861531  |     10        |
|         10 |  567977   |    9    ||  1936414  |   37    ||   26064   |    10         ||   391137  |      5        |
|         11 |  156450   |    3    ||  1551018  |   37    || 1326637   |    24         ||  1158178  |     20        |
|         12 |   24626   |   10    ||   187018  |    5    ||  165718   |    13         ||   297729  |      5        |
|         13 |  121306   |   12    ||  1002300  |   25    ||  683933   |    14         ||   251780  |     13        |
|         14 |  442266   |    7    ||   181412  |   20    ||   85678   |    14         ||   521311  |      8        |
|         15 |  156963   |   13    ||   183218  |   12    ||     946   |    29         ||    93879  |      3        |
|         16 |  249666   |   16    ||   662852  |   25    ||  692360   |    17         ||  1103360  |     29        |
|         20 |  126940   |    5    ||    43376  |    7    || 1379429   |    43         ||   114094  |      9        |
|         24 |  314699   |   11    ||  1007216  |   44    ||  282941   |    11         ||   278688  |     10        |
|         28 |  537623   |   24    ||   347046  |   21    ||    7142   |     7         ||   150583  |      6        |
|         32 |   62009   |    4    ||   423423  |   26    ||   93590   |    31         ||   666143  |     29        |
|         48 |  223585   |   25    ||   235338  |   72    ||   28398   |    23         ||   529759  |     40        |
|         64 |   11518   |    1    ||    41043  |   44    ||   28635   |     8         ||   163760  |     14        |
|         96 |   16999   |    2    ||   272321  |   63    ||  427018   |    53         ||    81186  |     10        |
|        128 |  258409   |   34    ||   137880  |  170    ||  310206   |    63         ||   561129  |    107        |
|        196 |  317769   |   84    ||   130109  |   85    ||   66443   |    46         ||    63363  |     46        |
|        256 |   77296   |   27    ||    68387  |   84    ||   37436   |    62         ||    62412  |    111        |
|        512 |   57461   |  115    ||   139949  |  169    ||  104195   |    71         ||    98073  |    121        |
|       1024 |  213690   |  250    ||    33953  |  168    ||   24878   |   247         ||      831  |     52        |
|       2048 |   33468   |  215    ||    10758  |  183    ||   78044   |   261         ||     4163  |     13        |
|       8192 |   42665   |  456    ||    31186  |  435    ||   23467   |   274         ||    46184  |    463        |
|      16384 |    6590   |  877    ||    30331  |  862    ||    5191   |   528         ||     1481  |    107        |
|      65536 |    6861   | 1020    ||     2597  |  371    ||    1293   |   517         ||     4511  |    438        |
|     132772 |    5542   |  929    ||     3656  |  868    ||    6285   |  1166         ||     4351  |    876        |
|     524288 |     327   |  234    ||     2439  | 2870    ||    3967   |  2575         ||       31  |    445        |
|    1048576 |     537   | 1740    ||        6  | 5535    ||    2699   |  4414         ||     1708  |   4057        |
|    2097152 |    1344   | 4125    ||      935  | 3611    ||     361   |  2343         ||     1518  |   3862        |
|    4194304 |     330   | 3793    ||       10  |15137    ||     746   |  8931         ||      776  |   3921        |
|    8388608 |     885   |18768    ||      503  | 5366    ||     167   |  4477         ||           |               |
|   16777216 |     320   | 8347    ||           |         ||     134   | 17180         ||           |               |
+------------+-----------+---------++-----------+---------++-----------+---------------++-----------+---------------+

(I haven't recorded rho tail length, which is why times appear erratic.)

Is there a well-known reason why cycle lengths tend to decrease as m increases?

If all C[i] values are the same, the iterator F(m) degenerates to repeated application of the 'standard' iterator, and will (I think) lead to shorter cycle length iff GCD(m+1,cycleLength) != 1, but this is a different effect.

Thanks in advance for any feedback on this,

Mick.

R.D. Silverman · 2014-12-11, 14:43

Quote:

Originally Posted by mickfrancis

I wonder if anyone could answer a question I have regarding iterator functions used in Pollard's Rho algorithm:

As I understand it, the aim is to use a function that is as psuedo-random as possible; this is assumed in the complexity analyses that have been carried out. It should also be computationally cheap for obvious reasons.

However, there are functions that we could consider that have shorter cycle (and tail) lengths than a perfectly (psuedo-)random one. An absurd example is the function that generates numbers spaced at a multiple of a factor (p) of N:

Code:

    p = getSmallestFactor(N);
    function f(x) = (x + p) % N;

This would loop (mod p) immediately and Pollard's Rho would find the factor. This would, of course completely defeat the object, as we are factorizing in order to find a factor.

My question is this: Are there 'better than psuedo-random' iterators that could be used, whose cycle-shortening benefits out-weigh their additional cost?

I have been playing with a class of function (that doesn't know about factors of N) that does produce shorter cycles. Unfortunately, the cost outweighs the benefits:

Suppose we have an array of distinct non-zero values C[0], C[1], ... and corresponding functions f(0), f(1), ... where f(i) is the 'standard' iterator using C[i] as the constant:

Code:

    function f(i)(x) = (x^2 + C[i]) % N;

If o represents function composition and we define function F(m) by:

Code:

    function F(m) = (m == 0) ? f(0) : f(m) o F(m-1);

then

Code:

    F(0) is the 'standard' iterator using C[0] as constant:
        x -> (x^2 + C[0]) % N

    F(1) is the function that iterates twice (with different C values):
        x -> ((x^2 + C[0])^2 + C[1]) % N
           = (x^4 + 2C[0]x^2 + C[0]^2 + C[1]) % N

    F(m)(x) generates a monic polynomial in x of degree 2^(m+1), with coefficients of x^i being non-zero iff i is even.

In tests, with N = 18868629790280349989518009992987136785227164415079137 (C53) with factor 7777774777777 (P13), I get the cycle lengths and times shown below. This is a Java implementation, so not that fast. The right-most set of values used x^1024 rather than x^2.

Code:

+------------+---------------------++---------------------++---------------------------++---------------------------+
|            | C[i] = i + 1        || C[i] = RANDOM()     || C[i] = 16384 + 16777216 i || C[i] = 16384 + 16777216 i |   
|            |                     ||                     ||                           ||    exp=1024               |
|            +-----------+---------++-----------+---------++-----------+---------------++-----------+---------------+   
|      m     | cycle len | time (s)|| cycle len | time (s)|| cycle len | time (s)      || cycle len | time (s)      |   
+------------+-----------+---------++-----------+---------++-----------+---------------++-----------+---------------+   
|          0 | 2537770   |    4    ||  1742273  |    9    ||    9408   |     5         ||  6073387  |     10        |
|          1 | 1149581   |    4    ||   559885  |   25    ||  784504   |     5         ||  2370108  |      8        |
|          2 |   85333   |   10    ||   168663  |    1    || 1217979   |     7         ||  1852565  |      7        |
|          3 | 1254046   |    7    ||  2800001  |   26    ||  573250   |     4         ||   411681  |      2        |
|          4 |  437527   |   10    ||   135296  |    7    ||  203384   |    10         ||  1012270  |     11        |
|          5 | 1218369   |   10    ||   682778  |    9    || 3235934   |    28         ||   226494  |      5        |
|          6 | 1026505   |    7    ||   437593  |   21    ||  365988   |     8         ||   195009  |     12        |
|          7 |  750226   |    8    ||   451631  |   13    ||  229190   |     2         ||   503277  |      4        |
|          8 |  418334   |    5    ||   294776  |   26    || 1294949   |    18         ||  1409182  |     17        |
|          9 |  349321   |   35    ||   375245  |    7    ||   52603   |     9         ||   861531  |     10        |
|         10 |  567977   |    9    ||  1936414  |   37    ||   26064   |    10         ||   391137  |      5        |
|         11 |  156450   |    3    ||  1551018  |   37    || 1326637   |    24         ||  1158178  |     20        |
|         12 |   24626   |   10    ||   187018  |    5    ||  165718   |    13         ||   297729  |      5        |
|         13 |  121306   |   12    ||  1002300  |   25    ||  683933   |    14         ||   251780  |     13        |
|         14 |  442266   |    7    ||   181412  |   20    ||   85678   |    14         ||   521311  |      8        |
|         15 |  156963   |   13    ||   183218  |   12    ||     946   |    29         ||    93879  |      3        |
|         16 |  249666   |   16    ||   662852  |   25    ||  692360   |    17         ||  1103360  |     29        |
|         20 |  126940   |    5    ||    43376  |    7    || 1379429   |    43         ||   114094  |      9        |
|         24 |  314699   |   11    ||  1007216  |   44    ||  282941   |    11         ||   278688  |     10        |
|         28 |  537623   |   24    ||   347046  |   21    ||    7142   |     7         ||   150583  |      6        |
|         32 |   62009   |    4    ||   423423  |   26    ||   93590   |    31         ||   666143  |     29        |
|         48 |  223585   |   25    ||   235338  |   72    ||   28398   |    23         ||   529759  |     40        |
|         64 |   11518   |    1    ||    41043  |   44    ||   28635   |     8         ||   163760  |     14        |
|         96 |   16999   |    2    ||   272321  |   63    ||  427018   |    53         ||    81186  |     10        |
|        128 |  258409   |   34    ||   137880  |  170    ||  310206   |    63         ||   561129  |    107        |
|        196 |  317769   |   84    ||   130109  |   85    ||   66443   |    46         ||    63363  |     46        |
|        256 |   77296   |   27    ||    68387  |   84    ||   37436   |    62         ||    62412  |    111        |
|        512 |   57461   |  115    ||   139949  |  169    ||  104195   |    71         ||    98073  |    121        |
|       1024 |  213690   |  250    ||    33953  |  168    ||   24878   |   247         ||      831  |     52        |
|       2048 |   33468   |  215    ||    10758  |  183    ||   78044   |   261         ||     4163  |     13        |
|       8192 |   42665   |  456    ||    31186  |  435    ||   23467   |   274         ||    46184  |    463        |
|      16384 |    6590   |  877    ||    30331  |  862    ||    5191   |   528         ||     1481  |    107        |
|      65536 |    6861   | 1020    ||     2597  |  371    ||    1293   |   517         ||     4511  |    438        |
|     132772 |    5542   |  929    ||     3656  |  868    ||    6285   |  1166         ||     4351  |    876        |
|     524288 |     327   |  234    ||     2439  | 2870    ||    3967   |  2575         ||       31  |    445        |
|    1048576 |     537   | 1740    ||        6  | 5535    ||    2699   |  4414         ||     1708  |   4057        |
|    2097152 |    1344   | 4125    ||      935  | 3611    ||     361   |  2343         ||     1518  |   3862        |
|    4194304 |     330   | 3793    ||       10  |15137    ||     746   |  8931         ||      776  |   3921        |
|    8388608 |     885   |18768    ||      503  | 5366    ||     167   |  4477         ||           |               |
|   16777216 |     320   | 8347    ||           |         ||     134   | 17180         ||           |               |
+------------+-----------+---------++-----------+---------++-----------+---------------++-----------+---------------+

(I haven't recorded rho tail length, which is why times appear erratic.)

Is there a well-known reason why cycle lengths tend to decrease as m increases?

If all C[i] values are the same, the iterator F(m) degenerates to repeated application of the 'standard' iterator, and will (I think) lead to shorter cycle length iff GCD(m+1,cycleLength) != 1, but this is a different effect.

Thanks in advance for any feedback on this,

Mick.

(1) You will not do better than cycles of length sqrt( pi/2 * p) ON AVERAGE with any prng. This is the expected
(asymptotic) cycle length based on the birthday "paradox".

(2) Even if you were to succeed in your goal, the effort would be pointless, IMO because you would be
finding a small improvement in an OBSOLETE algorithm. For numbers that are within reach of the method,
ECM and other methods will be faster.

bsquared · 2014-12-11, 14:57

Quote:

Originally Posted by R.D. Silverman

(2) Even if you were to succeed in your goal, the effort would be pointless, IMO because you would be
finding a small improvement in an OBSOLETE algorithm....

But IMO the effort is not pointless with respect to furthering his interest in and understanding of number theory, programming, and factorization methods.

mickfrancis · 2014-12-11, 15:14

Quote:

Originally Posted by R.D. Silverman

(1) You will not do better than cycles of length sqrt( pi/2 * p) ON AVERAGE with any prng. This is the expected
(asymptotic) cycle length based on the birthday "paradox".

(2) Even if you were to succeed in your goal, the effort would be pointless, IMO because you would be
finding a small improvement in an OBSOLETE algorithm. For numbers that are within reach of the method,
ECM and other methods will be faster.

Thanks for your reply on this.

I take your first point about psuedo-random number generators, of course - that is why I was wondering about "better than psuedo random" generators.

I also understand that Pollard's Rho is of relatively little use these days, and take your point that small improvements would be of no interest. However, if a generator could be found that reduced the cycle length by orders of magnitude (my F(4194304) does this, for example - expected cycle length of 3.5M goes down pretty consistently by a factor of more than 1000), would this not be of academic interest at least? What is it about these functions that shortens the cycle length?

I do appreciate that as a non-mathematician, I am probably barking up a whole forest of wrong trees, and really appreciate that you took the time to reply.

Kind regards,

Mick.

mickfrancis · 2014-12-11, 15:57

Quote:

Originally Posted by bsquared

But IMO the effort is not pointless with respect to furthering his interest in and understanding of number theory, programming, and factorization methods.

Absolutely right - I'm having a great time, regardless of the utility of my efforts!

jasonp · 2014-12-11, 17:36

The object is not to find a sequence of iterates that are 'more' random than some other sequence; Rho chooses a sequence whose members we hope are each a product of many primes, leading to a collision mod N between two such members. If you know something about the structure of the factors of N then rho can be modified to incorporate that structure; the best example is the factorization of the 8th Fermat number.

xilman · 2014-12-11, 19:44

Quote:

Originally Posted by jasonp

The object is not to find a sequence of iterates that are 'more' random than some other sequence; Rho chooses a sequence whose members we hope are each a product of many primes, leading to a collision mod N between two such members. If you know something about the structure of the factors of N then rho can be modified to incorporate that structure; the best example is the factorization of the 8th Fermat number.

I'm well aware that this viewpoint is heretical, but the steps of each of ECM, P-1 and P+1 produces a sequence of a product of (many) primes leading to a collision mod N.

Another, so far unrealised, algorithm would compute n! mod N in polynomial time (or, at least, in sub-exponential time) which would immediately give a fast factoring algorithm . I, and many others, have been thinking along these lines for many years. Needless to say, we've had no success.

mickfrancis · 2014-12-11, 22:32

Quote:

Originally Posted by jasonp

The object is not to find a sequence of iterates that are 'more' random than some other sequence; Rho chooses a sequence whose members we hope are each a product of many primes, leading to a collision mod N between two such members. If you know something about the structure of the factors of N then rho can be modified to incorporate that structure; the best example is the factorization of the 8th Fermat number.

Thanks Jason. I've just found Pollard and Brent's paper "Factorization of the Eighth Fermat Number", which looks very interesting - I'll give it a read and see if it helps me in my understanding of this.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
Random " % complete" ??	markg	Software	17	2008-05-24 18:03
Pseudo-random maps over an elliptic curve	ColdFury	Math	4	2007-05-29 21:30
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2014-12-11, 17:36	#6
jasonp Tribal Bullet Oct 2004 6725₈ Posts	The object is not to find a sequence of iterates that are 'more' random than some other sequence; Rho chooses a sequence whose members we hope are each a product of many primes, leading to a collision mod N between two such members. If you know something about the structure of the factors of N then rho can be modified to incorporate that structure; the best example is the factorization of the 8th Fermat number.