20200617, 21:11  #1 
"Michael"
Aug 2006
Usually at home
2^{4}×5 Posts 
Some Notes on Pollard's Rho
I have been examining the output from Pollard's method for different seeds and an interesting picture has emerged which you might have use for. Comments welcome as always.
https://drive.google.com/file/d/1ID.../view?ths=true 
20200618, 04:32  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2·2,819 Posts 
Quote:
Why not just post whatever you have directly here? 

20200618, 11:03  #3 
"Michael"
Aug 2006
Usually at home
80_{10} Posts 
Sorry about that. Here you go
The function a_{i+1} = (a_{i}^2 + 1) (mod n) is typical of the kind used in Pollard's Rho Method. The sequence is divided into two parts. The 'tail' and the 'cycle'. But it might be better to view the tail as a tree, with various branches joining up. Each branch represents a different starting seed, as will be seen. The output looks like this a1, a2,...ak, [A1, A2,...Ak] where ai, is in the tail/branch and Ai, is in the cycle. For all i, ai cannot be equal to Ai, otherwise it is in the cycle. Each Ai is the start of the cycle and can be arrived at from different starting values. For example suppose the starting value is x. The following can happen (1) x1, x2,...xk, Ai... and we are now in the cycle. Or, (2) x1, x2,...ai,...ak Ai... and we are in the cycle again. The x branch joins the a branch at ai. So different lead ins branch out like trees and each branch can enter the cycle at a different node or Ai. Also, there are usually a number of cycles that are independent from each other with different branches leading into it such as this B cycle  b1, b2,...bk, B1, B2,...Bk This might be one reason why Pollard's method fails sometimes. One version of the function (tortoise) goes into the A cycle and the other (hare) goes into the B cycle and are forever insulated from each other because there can be no Bi = Ai otherwise Bi is part of the A cycle. The larger the cycle is, the more likely f() is to go into that cycle because there are many ways into it. But there are small cycles too, sometimes of length 2, 3, 4,... that rarely show up because a 2cycle, for example, has only 2 ways into it whereas a kcycle has k ways in and each of these k tails/branches can be compound, more like a branching tree, as illustrated in (2) above. For non trivially small primes, the smaller 2cycles will only show up for specific starting seeds. Many different starting seeds can lead to the main, or biggest, cycle. Here are some of the entries to the cycle for p = 61. The cycle is in square brackets Seed 50 0, 1, 2, 5, 26, [6, 37, 28, 53, 4, 17, 46, 43,...] Seed 51 40, 15, 43, 20, 35, [6, 37, 28, 53, 4, 17, 46, 43...] Both branches enter the cycle at 6. Notice that both branches cannot share a common node/number. If they shared one number they would share the next and the next and so on and would be the same branch. Here we have two twigs, in brackets, converging on the same branch, underlined, and entering the cycle at 97 Seed 37 (57, 18,) 22, 81, 98, ...93, 65, 85, 55, [97, 17, 88,...] Seed 38 (31, 53, 83,) 22, 81, 98, ...93, 65, 85, 55, [97, 17, 88,...] So the twigs join at 22 becoming the same branch and that leads into the cycle at 97, so here are two ways along the tree structure that enter at 97. The well known rho shape shows one branch leading into a node on a single cycle. But when the whole system of branches and cycles emerges from all seeds from 1 to p  1 a different picture emerges. It is like a circle, which is a cycle, with trees growing out of each of its nodes. And there are a number of mutually exclusive cycles of different lengths, seemingly with one main (biggest) cycle. This is the cycle the algorithm is most likely to enter because it has so many trees growing out of it. From all this it seems that  (1) Two twigs entering the same branch cannot share a common node/number. (2) Two branches growing out of the same node on the cycle cannot share a common number. If they did, they would share the next number and the next etc. They only share a number at the node at which they converge becoming a single branch. (3) If there are two cycles, A and B, they cannot share the same number. If ai is in cycles A and B so are a_{i+1}, a_{i+2} etc so A and B are really the same cycle. (4) Each circle/cycle with its trees growing out of its nodes is a unique structure, not sharing any of its members with another circletree structure. They are mutually exclusive. (5) A randomly chosen seed can exist anywhere on a twig, branch or cycle. So maybe 50% of randomly chosen seeds are already half way to the cycle. This Pari program will print out some cycles and branches for small primes. PrintTree() = { local(p, i, k); p = input(); k = 1; while(k < p, i = 1; a = k; print("\n("k")___________________________________________________"); while(i < p  1, a = (a^2 + 1)%p; print1(a ", "); i++; ); k++; ); } PrintTree(); Last fiddled with by mgb on 20200618 at 11:11 
20200618, 14:33  #4  
Nov 2003
2^{2}×5×373 Posts 
Quote:


20200618, 19:25  #5 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
8442_{10} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
System management notes  kriesel  kriesel  6  20190522 19:37 
Pollard Rho Discrete Log  rogue  Math  6  20120926 11:20 
Work types in "Computers and Notes" table  Chuck  GPU to 72  3  20120825 03:10 
Mally's marginal notes  devarajkandadai  Math  3  20081219 03:33 
Pollard Rho Help?  theta  Factoring  2  20050823 21:14 