Re: Simple answer, surrogate factoring
From: Tim Peters (tim.one_at_comcast.net)
Date: 03/04/05
- Next message: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Previous message: spinoza1111_at_yahoo.com: "Re: What constitutes "around the world"?"
- In reply to: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Next in thread: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Reply: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 4 Mar 2005 18:51:31 -0500
[...]
[JSH]
>>> 2M^2 - 2(+/-(f_1 - f_2) + 2j^2
[Tim Peters]
>> This one is missing a right parenthesis; don't know whether
>>
>> 2M^2 - 2(+/-(f_1 - f_2)) + 2j^2
>>
>> or
>>
>> 2M^2 - 2(+/-(f_1 - f_2) + 2j^2)
>>
>> was intended.
[JSH]
> Sorry, should be
>
> 2M^2 - 2(+/-(f_1 - f_2) + 2j^2)
OK.
[...]
>> I tried all plausible (to me) ways of fleshing out an implementation
>> from this, and they all failed to factor some 3-digit composites.
> Well, the proof is actually not hard, and it is perfect, so that means
> in this case I can say definitely that you made some mistake.
>
> First off, you *will* get a factor of M, which has to be divided off,
> and maybe you can get more than one factor of M, but in any event, you
> have to divide off all factors of M, first.
I really don't know what that means, but will show the work below. It
doesn't match what you originally wrote, so maybe you're just not writing
clearly enough to follow:
>> and you divide out any factors in common between them, and then take
>> the gcd of the denominator with M, and for at least one case for any
>> non-zero j coprime to M, you will have a prime factor of M.
"dividing out factors in common between them" isn't the same as "dividing
off factors of M" (which I guess means "divide out multiples of M", not "for
each p such that p is a factor of M, divide out multiples of p"), right?
> What's left over will have a single prime factor of M for at least one
> case, as the mathematical proof is in this time.
>
> If you do it right, it will work.
Sorry, I can't make it work, no way, no how. Perhaps you could show how it
finds a factor of M=221 at j=2.
M = 221 = 13 * 17
j = 2
T = M**2 - j**2 = 48837 = 3 * 73 * 223
T*j**2 = T*4 = 195348 = 2**2 * 3 * 73 * 223
All ways to split T*j**2 as product f1*f2 both >= 1:
f1 f2
------ ------
1 195348
2 97674
4 48837
3 65116
6 32558
12 16279
73 2676
146 1338
292 669
219 892
438 446
876 223
223 876
446 438
892 219
669 292
1338 146
2676 73
16279 12
32558 6
65116 3
48837 4
97674 2
195348 1
If there's a way to get from one of those to 13 or 17, it's not a way you
wrote about. Here are the gcds:
gcd((1-195348)+8, 221) = 1
gcd(-(1-195348)+8, 221) = 1
gcd((2-97674)+8, 221) = 1
gcd(-(2-97674)+8, 221) = 1
gcd((4-48837)+8, 221) = 1
gcd(-(4-48837)+8, 221) = 221
gcd((3-65116)+8, 221) = 1
gcd(-(3-65116)+8, 221) = 1
gcd((6-32558)+8, 221) = 1
gcd(-(6-32558)+8, 221) = 1
gcd((12-16279)+8, 221) = 1
gcd(-(12-16279)+8, 221) = 1
gcd((73-2676)+8, 221) = 1
gcd(-(73-2676)+8, 221) = 1
gcd((146-1338)+8, 221) = 1
gcd(-(146-1338)+8, 221) = 1
gcd((292-669)+8, 221) = 1
gcd(-(292-669)+8, 221) = 1
gcd((219-892)+8, 221) = 1
gcd(-(219-892)+8, 221) = 1
gcd((438-446)+8, 221) = 221
gcd(-(438-446)+8, 221) = 1
gcd((876-223)+8, 221) = 1
gcd(-(876-223)+8, 221) = 1
gcd((223-876)+8, 221) = 1
gcd(-(223-876)+8, 221) = 1
gcd((446-438)+8, 221) = 1
gcd(-(446-438)+8, 221) = 221
gcd((892-219)+8, 221) = 1
gcd(-(892-219)+8, 221) = 1
gcd((669-292)+8, 221) = 1
gcd(-(669-292)+8, 221) = 1
gcd((1338-146)+8, 221) = 1
gcd(-(1338-146)+8, 221) = 1
gcd((2676-73)+8, 221) = 1
gcd(-(2676-73)+8, 221) = 1
gcd((16279-12)+8, 221) = 1
gcd(-(16279-12)+8, 221) = 1
gcd((32558-6)+8, 221) = 1
gcd(-(32558-6)+8, 221) = 1
gcd((65116-3)+8, 221) = 1
gcd(-(65116-3)+8, 221) = 1
gcd((48837-4)+8, 221) = 221
gcd(-(48837-4)+8, 221) = 1
gcd((97674-2)+8, 221) = 1
gcd(-(97674-2)+8, 221) = 1
gcd((195348-1)+8, 221) = 1
gcd(-(195348-1)+8, 221) = 1
Since the ones that return 1 are hopeless, here are the rest:
gcd(-(4-48837)+8, 221) = 221
gcd((438-446)+8, 221) = 221
gcd(-(446-438)+8, 221) = 221
gcd((48837-4)+8, 221) = 221
Two of those are redundant, so it's down to:
gcd((438-446)+8, 221) = 221
gcd((48837-4)+8, 221) = 221
It's unclear in
>> The numerator is just
>>
>> (+/-(f_1 - f_2) + 2j^2 +/- (f_1 + f_2))
whether you want to try all 4 ways implied by the two +/-, so I tried all 4.
Similarly, for each of those, I tried both ways of interpreting
>> 2M^2 - 2(+/-(f_1 - f_2) + 2j^2)
for the denominator. So for the 2 gcds above, I tried 8 ways each of
picking numerator and denominator, and they all fizzled out.
>> and you divide out any factors in common between them, and then take
>> the gcd of the denominator with M, and for at least one case for any
>> non-zero j coprime to M, you will have a prime factor of M.
gcd(884, 97682) = 442
denom/gcd = 97682/442 = 221
gcd(221, 221) = 221
gcd(884, 97650) = 2
denom/gcd = 97650/2 = 48825
gcd(48825, 221) = 1
gcd(900, 97682) = 2
denom/gcd = 97682/2 = 48841
gcd(48841, 221) = 221
gcd(900, 97650) = 450
denom/gcd = 97650/450 = 217
gcd(217, 221) = 1
gcd(-868, 97682) = 2
denom/gcd = 97682/2 = 48841
gcd(48841, 221) = 221
gcd(-868, 97650) = 434
denom/gcd = 97650/434 = 225
gcd(225, 221) = 1
gcd(-884, 97682) = 442
denom/gcd = 97682/442 = 221
gcd(221, 221) = 221
gcd(-884, 97650) = 2
denom/gcd = 97650/2 = 48825
gcd(48825, 221) = 1
gcd(97682, 0) = 97682
denom/gcd = 0/97682 = 0
gcd(0, 221) = 221
gcd(97682, 195332) = 2
denom/gcd = 195332/2 = 97666
gcd(97666, 221) = 1
gcd(16, 0) = 16
denom/gcd = 0/16 = 0
gcd(0, 221) = 221
gcd(16, 195332) = 4
denom/gcd = 195332/4 = 48833
gcd(48833, 221) = 1
gcd(-97666, 0) = 97666
denom/gcd = 0/97666 = 0
gcd(0, 221) = 221
gcd(-97666, 195332) = 97666
denom/gcd = 195332/97666 = 2
gcd(2, 221) = 1
gcd(0, 0) = 0
denom/gcd = 0/0 = senseless, so skip this one
gcd(0, 195332) = 195332
denom/gcd = 195332/195332 = 1
gcd(1, 221) = 1
"Dividing off factors of M" out of the denominator instead doesn't work
either here (still leaves gcds of 1 or 221 in the end).
How do you get a factor of M=221 at j=2?
- Next message: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Previous message: spinoza1111_at_yahoo.com: "Re: What constitutes "around the world"?"
- In reply to: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Next in thread: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Reply: jstevh_at_msn.com: "Re: Simple answer, surrogate factoring"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
