mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-06-17, 21:11   #1
mgb
 
"Michael"
Aug 2006
Usually at home

24×5 Posts
Default 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
mgb is offline   Reply With Quote
Old 2020-06-18, 04:32   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2·2,819 Posts
Default

Quote:
Originally Posted by mgb View Post
I tried your link and was asked to sign-in. I'm not enabling JS or joining google just to view your stuff.

Why not just post whatever you have directly here?
retina is online now   Reply With Quote
Old 2020-06-18, 11:03   #3
mgb
 
"Michael"
Aug 2006
Usually at home

8010 Posts
Default

Quote:
Originally Posted by retina View Post
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
mgb is offline   Reply With Quote
Old 2020-06-18, 14:33   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by mgb View Post
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();
Please move to misc.math
R.D. Silverman is offline   Reply With Quote
Old 2020-06-18, 19:25   #5
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

844210 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Please move to misc.math
Please don't quote a long post just to add a single line request.
Uncwilly is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
System management notes kriesel kriesel 6 2019-05-22 19:37
Pollard Rho Discrete Log rogue Math 6 2012-09-26 11:20
Work types in "Computers and Notes" table Chuck GPU to 72 3 2012-08-25 03:10
Mally's marginal notes devarajkandadai Math 3 2008-12-19 03:33
Pollard Rho Help? theta Factoring 2 2005-08-23 21:14

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

Sat Aug 15 14:35:59 UTC 2020 up 2 days, 11:11, 1 user, load averages: 1.91, 1.85, 1.81

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