Re: Reality check, surrogate factoring

From: Mack (macckone_at_a_nospamjunk123_ol.com)
Date: 01/28/05 

Date: Fri, 28 Jan 2005 00:45:25 GMT

On Wed, 26 Jan 2005 21:22:48 -0500, Rick Decker <rdecker@hamilton.edu>
wrote:

>
>
>Tim Smith wrote:
>
>> In article <1106707007.031093.186480@z14g2000cwz.googlegroups.com>,
>> jstevh@msn.com wrote:
>>
>>>But, you're factoring T, where T = M^2 - j^2, where M is your target, and
>>>j is picked. Like typically j is odd, as M is odd (though you may need to
>>>make it even, more later), and you can also pick j such that T is
>>>divisible by 3, or such that it is divisible by any number you wish it to
>>>be.
>>>
>>>You also get a partial factorization of T at the outset as
>>>
>>>T = (M-j)(M+j)
>>>
>>>so what I'm saying is that some people somewhere work really hard to pick
>>>p_1 and p_2 so that p_1 p_2 is hard to factor by known methods, and
>>>surrogate factoring allows you to blow all of that out of the water by
>>>shifting to another number, easy to factor.
>>
>>
>> You should give examples, using small integers. E.g., pick a couple of 2
>> digit primes, multiply them, and show how your methods would be used to
>> factor that product.
>>
[snip]
>We've left off some relevant questions:
>
>1. In my example, it appears that j = 2 was a lucky choice.
> How far do we have to search among the j's to get an
> x that has a *nontrivial* (ie., not 1 or M) factor
> in common with M? If M were a 200-digit composite, for
> example, would we have to look through 10^100 candidates
> for j?

It is a distinct possibility that you will have to look through a
LOT of j's before you get a nontrivial factorization. Is there some
method of choosing j's that produce nontrival factorizations?

>
>2. In my example, all we had to do was use the "obvious"
> factors 17 and 13 of T. If M was a 200-digit number
> and none of the choices for j gave us a useful x,
> would we have to (somehow) factor T further to get
> some f_1 and f_2 that would yield a useful result,
> given that each of the obvious factors is about 200
> digits long?

If j is chosen so that T is easy to factor that could
help. In your case T only has two factors.
The general case is that T has many factors.
What happens when T has more than two factors?

>
>3. Although I didn't explain it, finding the a's is
> easy. Finding *all* possible a's for which x is
> rational requires another factorization. Do we
> ever have to do this, and if so, can it be done
> quickly? The number we'd have to factor is
> approximately as large as M^2.
>

Off the top of my head it would seem the answer is
that doing this is required some of the time. Cycling
through the list of a's that gives rational x's would
seem to be necessary. When the method gives a
trivial factorization isn't it necessary to try other choices
of a's?

>Hope this helps. I apologize for the length.
>
>
>Regards,
>
>Rick

Leslie 'Mack' McBride
remove text between _ marks to respond via e-mail