Browse Groups

• [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
View Source
[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
• ... 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
View Source
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)
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]
• ... 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
View Source
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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.