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: IdleThoughtsAboutPollardRho

''' <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:
  * 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
********
[[[>50 This post will be less polished, as I'm not really
sure what I want to say, but thought I'd get it "out there"
to see if anyone had any comments.

TaggedAsMaths
]]]
I've had an idle thought about the Pollard Rho[0] method of integer factoring.
To start with, let's sketch how it works.

!! Pollard Rho in brief

The basic idea is that we have a number $N$ to factor, and we've
already stripped out all the really small factors by using a quick
hit of trial division[1].  Now what we do is run around the integers
modulo N and hope to get a coincidence.

So we have $N$ and we assume that there is some $p,$ currently unknown
to us, which divides $N.$

We're trying to find $p.$

We define a sequence $\{x_i\}_{i=0}^\infty$ with $x_0$ something a bit
arbitrary, and $x_{i+1}=x_i^2+c$ for some $c,$ often just a small
integer from 1 to 5 or so.

We compute the sequence modulo $N,$ but thinking about it modulo $p$
we can see that it must eventually start repeating.  So after some
values that don't get repeated we end up in a cycle (mod $p$).

So at some point $x_i=x_j\ (mod p)$ and we can detect this by
computing $gcd(x_j-x_i,N)$ and finding that it's bigger than 1.

!! The Algorithm

So the algorithm is:

{{{
    def f(x): x^2 + c

x_0 = k:
    rabbit = x_0
    turtle = x_0
    while True:
        rabbit = f(f(rabbit))
        turtle = f(turtle)
        g = gcd(rabbit-turtle,N)
        if 1 < g <=N:
            return g
}}}

[[[> https://www.solipsys.co.uk/images/Rho_93_5.png _ |>> N=93, c=5 <<| ]]]
!! Why it works

So how and why does this work?

Thinking about the sequence ${x}$ mod $p$ we can see that it eventually
cycles.  Each term is the square of the one before, plus a constant,
so we can think of the values as "pinging about randomly," and because
of the birthday paradox says we should get a repeat time $O(\sqrt{p}).$

So if $p$ isn't too big we should find it reasonably quickly, and in
any rate in time $O(n^{\frac{1}{4}}).$

!! And now for something completely different

So why do we use $f(x)=x^2+c$ ? Is there something special about that?

If we have any pseudo-random $f:Z_p -> Z_p$ then we'd think that would
work.  So we plot the digraph with nodes for integers and edges for $a$
goes to $b,$ the digraph we get for the quadratic shows that there are
lots of cycles that aren't too large, and the paths that take you into
the cycles are not very long.

On the other hand, the first quick hack I tried for a pseudo-random
thingy either has very long tails before we get to a cycle, or has very
long cycles.

|>>
********>
[[[ https://www.solipsys.co.uk/images/Rho_93_507.png ]]]
********
[[[ https://www.solipsys.co.uk/images/Rho_93_540.png ]]]
********<
<<|

I don't understand this.

True, I've only drawn digraphs for comparatively small $N,$ because
I don't have the tools immediately to hand to layout huge graphs. But
even so, there's something going on here that I don't understand.

I suspect there's something going on with the fact that $x^2+c$ is
such that every node has out degree 1, but in degree either 0 or 2
(with a couple of possible exceptions).  That might have something
to do with the overall structure, but I don't see how that's critical.

And if it /is/ critical, then perhaps we can make a pseudo-random
function that has the right properties, but is faster than computing
the square each time.  It's not a huge speed-up, but it might be
worth having.

And if it is the degree structure that matters, perhaps we can devise
one that's fast to compute and even /*more*/ favourable.

As I say, idle musings ...

----

!! References

[0] https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

[1] https://en.wikipedia.org/wiki/Trial_division
----

|>>
| |>> <<<< Prev <<<< ---- WhenOptimisingCodeMeasure <<| | : | |>> >>>> Next >>>> ---- MoreMusingOnPollardRho ... <<| |
----
********>
''' <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?IdleThoughtsAboutPollardRho" 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 : IdleThoughtsAboutPollardRho"         >
''' <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:

''' <centre><font size="+4"><INPUT TYPE="submit" VALUE="CLICK HERE TO SEND"></font></center>
******** width="6%"
******** width="47%"
If you include an email address then I'll be able to respond,
and conversely, if you don't, I won't!  Likewise, if you give
me explicit permission to add your comments here then I might
choose to do so, and if you don't, I won't!

So if you reply, please include your preferences, otherwise
I'll read you email, nod sagely, and file it away.
********<

''' <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>

********<