mersenneforum.org Some Notes on Pollard's Rho
 Register FAQ Search Today's Posts Mark Forums Read

 2020-06-17, 21:11 #1 mgb   "Michael" Aug 2006 Usually at home 8010 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/1I-D.../view?ths=true
2020-06-18, 04:32   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

130068 Posts

Quote:

Why not just post whatever you have directly here?

2020-06-18, 11:03   #3
mgb

"Michael"
Aug 2006
Usually at home

24×5 Posts

Quote:
 Originally Posted by retina Why not just post whatever you have directly here?
Sorry about that. Here you go-

The function ai+1 = (ai^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 2-cycle, for example, has only 2 ways into it whereas a k-cycle 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 2-cycles 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 ai+1, ai+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 circle-tree 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 2020-06-18 at 11:11

2020-06-18, 14:33   #4
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by mgb Sorry about that. Here you go- The function ai+1 = (ai^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 2-cycle, for example, has only 2 ways into it whereas a k-cycle 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 2-cycles 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 ai+1, ai+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 circle-tree 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();

2020-06-18, 19:25   #5
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

2·32·7·67 Posts

Quote:
 Originally Posted by R.D. Silverman Please move to misc.math
Please don't quote a long post just to add a single line request.

 Similar Threads Thread Thread Starter Forum Replies Last Post kriesel kriesel 6 2019-05-22 19:37 rogue Math 6 2012-09-26 11:20 Chuck GPU to 72 3 2012-08-25 03:10 devarajkandadai Math 3 2008-12-19 03:33 theta Factoring 2 2005-08-23 21:14

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

Sat Aug 15 14:53:46 UTC 2020 up 2 days, 11:29, 1 user, load averages: 1.75, 1.81, 1.76