- [pushing back on list]

--- Chris Caldwell <caldwell@...> wrote:> At 09:23 AM 7/7/2005, you wrote:

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

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

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 - Phil Carmody wrote:
> Anna is coming to Turku with my copy of the book today.

This sounds like one of the research problems in C&P. I've worked alot on

>

> 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?)

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] - David, quoting me:
> > I have had a wacky idea for a possible modification to pollard rho.

That's related, but the poly evaluation I'm after is at arbitrary points.

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

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

I certainly do. I submitted a whole bunch of 4/16 results, found quite easily,

> would like the results for the 4 squaring/16 a.f. polynomials, just let me

> know and I can send it on over.

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