Suggest a change

These fields are all optional and need only
be supplied if you would like a direct reply.

Subject
Your email address
Your real name

You must answer this!

If you don't, my spam filtering will
ensure that I never see your email.

What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.

File: MoreMusingOnPollardRho

''' <link rel="alternate" type="application/rss+xml"
'''       href="/rss.xml" title="RSS Feed">

********> width="25%"
|>>
''' <a title="Subscribe to my feed"
'''    rel="alternate"
'''    href="https://www.solipsys.co.uk/rss.xml">
'''    <img style="border-width: 0px;"
'''         src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png"
'''         align="middle"
'''         alt="" />Subscribe!</a>
_
''' <a href="https://twitter.com/ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png"
'''      title="By: TwitterButtons.net"
'''      width="212" height="69"
'''      alt="@ColinTheMathmo"
'''     /></a>
<<|
----
My latest posts can be
found here:
  * ColinsBlog
----
Previous blog posts:
  * IdleThoughtsAboutPollardRho
  * WhenOptimisingCodeMeasure
  * ADogCalledMixture
  * AnotherPayPalScam
  * WhyTopPostingHasWon
  * UnexpectedInteractionOfFeatures
  * ArchimedesHatBoxTheorem
  * ConsideringASphere
  * ToLinkOrNotToLink
  * GenericAdviceForWritingAThesis
  * JustTeachMyChildTheMaths
  * NotASpectatorSport
  * LeftTruncatablePrime
  * TheDoctorAndTheLawyer
  * FourPointsTwoDistancesProof
  * MeetingRonGraham
  * NapkinRingVersusSphericalCap
  * TheFourPointsPuzzle
  * RadiusOfTheEarthPartTwo
  * GrepTimingAnomaly
  * TheRadiusOfTheEarth
  * ThisWorksToCureMyHiccoughs
  * PerhapsWeSavedOne
  * ThinkingAboutMastodon
  * DisappearingTrainsOnVirgin
  * TheIndependenceGame
  * OneOfMyFavouritePuzzles
  * ThinkingAboutRecursion
  * MemorisingTheTube
  * SpikeySpheres
  * SurprisinglyQuick
  * AnUnexpectedFraction
  * YouHaveToAdmireTheirOptimism
  * RepresentativesMatter
  * PythagorasByIncircle
  * APuzzleAboutPuzzles
  * HowNotToDoTwitter
  * Calculating52FactorialByHand
  * SmallThingsMightNotBeSoSmall
  * NotIfYouHurry
  * FactoringViaGraphThreeColouring
  * AnotherProofOfTheDoodleTheorem
  * WhenObviousIsNotObvious
  * GraphThreeColouring
  * TheDoodleTheorem
  * BeCarefulWhatYouSay
  * TheMutilatedChessboardRevisited
  * AMirrorCopied
  * TheOtherOtherRopeAroundTheEarth
  * PhotocopyAMirror
  * ThePointOfTheBanachTarskiTheorem
  * SieveOfEratosthenesInPython
  * FastPerrinTest
  * RussianPeasantMultiplication
  * FindingPerrinPseudoPrimes_Part2
  * FindingPerrinPseudoPrimes_Part1
  * TheUnwiseUpdate
  * MilesPerGallon
  * TrackingAnItemOnHackerNews
  * HackerNewsUserAges
  * PokingTheDustyCorners
  * ThereIsNoTimeForThis
  * PublicallySharingLinks
  * LearningTimesTables
  * GracefulDegradation
  * DiagrammingMathsTopics
  * OnTheRack
  * SquareRootByLongDivision
  * BeyondTheBoundary
  * FillInTheGaps
  * SoftwareChecklist
  * NASASpaceCrews
  * TheBirthdayParadox
  * TheTrapeziumConundrum
  * RevisitingTheAnt
  * TheAntAndTheRubberBand
  * IrrationalsExist
  * MultipleChoiceProbabilityPuzzle
  * RandomEratosthenes
  * WrappingUpSquareDissection
  * DissectingASquarePart2
  * DissectingACircle
  * DissectingASquare
  * AnOddityInTennis
  * DecisionTreeForTennis
  * DecisionTreesInGames
  * AMatterOfConvention
  * DoYouNourishOrTarnish
  * BinarySearchReconsidered
  * TwoEqualsFour
  * TheLostPropertyOffice
  * TheForgivingUserInterface
  * SettingUpRSS
  * WithdrawingFromHackerNews
----
Additionally, some earlier writings:
  * RandomWritings.
  * ColinsBlog2010
  * ColinsBlog2009
  * ColinsBlog2008
  * ColinsBlog2007
  * ColinsBlogBefore2007
********
!! More thoughts about Pollard Rho

[[[>
The previous post can be found here:
  * IdleThoughtsAboutPollardRho

This page has been _ TaggedAsMaths
]]]
After my previous post I started to explore a little more about
how the function in Pollard Rho affects what's going on.  As yet
I've not come to any conclusions, and I'm currently deep in the
"I'm confused" stage of the exploration. I'm sure there are other
people know all this, but I don't know who they are, and haven't
been able to find any write-ups, so I'll just carry on.

!! The role of the function ...

Pollard Rho works by iterating a function $f:Z_n -> Z_n$ and we
look for a cycle modulo $p,$ where $p$ is a factor of $n$.  The
usual function is $f(x)=x^2+c$ for some $c$, and I was wondering
about using another function that "hops about" pseudo-randomly,
and whether that would work.  But my first attempt didn't seem to
work, and I speculated that the quadratic nature might actually
matter.  The quadratic form means that nodes in the transition
graph all have out degree 1, but in degree either 0 or 2.  Maybe
that matters.

So I decided to experiment with random graphs of different in-degrees.

!! Having in-degree $k$ ...

[[[>
{{{
#!/usr/bin/python

import sys
from random import *

n = int(sys.argv[1])
k = int(sys.argv[2])

nodes = range(n)
targets = sample( nodes, (n+k-1)/k )
targets = k*targets
shuffle(targets)

for node in nodes:
    print targets[node]
}}}
]]]
This Python program takes a value $n$, which is the number we think we
want to factor, and an in-degree $k$ for the graph nodes.  We randomly
select $n/k$ elements from the range $0$ to $n-1$, and then replicate
those elements $k$ times, and shuffle them.  The result is a list which
for each element shows who it gets mapped to.  Every element either has
nothing coming in, or $k$ coming in.

So we pick a value of $n$ - say $n=10000153$ - and then for each $k$ in
the range $1$ to $4$ we generate the graph.  Having done so, we then
run the Pollard Rho algorithm.

!! What happens when we factor?

[[[>
{{{
mapping = [ int(x.strip()) \
    for x in \
        file(sys.argv[1]).readlines() \
    ]
n = len(mapping)

k = int(sys.argv[2])

rabbit, turtle, steps = k, k, 0

while True:

rabbit = mapping[mapping[rabbit]]
    turtle = mapping[turtle]
    steps += 1
    if gcd(rabbit-turtle,n) != 1:
        print gcd(rabbit-turtle,n), steps
        sys.exit(0)
}}}
]]]
Having produced random "functions" we can now use the Pollard Rho
factoring algorithm to try to factor the number we started with. In
doing so, we can see if the in-degree seems to have an influence on
how quickly we factor.  It's not really the "time" that matters, it
is the number of "steps" we take in the factorisation.

The hope is that with larger in-degrees the graph will be more
"squat" and we'll home into a cycle more quickly.  That would mean
that we take fewer steps, so it will run more quickly.  We're still
not looking at a huge improvement, but who knows.

So let's run this, and give several different possible starting nodes
to try to see if we get some sort of spread.

----
|>> https://www.solipsys.co.uk/images/PollardRhoTiming.png <<|
----

Well, that's disappointing.  There doesn't actually seem to be any
real change, even though you'd hope that with an in-degree of 4, or 8,
perhaps you'd zoom in on the cycle more quickly. But these experiments
appear not to support that.

Of course I'm still using relatively small numbers, about $10^7$, so
maybe that matters.  But even so ...

I guess I /really/ don't understand this.
----

|>>
| |>> <<<< Prev <<<< ---- IdleThoughtsAboutPollardRho <<| | : | |>> >>>> Next >>>> ---- JustGiveMeTheAnswer ... <<| |
----
********>
''' <a href="https://mathstodon.xyz/@ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/images/Mastodon_Mascot.png"
'''      width="256" height="280"
'''      alt="https://mathstodon.xyz/@ColinTheMathmo"
'''     /></a>
********
''' <a href="https://mathstodon.xyz/@ColinTheMathmo/">You can follow me on Mathstodon.</a>
_ _ _ _
[[[>
''' <a href="https://twitter.com/ColinTheMathmo">Of course, you can also<br>follow me on twitter:</a>

''' <a href="https://twitter.com/ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png"
'''      title="By: TwitterButtons.net"
'''      width="212" height="69"
'''      alt="@ColinTheMathmo"
'''     /></a>
''' <img src="/cgi-bin/CountHits.py?MoreMusingOnPollardRho" alt="" />
]]]
********<

----

!! Send us a comment ...

''' <form action="https://www.solipsys.co.uk/cgi-bin/FormMail.pl" method=post>
''' <input type=hidden name="recipient"               value="colinsblogcomment@solipsys.co.uk" >
''' <input type=hidden name="subject"                 value="Blog comment : MoreMusingOnPollardRho"         >
''' <input type=hidden name="redirect"                value="https://www.solipsys.co.uk/new/ThankYouForYourComment.html" >
''' <input type=hidden name="missing_fields_redirect" value="https://www.solipsys.co.uk/RequestError.html">
''' <input type=hidden name="env_report"              value="REMOTE_HOST, REMOTE_ADDR, HTTP_USER_AGENT"  >
''' <input type=hidden name="print_blank_fields"      value="1"                                          >

********> width="47%"
You can send us a message here. It doesn't get published,
it just sends us an email, and is an easy way to ask any
questions, or make any comments, without having to send a
separate email. So just fill in the boxes and then
''' <font size="+4"><INPUT TYPE="submit" VALUE="CLICK HERE TO SEND"></font>
******** width="53%"
********<

''' <table cellpadding="5">
'''   <tr>
'''     <td valign="top">Your name </td> <td valign="top">:</td>
'''     <td> <input type=text name="realname" size="48"> </td>
'''   <tr>
'''     <td valign="top">Email </td> <td valign="top">:</td>
'''     <td> <input type=text name="email" size="48"> </td>
'''     </tr>
'''   <tr>
'''     <td valign="top">Message </td> <td valign="top">:</td>
'''     <td> <TEXTAREA NAME="Message" ROWS=10 COLS=64></TEXTAREA> </td>
'''     </tr>
'''   </table>

''' <center>
'''   <font size="+4">
'''     <INPUT TYPE="submit" VALUE="CLICK HERE TO SEND">
'''     </font>
'''   </center>
''' </form>

********<