mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-12-11, 13:23   #1
mickfrancis
 
Apr 2014
Marlow, UK

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

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.
mickfrancis is offline   Reply With Quote
Old 2014-12-11, 14:43   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

165108 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
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.
R.D. Silverman is online now   Reply With Quote
Old 2014-12-11, 14:57   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

372310 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
(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.
bsquared is offline   Reply With Quote
Old 2014-12-11, 15:14   #4
mickfrancis
 
Apr 2014
Marlow, UK

23·7 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
(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 is offline   Reply With Quote
Old 2014-12-11, 15:57   #5
mickfrancis
 
Apr 2014
Marlow, UK

3816 Posts
Default

Quote:
Originally Posted by bsquared View Post
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!
mickfrancis is offline   Reply With Quote
Old 2014-12-11, 17:36   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·52·71 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2014-12-11, 19:44   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

22×3×5×193 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.

Last fiddled with by xilman on 2014-12-11 at 19:45 Reason: Clarification
xilman is offline   Reply With Quote
Old 2014-12-11, 22:32   #8
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
mickfrancis is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 21:14.


Thu Dec 1 21:14:45 UTC 2022 up 105 days, 18:43, 0 users, load averages: 0.67, 0.88, 0.93

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”