Re: Surrogate factoring and the k/T ratio
- From: rossum <rossum48@xxxxxxxxxxxx>
- Date: Thu, 01 Mar 2007 12:58:50 +0000
On 28 Feb 2007 21:22:13 -0800, jstevh@xxxxxxxxx wrote:
Readers wanting to see my examples can go to my math blog or toI looked at your example:
and see the theory and an example.
JSH> T = 2066147, k = 68873, [a-b] = -2, x=334429/2, y=-430137/2
JSH> x+y=-47854, which has 337 as a factor, and T = ( 337 )( 6131 )
JSH> Surrogate: 9482847964 = (2^2)( 43^2 )( 61 )( 21019 )
JSH> To get that example I multiplied a 3 digit prime times a 4
JSH> digit prime, and started with k = floor(T/30), which gives
JSH> 68871, which didn't work, but incrementing twice gives a k
JSH> that does.
JSH> So by factoring the surrogate I obtained a factorization of
JSH> the target composite.
This example is not the method you posted on this newsgroup. In your
OP of this thread you talked about using "a k that was about 20% of
T", i.e. k = floor(T/5) and a-b = -1. In your example you are using k
= floor(T/30) and a-b = -2, which is a different version of your
method. For a true comparison you need to stick to the same version
Analysing your example we start with k = 68871 which gives a surrogate
of S = 9482296988. There are twelve possible pairs of positive
factors of 9482296988: (1, 9482296988), (2, 4741148494), (4,
2370574247), (31, 305880548), (62, 152940274), (124, 76470137), (599,
15830212), (1198, 7915106), (2396, 3957553), (18569, 510652), (37138,
255326), (74276, 127663) and a further twelve pairs of negative
factors, (-1, -9482296988) etc. Each of the 24 pairs of factors can
be used to calculate x and y and both x and y have to be tried to see
if a factor can be found. So we will have had 48 attempts at
factoring, without success.
Incrementing k to 68872 gives S = 9482572474. This has four possible
positive factor pairs: (1, 9482572474), (2, 4741286237), (149,
63641426), (298, 31820713) for a further 16 unsuccessful factoring
attempts. Total so far 48 + 16 = 64 unsuccessful factoring attempts.
Incrementing k to 68873 gives S = 9482847964 as you say. This has
eighteen possible positive factor pairs: (1, 9482847964), (2,
4741423982), (4, 2370711991), (43, 220531348), (61, 155456524), (86,
110265674), (122, 77728262), (172, 55132837), (244, 38864131), (1849,
5128636), (2623, 3615268), (3698, 2564318), (5246, 1807634), (7396,
1282159), (10492, 903817), (21019, 451156), (42038, 225578), (84076,
112789) for up to 72 factoring attempts, one of which will be
successful. Since you do not specify which order to try factor pairs
I cannot be more detailed.
Your example requires between 65 and 136 attempts in order to produce
one factor. It tries three possible values of k. Each different
value of k will generally produce multiple values of x and y and hence
multiple attempts to find a factor.
I tried your different version (k = floor(T/30), a-b = -2) in my test
Fermat average = 7.804 probes.
JSH average = 2055.03 probes.
Probe ratio = 1 : 263.331
Trial average = 119.602 probes.
Random average = 372.076 probes.
500 tries, 0 misfactors found.
Average k's tried per factorisation: 15.874
These results are slightly worse those I posted earlier. They tend to
suggest that k = floor(T/30), a-b = -2 is worse than k = floor(T/5),
a-b = -1.
Your Surrogate method does find factors, but it finds them more slowly
than existing methods. This has been consistent across all the
versions of your method I have tested. Your problem is not finding
factors - your method does that part successfully. Your problem is
that your method is slower than existing methods.
- Prev by Date: Re: disc erasure
- Next by Date: Re: disc erasure
- Previous by thread: Re: Surrogate factoring and the k/T ratio
- Next by thread: Re: Surrogate factoring and the k/T ratio