Loading ...
Sorry, an error occurred while loading the content.
 

Re Looking for resources

Expand Messages
  • Phil Carmody
    [pushing back on list] ... Anna is coming to Turku with my copy of the book today. I have had a wacky idea for a possible modification to pollard rho. I was
    Message 1 of 3 , Jul 8, 2005
      [pushing back on list]

      --- Chris Caldwell <caldwell@...> wrote:
      > At 09:23 AM 7/7/2005, you wrote:
      > >I'm many miles from home, and without my C&P, and floundering with my google
      > >searches. I don't suppose someone could provide some links, or a few quick
      > >hints for the following.
      >
      > I don't recall this. I've got the book. Where/how do you suggest I look?
      > Found it--three algorithms: are the points in artih. prog, geo prog or
      > arbitrary?

      Anna is coming to Turku with my copy of the book today.

      I have had a wacky idea for a possible modification to pollard rho.
      I was wondering if one could iterate different starting points (using the same
      function), and then the birthday paradox could kick in as you take gcds using
      differences between each possible pair of final values.

      t_i_0 = a_i, iterate t_i_m = t_i_{m-1}^2+a up to t_i_n
      Then look at (t_i_n - t_j_n) for all pairs {i,j},
      this, as in t_i_m-t_i_{m-1}, is a (recursive) difference of squares.
      To do this look at P(x) = Prod(x-t_i_n) at x=t_j_n

      Unfortunately there's the nasty factor of (t_i_n-t_i_n) in that product, which
      I need to remove. (Any ideas how to do this massive product of differences?)

      I don't believe it will be an improvement over the current Pollard Rho (as I
      don't believe in the 'random cycles'/'birthday paradox' nature of Rho in the
      first place), but believe it might shift how/where the birthday paradox kicks
      in. (Which is useless if my prejudice is correct :-| .)
      It however lets Rho be distributed very easily. It may be an old idea anyway.

      A second Rho idea, while I'm here:
      It's common knowledge that apart from x->x^2 and x->x^2-2 all x->x^2+a
      iterations are as good as each other. However I might be tempted to claim that
      x->x^2-6 is a (ever so fractionally) better iteration function than x->x^2+a
      for any n for finding small factors. What kind of test would I have to perform
      in order to verify if the improvement is measurable? I tested ten thousand
      numbers in GP, and 'visually' it looks like -6 finds factors faster than +a,
      but that could just be personal bias in only paying attention to the positive
      results.

      Unfortunately the improvement decreases to zero as the size of factors you're
      looking for increases. So even if my claim is true, you'd be most likely to be
      running simple Euclid-GCD-based (i.e. tree) trial division at that stage
      anyway, and not see its benefits.

      Phil

      () ASCII ribbon campaign () Hopeless ribbon campaign
      /\ against HTML mail /\ against gratuitous bloodshed

      [stolen with permission from Daniel B. Cristofani]

      __________________________________________________
      Do You Yahoo!?
      Tired of spam? Yahoo! Mail has the best spam protection around
      http://mail.yahoo.com
    • David Cleaver
      ... This sounds like one of the research problems in C&P. I ve worked alot on it and can see some similarities to your problem. In chapter 6, research
      Message 2 of 3 , Jul 8, 2005
        Phil Carmody wrote:
        > Anna is coming to Turku with my copy of the book today.
        >
        > I have had a wacky idea for a possible modification to pollard rho.
        > I was wondering if one could iterate different starting points (using the same
        > function), and then the birthday paradox could kick in as you take gcds using
        > differences between each possible pair of final values.
        >
        > t_i_0 = a_i, iterate t_i_m = t_i_{m-1}^2+a up to t_i_n
        > Then look at (t_i_n - t_j_n) for all pairs {i,j},
        > this, as in t_i_m-t_i_{m-1}, is a (recursive) difference of squares.
        > To do this look at P(x) = Prod(x-t_i_n) at x=t_j_n
        >
        > Unfortunately there's the nasty factor of (t_i_n-t_i_n) in that product, which
        > I need to remove. (Any ideas how to do this massive product of differences?)

        This sounds like one of the research problems in C&P. I've worked alot on
        it and can see some similarities to your problem. In chapter 6, research
        problem 6.16 starts out by saying:

        "Observe first the amusing algebraic identity:
        F(x) = ((x^2 - 85)^2 - 4176)^2 - 2880^2 =
        (x - 13)(x - 11)(x - 7)(x - 1)(x + 1)(x + 7)(x + 11)(x + 13)"

        which, as we can all see is also =
        (x^2 - 1^2)(x^2 - 7^2)(x^2 - 11^2)(x^2 - 13^2)
        [ie, your difference of squares]
        So, you can test 8 algebraic factors with only 3 squarings. This can also
        be extended up to 4 squarings to test 16 algebraic factors at once. I've
        written a program to generate these pretty quickly. However, I've also
        used this program to search for a 5 squaring/32 a.f. solution but haven't
        found any to date.

        I know that this won't completely cover your difference of squares
        multiplication, but you can use several different polynomials (similar to
        F(x) above) to try and obtain a covering set. I'm not sure how much this
        will help with your current problem, but I thought I'd throw it out there
        to see what you (and anyone else) thought. If you'd like the program, or
        would like the results for the 4 squaring/16 a.f. polynomials, just let me
        know and I can send it on over.

        -David C.


        > I don't believe it will be an improvement over the current Pollard Rho (as I
        > don't believe in the 'random cycles'/'birthday paradox' nature of Rho in the
        > first place), but believe it might shift how/where the birthday paradox kicks
        > in. (Which is useless if my prejudice is correct :-| .)
        > It however lets Rho be distributed very easily. It may be an old idea anyway.
        >
        > A second Rho idea, while I'm here:
        > It's common knowledge that apart from x->x^2 and x->x^2-2 all x->x^2+a
        > iterations are as good as each other. However I might be tempted to claim that
        > x->x^2-6 is a (ever so fractionally) better iteration function than x->x^2+a
        > for any n for finding small factors. What kind of test would I have to perform
        > in order to verify if the improvement is measurable? I tested ten thousand
        > numbers in GP, and 'visually' it looks like -6 finds factors faster than +a,
        > but that could just be personal bias in only paying attention to the positive
        > results.
        >
        > Unfortunately the improvement decreases to zero as the size of factors you're
        > looking for increases. So even if my claim is true, you'd be most likely to be
        > running simple Euclid-GCD-based (i.e. tree) trial division at that stage
        > anyway, and not see its benefits.
        >
        > Phil
        >
        > () ASCII ribbon campaign () Hopeless ribbon campaign
        > /\ against HTML mail /\ against gratuitous bloodshed
        >
        > [stolen with permission from Daniel B. Cristofani]
      • Phil Carmody
        ... That s related, but the poly evaluation I m after is at arbitrary points. The closest thing in C&P is in the research problems for exponential-time
        Message 3 of 3 , Jul 11, 2005
          David, quoting me:
          > > I have had a wacky idea for a possible modification to pollard rho.
          > > I was wondering if one could iterate different starting points (using the
          > same
          > > function), and then the birthday paradox could kick in as you take gcds
          > using
          > > differences between each possible pair of final values.
          > >
          > > t_i_0 = a_i, iterate t_i_m = t_i_{m-1}^2+a up to t_i_n
          > > Then look at (t_i_n - t_j_n) for all pairs {i,j},
          > > this, as in t_i_m-t_i_{m-1}, is a (recursive) difference of squares.
          > > To do this look at P(x) = Prod(x-t_i_n) at x=t_j_n
          > >
          > > Unfortunately there's the nasty factor of (t_i_n-t_i_n) in that product,
          > which
          > > I need to remove. (Any ideas how to do this massive product of
          > differences?)
          >
          > This sounds like one of the research problems in C&P. I've worked alot on
          > it and can see some similarities to your problem. In chapter 6, research
          > problem 6.16 starts out by saying:

          That's related, but the poly evaluation I'm after is at arbitrary points.
          The closest thing in C&P is in the research problems for exponential-time
          factoring algorithms section - the 'g^K' part-2 for P-1.

          > If you'd like the program, or
          > would like the results for the 4 squaring/16 a.f. polynomials, just let me
          > know and I can send it on over.

          I certainly do. I submitted a whole bunch of 4/16 results, found quite easily,
          to C&P several years ago, but decided that 5/32 was _hard_. However, hard
          problems can sometimes be solved by throwing a combination of the right
          algorithm and the right (quantity of) hardware, and enough time. Therefore I'd
          like to revisit it. I can let you have what I have too, in case it's useful,
          but I don't think it will be, as it surely doesn't scale to 5/32, and also
          makes _absolutely_ no sense to me at all any more.

          Phil

          () ASCII ribbon campaign () Hopeless ribbon campaign
          /\ against HTML mail /\ against gratuitous bloodshed

          [stolen with permission from Daniel B. Cristofani]

          __________________________________________________
          Do You Yahoo!?
          Tired of spam? Yahoo! Mail has the best spam protection around
          http://mail.yahoo.com
        Your message has been successfully submitted and would be delivered to recipients shortly.