Re: Factoring, sf, and reasonable requests

From: Tim Peters (tim.one_at_comcast.net)
Date: 02/19/05 

Date: Sat, 19 Feb 2005 06:21:26 -0500

[JSH]
[...]
>>> Ax= Az(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)
>>>
>>> Az= Ax(-Ax +/- sqrt((Ax - 2j^2)^2 + 4Tj^2))/(2M^2 - 2Ax)
>>>
>>> where T = M^2 - j^2
>>>
>>> Here you have a two equations defining rationals Ax and Az, where M
>>> is the number to be factored and j is an integer you pick to try and
>>> factor it.
>>>
>>> I noted that by working backwards--using an M for which you have
>>> the factorization--you can see that for an integer Az that factors
>>> M, the rational Ax has a denominator that has the same prime factors
>>> as T.

[Rick Decker, tries to make sense of that]
>> Not in all cases. Let's take an extremely simple example.
>>
>> M = 15, j = 2. Thus T = 221 = 13*17. Now pick integers that factor
>> M and consider D = sqrt((Az - 2M^2)^2 - 4TM^2)):
>>
>> Az = 1. D = sqrt(2701), which is not rational.
>>
>> Az = 3. D = sqrt(3^2 * 101), which is not rational.
>>
>> Az = 5. D = sqrt(5^2 * (-35)), which isn't even real.
>>
>> Az = 15. D = sqrt(15^2 * (-883)), which also isn't real.
>>
>> So since none of the possible Az values yield a rational Ax,
>> your assertion about the denominator of Ax is meaningless.

[JSH, pulls a surprise out of his hat]
> An integer Az that factors M, is one which has a *single* prime factor
> of M.
>
> I did not mean an integer Az that is a factor of M.
>
> Given an Az with a single prime factor of M, you can get that factor by
> using a gcd, and that's what I meant.
>
> Ok, so there's no debate about saying what you mean, if it was
> ambiguous, sorry, but I don't mean that Az is a factor of M.
>
> Now go back, use Az's that have a single prime factor of M that do
> work, and see what happens.

OK, how about Az = 1120 = 2^5*5*7? Then gcd(Az, M) = gcd(1120, 15) = 5. Is
that of the proper form?

I'm guessing it is. Then (sorry, I'm switching to using "**" for
exponentiation, so I can paste these equations directly into a Python shell
for evaluation):

    D = sqrt((Az - 2*M**2)**2 - 4*T*M**2) =
        sqrt((1120 - 2*15**2)**2 - 4*221*15**2) =
        sqrt((1120 - 450)**2 - 198900) =
        sqrt(448900 - 198900) =
        sqrt(250000) =
        500

That looks rational to me <wink>.

Now I guess that by "denominator" in "Ax has a denominator" you mean the
(2j^2 - 2Az) in

    Ax= Az(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)

Is that right? Or do you mean something else? Assuming that is right,

    2*j**2 - 2*Az =
    2*2**2 - 2*1120 =
    8 - 2240 =
    -2232 =
    - 2**3 * 3**2 * 31

That doesn't have any factors in common with T = 221 = 13*17. But maybe I
don't know what "has a denominator that has the same prime factors as T"
means.

If I'm not failing to guess your meanings, then Az equal to 1188, 1280,
1476, 1600, 1764, 10400, and 17028 also lead to both that D is rational and
that 2j^2 - 2Az has no factors in common with T.

Or did you mistype your claim, and you really meant to claim that when D is
rational the denominator of Ax _never_ has a factor in common with T? That
would match the results I got with this example: I wasn't able to find any
Az with gcd(Az, 15) equal to 3 or 5, D rational, and gcd(2j^2 - 2Az, T) > 1.

As a general hint, truly meant to help: your writing is often so unclear
that a simple, concrete numeric example would really help to clarify your
intent. That's why people keep asking you for numeric examples. I don't
know why you refuse -- and it's obvious you'd often catch some of your
mistakes if you just tried to give a real example. Because I gave you a
numeric example in great deatil above, I don't believe it possible for you
to misunderstand what I said above. Then again, you could surprise me ...
but I'd rather you didn't <wink>.

Relevant Pages

  • Re: Factoring, sf, and reasonable requests
    ... >> your assertion about the denominator of Ax is meaningless. ... [JSH, pulls a surprise out of his hat] ... > Given an Az with a single prime factor of M, you can get that factor by ... rational the denominator of Ax _never_ has a factor in common with T? ...
    (sci.math)
  • Re: Factoring, sf, and reasonable requests
    ... Tim Peters wrote: ... use Az's that have a single prime factor of M that do ... My thesis was that the denominator would have the same prime factors as ... and it's not an ambiguous statement. ...
    (sci.crypt)
  • Re: Factoring, sf, and reasonable requests
    ... Tim Peters wrote: ... use Az's that have a single prime factor of M that do ... My thesis was that the denominator would have the same prime factors as ... and it's not an ambiguous statement. ...
    (sci.math)
  • Re: Simple answer, surrogate factoring
    ... [JSH] ... >> the gcd of the denominator with M, and for at least one case for any ... "dividing out factors in common between them" isn't the same as "dividing ... Here are the gcds: ...
    (sci.math)
  • Re: Simple answer, surrogate factoring
    ... [JSH] ... >> the gcd of the denominator with M, and for at least one case for any ... "dividing out factors in common between them" isn't the same as "dividing ... Here are the gcds: ...
    (sci.crypt)
Quantcast