Re: Surrogate factoring, surprising result
From: Tim Peters (tim.one_at_comcast.net)
Date: 03/06/05
- Next message: Abraham Buckingham: "Re: JSH: That's it"
- Previous message: Lefty: "Re: JSH: That's it"
- In reply to: jstevh_at_msn.com: "Re: Surrogate factoring, surprising result"
- Next in thread: jstevh_at_msn.com: "Re: Surrogate factoring, surprising result"
- Reply: jstevh_at_msn.com: "Re: Surrogate factoring, surprising result"
- Messages sorted by: [ date ] [ thread ]
Date: Sat, 5 Mar 2005 22:10:12 -0500
[JSH]
[...]
>> It looks like this IS the real result. And you only need to factor
>> T, and not even bother with T^2, so it's very simple.
>>
>> I still keep thinking I must be missing something...
Probably, alas.
[JSH]
> Well there are some minor details, like I tried a factorization:
>
> M = 77, with j = 75, which gives
>
> T = 304 = 16(19)
>
> and I find the factorization with f_1 = -8, which gives
>
> r = -7
I'm not clear on what your algorithm is now. Is this it?
Given odd composite M not the square of a prime:
1. Pick an odd j in 1..M-1.
2. T = M^2 - j^2.
3. For each integer f (positive or negative) dividing T,
compute g = gcd(f+1, M). Report that g is a factor if
1 < g < M (gcd in my universe always returns a non-negative
result, so in your example above my gcd(-8+1, 77) = 7 and
reports success).
Right? Wrong?
> while the second
"The second" what? Perhaps this means that M=7*11, and you found 7 above,
so that 11 is "the second" prime factor of M?
> reveals an issue with my technique as 11-1 = 10, but j
> blocks that, and 11+1 = 12, so j blocks that as it has 15 as a factor.
>
> So if f_1 + 1 shares a prime factor with j *and* f_1 - 1 does as well,
> then that factor will be blocked.
>
> The math here is amazingly simple. It's amazing that it could be this
> easy.
>
> Just this little formula
>
> Az = (j^2(r+1) - T/(r-1))/r
>
> and the derivation is so basic.
>
> I wonder about that blocking, maybe it's significant if you have a j
> that has a lot of prime factors, as if somehow all the prime factors of
> M plus or minus one share primes with it then the factorization can be
> blocked.
If the algorithm above _is_ what you have in mind, here are the troublesome
<M, j> pairs with M < 1000 ("troublesome" means M is an odd composite not
the square of a prime, but the algorithm I gave above-- which may or may not
be what you have in mind --doesn't find a factor):
M j
--- ---
143 141
253 249
299 297
319 315
323 255
377 189
377 375
391 243
403 399
437 219
437 285
437 429
437 435
451 447
481 477
527 459
527 525
533 255
551 3
551 543
559 117
559 507
559 555
589 117
589 255
589 453
589 585
649 645
667 39
667 129
667 561
667 567
667 651
697 309
697 459
703 141
703 429
703 681
703 699
713 129
713 261
713 285
713 291
713 315
713 429
713 549
713 555
713 675
713 699
731 663
731 729
767 765
779 57
779 87
779 195
779 777
803 561
803 801
817 315
817 741
817 771
851 153
851 177
851 285
851 687
851 825
871 195
871 435
893 1
893 201
893 345
893 825
893 891
899 105
899 183
899 303
899 513
899 567
899 603
899 615
899 693
899 825
899 873
899 897
901 833
913 909
923 819
923 921
943 171
943 375
943 405
943 549
943 651
943 939
949 945
979 975
989 15
989 147
989 273
989 315
989 423
989 567
989 825
989 897
989 927
989 975
For M = 112554401 * 221667653, the same implementation has so far tried all
odd j in 1 through 5257 without finding a factor.
Across 1000 products of two randomly chosen 20-bit primes, and always using
j=1, no factors were found.
- Next message: Abraham Buckingham: "Re: JSH: That's it"
- Previous message: Lefty: "Re: JSH: That's it"
- In reply to: jstevh_at_msn.com: "Re: Surrogate factoring, surprising result"
- Next in thread: jstevh_at_msn.com: "Re: Surrogate factoring, surprising result"
- Reply: jstevh_at_msn.com: "Re: Surrogate factoring, surprising result"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
