Re: Reality check, surrogate factoring

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 01/28/05 

Date: Thu, 27 Jan 2005 21:18:12 -0500

Mack wrote:

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

<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?
>
If there is, James might be on to something useful, but I don't
see it yet and admit to being skeptical.

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

I've thought about it some more and it turns out that
what I do is completely independent of how T is
factored, so question (2) is bootless.
>
>
>>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?

It might be. However, given my factorization to get a_1 and a_2
(explained in another post), I can express the possible
values of x and it turns out that I can express *any* x
given a suitable a_2 (or a_1), so it seems that there's
also nothing useful in question (3).

Regards,

Rick

Relevant Pages

  • Re: JSH: Remarkably odd
    ... public intfactor(int num) { ... then you have a nontrivial factorization of D. So you ... I argue that rational v EXISTS such that that condition is set. ...
    (sci.math)
  • Re: Reality check, surrogate factoring
    ... Mack wrote: ... > LOT of j's before you get a nontrivial factorization. ...
    (sci.math)
  • Re: JSH: Why factoring solution must work
    ... wouldn't suffice to generate a nontrivial factorization of D. ... The point is that for all interesting D, you won't be able to satisfy ... your minima condition. ...
    (sci.math)
  • Re: JSH: Why factoring solution must work
    ... wouldn't suffice to generate a nontrivial factorization of D. ... Not necessary professor Decker of Hamilton College. ...
    (sci.math)
  • Re: Proof factoring solution is closed form
    ... > Now Rick Decker has been at his game for years now, ... > derived in my original post that given a full factorization of Tj^2 to ... you cannot get a factorization of M. ...
    (sci.math)