Re: Surrogate factoring and the k/T ratio

On 28 Feb 2007 21:22:13 -0800, jstevh@xxxxxxxxx wrote:

Readers wanting to see my examples can go to my math blog or to

http://groups.google.com/group/extrememathematics/web/surrogate-factoring

and see the theory and an example.
I looked at your example:

JSH> 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> f_1=21019/2
JSH> f_2=225578

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
for consistency.

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
program:

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.

rossum

.

Relevant Pages

  • Re: Surrogate factoring and the k/T ratio
    ... JSH> To get that example I multiplied a 3 digit prime times a 4 ... factoring, without success. ... multiple attempts to find a factor. ...
    (sci.crypt)
  • Re: Surrogate factoring and the k/T ratio
    ... JSH> To get that example I multiplied a 3 digit prime times a 4 ... JSH> the target composite. ... factoring, without success. ...
    (sci.crypt)
  • Re: JSH: What is surrogate factoring? Once more.
    ... Sieve as well as James' method. ... his surrogate factoring method rarely results ... Assume given a friendly number k from JSH. ... might also fail to produce a factor of T if k is a multiple ...
    (sci.math)
  • Re: Surrogate factoring and the k/T ratio
    ... JSH> To get that example I multiplied a 3 digit prime times a 4 ... factoring, without success. ... multiple attempts to find a factor. ...
    (sci.crypt)
  • Re: JSH: Latest factoring idea is crap
    ... is good enough for top mathematicians, he's got no reason to try to make it ... Since he's attracted to messy methods involving multiple free choices, ... factoring 35 and show him that it didn't find a factor after all. ... Subject: JSH: Now what? ...
    (sci.math)