Re: Factoring, sf, and reasonable requests
From: Tim Peters (tim.one_at_comcast.net)
Date: 02/19/05
- Next message: Mike Terry: "Re: Sign conventions"
- Previous message: A N Niel: "Re: inner product spaces."
- In reply to: jstevh_at_msn.com: "Re: Factoring, sf, and reasonable requests"
- Next in thread: C. Bond: "Re: Factoring, sf, and reasonable requests"
- Messages sorted by: [ date ] [ thread ]
Date: Sat, 19 Feb 2005 13:56:59 -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.
[Tim Peters, tries to fill in other gaps]
>> 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.
[JSH]
> My thesis was that the denominator would have the same prime factors as
> T, and it's not an ambiguous statement.
You don't get it. I'm sure your meaning is clear to _you_, but in the
absence of a concrete example, there are many things it _could_ plausibly
mean, because ""has a denominator that has the same prime factors as T" is
so vaguely stated. Among them:
- The set of primes that divide the denominator is equal to the set
of primes that divide T.
- The set of primes that divide the denominator is a subset of the
set of primes that divide T.
- The set of primes that divide the denominator is a superset of the
set of primes that divide T.
- The set of primes that divide the denominator and the set of primes
that divide T have at least one element in common.
- Variations on all the above where it's not just the sets of
primes that are of interest, but also the exponents on one or more
primes in the canonical factorizations of the denominator and T.
Since I found rationals where the canonical factorizations of the
denominator and T had nothing in common, it didn't matter which of those you
actually meant: they were counterexamples to all plausible meanings. I was
lucky that way in this case.
You should read some good mathematical exposition. Since you're a
programmer, maybe you have Knuth's books handy? Despite that he writes with
extraordinary clarity, note that he often gives small concrete examples
anyway. That's important if you want to be understood, and, believe it or
not, your mathematical expositions are very hard to follow. You must know
that already, since so few people even try to understand them anymore. One
way to improve that situation is to give concrete examples, as even the
masters do.
> So the denominator didn't. Interesting. That thesis was wrong.
As above, I still don't know exactly what your thesis was, but I'm gratified
that the examples managed to point out something of interest to you.
> Now then, do you suppose that denominator's factors are *random* or
> dependent in some way on mathematical rules?
They're obviously not random. They may be pseudo-random (formulas even
simpler than this have been used as the basis of PRNGs in practice, and have
similar form -- in fact, modularly adding the outputs of two dumb PRNGs of
different algebraic structure is an effective practical way to create a
better PRNG than either of the inputs; the "different algebraic structure"
part doesn't apply in this case, though).
> If they are not random, then do you suppose some way might be found to
> figure out how to determine them?
I talked about that earlier. In a nutshell, there are very few useful
results relating the factorization of a sum to the factorizations of the
addends that go into that sum. For example, is i+j divisible by 17? Not
enough info to say. What if we know that i is divisible by 17? Same
answer. What if we know that i is not divisible by 17? Ditto. What if we
know that both aren't divisible by 17? We _still_ can't tell whether the
sum is. The only we can "win" is to know in advance whether i = -j mod 17.
That likely (meaning this is just an educated guess) makes this approach a
very tough row to hoe.
> If that way does not itself depend on knowing the prime factors of M,
> why would that not be a potential major threat to Internet security?
Sorry, I couldn't make sense of that question.
> Now then, for some of you the exchange should be surprising as you're
> looking a this as black and white:
>
> a: I have to get everything right or lose
>
> b: If I'm wrong anywhere that proves my ideas are worthless
>
> If you believe that, fine, I don't care, but I thought it worth
> pointing out how simplistically some of you may be thinking.
I'm going to quote in full the message in which you introduced this test.
*I* don't know why you thought it was so important, but it was you who set
it up as a black-and-white test. So if people take you at your word on
that, the primary blame for encouraging simplistic thinking about it falls
on you:
From: jstevh@msn.com
Newsgroups: sci.crypt,sci.math,alt.math.recreational
Subject: Easy test of surrogate factoring
Date: 17 Feb 2005 17:01:27 -0800
Organization: http://groups.google.com
Lines: 49
Message-ID: <1108686448.904328.183930@o13g2000cwo.googlegroups.com>
Now I've accused some posters of lying, and I've issued warnings
mentioning hackers and terrorists, so it's only fair that I give an
easy test for people to defend themselves, as later, there may be
no defense. My accusations alone may be enough to get some of you
in trouble, in a world where few people will be interested in
listening to reasons.
They may simply act.
The test is simple.
I say that the denominator of Ax for an integer solution of Az,
contains only prime factors of T.
Where
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)
and T = M^2 - j^2, and so the test would be for someone to pick an
M for which they have the factorization, and pick some integer j,
to get T.
Then use an Az which has only one prime factor of M, to solve for
an Ax, and factor its denominator.
I'm *telling* you that the denominator will only have prime factors
in common with T.
If I'm wrong, then the world has its first perfect random number
generator.
If I'm right, then for all we know by this time, hackers may be
having a field day.
It's not a hard test.
I mention for governments and their prosecutors who may come later
that some of the posters here may have acted in their own selfish
interest, possibly believing they could exact some personal gain by
lying here.
Others may represent third parties.
It would make sense to check them all very carefully.
James Harris
If it's still your claim that the existence of these counterexamples means
the world has its first perfect random number generator (by which I guess
you mean a perfect deterministic pseudorandom number generator), of course I
disagree.
- Next message: Mike Terry: "Re: Sign conventions"
- Previous message: A N Niel: "Re: inner product spaces."
- In reply to: jstevh_at_msn.com: "Re: Factoring, sf, and reasonable requests"
- Next in thread: C. Bond: "Re: Factoring, sf, and reasonable requests"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
