Re: JSH: Surrogate factoring, periodic behavior

On Sun, 02 Sep 2007 00:03:28 -0000, JSH <jstevh@xxxxxxxxx> wrote:

Here is output from my program and a run I just did testing out some
new theory.

Here for various reasons I won't explain I'm using k=30, starting with
n=1, and there is a lot wrong with this example from my standpoint as
by my theory I don't think it should have factored at this point.

java Factor 34587541
I wrote an instrumented version of my program and tried it with your
inputs. It factored the target with 160 probes:

target = 34587541
k = 30

trying n = 1, surrogate = 34589341
trying factor pair: (1, 34589341)
1 failed. -1 failed. 34589341 failed. -34589341 failed.
trying factor pair: (463, 74707)
463 failed. -463 failed. 74707 failed. -74707 failed.

trying n = 2, surrogate = 69176882
trying factor pair: (1, 69176882)
1 failed. -1 failed. 69176882 failed. -69176882 failed.
trying factor pair: (2, 34588441)
2 failed. -2 failed. 34588441 failed. -34588441 failed.

trying n = 3, surrogate = 103764423
trying factor pair: (1, 103764423)
1 failed. -1 failed. 103764423 failed. -103764423 failed.
trying factor pair: (3, 34588141)
3 failed. -3 failed. 34588141 failed. -34588141 failed.
trying factor pair: (7, 14823489)
7 failed. -7 failed. 14823489 failed. -14823489 failed.
trying factor pair: (21, 4941163)
21 failed. -21 failed. 4941163 failed. -4941163 failed.

trying n = 4, surrogate = 138351964
trying factor pair: (1, 138351964)
1 failed. -1 failed. 138351964 failed. -138351964 failed.
trying factor pair: (2, 69175982)
2 failed. -2 failed. 69175982 failed. -69175982 failed.
trying factor pair: (4, 34587991)
4 failed. -4 failed. 34587991 failed. -34587991 failed.
trying factor pair: (179, 772916)
179 failed. -179 failed. 772916 failed. -772916 failed.
trying factor pair: (199, 695236)
199 failed. -199 failed. 695236 failed. -695236 failed.
trying factor pair: (358, 386458)
358 failed. -358 failed. 386458 failed. -386458 failed.
trying factor pair: (398, 347618)
398 failed. -398 failed. 347618 failed. -347618 failed.
trying factor pair: (716, 193229)
716 failed. -716 failed. 193229 failed. -193229 failed.
trying factor pair: (796, 173809)
796 failed. -796 failed. 173809 failed. -173809 failed.
trying factor pair: (971, 142484)
971 failed. -971 failed. 142484 failed. -142484 failed.
trying factor pair: (1942, 71242)
1942 failed. -1942 failed. 71242 failed. -71242 failed.
trying factor pair: (3884, 35621)
3884 failed. -3884 failed. 35621 failed. -35621 failed.

trying n = 5, surrogate = 172939505
trying factor pair: (1, 172939505)
1 failed. -1 failed. 172939505 failed. -172939505 failed.
trying factor pair: (5, 34587901)
5 failed. -5 failed. 34587901 failed. -34587901 failed.
trying factor pair: (4583, 37735)
4583 failed. -4583 failed. 37735 failed. -37735 failed.
trying factor pair: (7547, 22915)
7547 failed. -7547 failed. 22915 failed. -22915 failed.

trying n = 6, surrogate = 207527046
trying factor pair: (1, 207527046)
1 failed. -1 failed. 207527046 failed. -207527046 failed.
trying factor pair: (2, 103763523)
2 failed. -2 failed. 103763523 failed. -103763523 failed.
trying factor pair: (3, 69175682)
3 failed. -3 failed. 69175682 failed. -69175682 failed.
trying factor pair: (6, 34587841)
6 failed. -6 failed. 34587841 failed. -34587841 failed.
trying factor pair: (239, 868314)
239 failed. -239 failed. 868314 failed. -868314 failed.
trying factor pair: (478, 434157)
478 failed. -478 failed. 434157 failed. -434157 failed.
trying factor pair: (717, 289438)
717 failed. -717 failed. 289438 failed. -289438 failed.
trying factor pair: (1434, 144719)
1434 failed. -1434 failed. 144719 failed. -144719 failed.

trying n = 7, surrogate = 242114587
trying factor pair: (1, 242114587)
1 failed. -1 failed. 242114587 failed. -242114587 failed.
trying factor pair: (11, 22010417)
11 failed. -11 failed. 22010417 failed. -22010417 failed.
trying factor pair: (13, 18624199)
13 failed. -13 failed. 18624199 failed. -18624199 failed.
trying factor pair: (19, 12742873)
19 failed. -19 failed. 12742873 failed. -12742873 failed.
trying factor pair: (121, 2000947)
121 failed. -121 failed. 2000947 failed. -2000947 failed.
trying factor pair: (143, 1693109)
143 failed. -143 failed. 1693109 failed. -1693109 failed.
trying factor pair: (209, 1158443)
209 failed. -209 failed. 1158443 failed. -1158443 failed.
trying factor pair: (247, 980221)
247 failed. -247 failed. 980221 failed. BINGO! -980221 succeeded

factor = 307
34587541 = 307 * 112663
160 probes total.

Looking at things this way you can see that your method is repeatedly
trying 1, -1, 2 and -2 when they only need to be tried once each. For
example you could try all possible small factors of S from, say -10 to
10, at the start and then ignore them whenever they occur later. That
would remove repeats of those small factors - which is where repeats
are a problem.

Your current work on determining the best choices of k and n for a
given T is good. The more you can narrow down the allowed ranges of k
and n the fewer failed probes your method will have and the faster it
will run.

rossum

.

Relevant Pages

  • RE: Malformed DNS or something odd (or just me)
    ... There are several different similar types of probes, ... The second UDP port is identical for all probes to any target address. ... - The payloads of the packets generally have IP addresses embedded in them. ...
    (Incidents)
  • Re: Creating and using an array
    ... Sub CopyData(StartCell As Range, Target As Range) ... Bob Phillips ... I have a section of code which repeats with minimal changes (2 items per ...
    (microsoft.public.excel.programming)
  • Re: NTP, ntpdate, and ISP-based firewall
    ... >reply to probes at prohibited ports. ... >less of a target because I clearly have active security measures in place. ... how to use portsentry, iptables, and a simple shell script to totally ...
    (Fedora)
  • Re: Circus archive footage (circa 1955)
    ... target looks like she's about 5 or 6. ... The Void ... History never repeats, I tell myself before I go to sleep. ...
    (rec.juggling)