Re: Surrogate factoring approach, analysis

jstevh at msn.com

Bryan Olson

From:	jstevh at msn.com
Subject:	Re: Surrogate factoring approach, analysis
Date:	20 Jan 2005 17:59:27 -0800

Bryan Olson wrote:
> jstevh@msn.com wrote:
> [...]
> > I suspect you're just another Usenet poster without a clue who
wishes
> > to broadcast that to the world.
>
> I'm also the Usenet poster to whom you wrote:
>
> | Yup. You were *exactly* right Bryan, and I want to thank
> | you for noticing that and for repeatedly pointing it out.
>
> (Admittedly, that was not your last word on the subject.)
>
> Here, I wrote about your algorithm and about interpreting your
> program's results. Why do you insist on making personal attacks?
>

I'm attacking your knowledge, or lack of it.

You seem to have no clue about what the actual odds for the factorings
are, but you're talking as if you do.

I assure you that you are quite wrong, and that even the factorizations
I gave are well beyond chance.

You stated otherwise.

To you this is probably some joke, or some nothing.

But I'm a researcher who sees people like you way too often, people who
talk a lot, influence others, and act as if they know something when
they do not.

You are dangerous.

You see my pointing out your lack of knowledge as a personal attack,
but factoring is an important problem in this world.

Yet here you are, talking outside of your knowledge level in a way that
might influence others, and the harm you can do is far more than you
seem willing to imagine.

After all, this research can be furthered by others. But if enough
people like you downplay it, then the world will not pay attention
until it's FORCED to pay attention, and do you know what might force
it?

A major cyber-attack, like something massive that finally forces people
to quit paying attention to nonsense, and then the world as we know it
will end.

You are dangerous, whether you realize it or not.

Your ignorance is dangerous.
Your confidence based on your ignorance is dangerous.

James Harris

From:	Bryan Olson
Subject:	Re: Surrogate factoring approach, analysis
Date:	Sat, 22 Jan 2005 04:16:45 GMT

jstevh@msn.com wrote:

> You seem to have no clue about what the actual odds for the factorings
> are, but you're talking as if you do.

Well, for trial GCD, the chance that two large random
(independent) odd integers share a non-trivial common factor is:

1 - 8/(Pi**2).

In truth, I didn't know it, but I knew I had known it and I knew
it approximately and I knew where to look it up. Whether I knew
how to re-derive it, I don't now know. (It's exercise 13, section
4.5.2, Knuth vol 2.)

[...]
> You see my pointing out your lack of knowledge as a personal attack,
> but factoring is an important problem in this world.

I've previously suggested Pollard's 'rho' algorithm as a
benchmark for interesting-ness of factoring algorithms.
Factoring slower than Pollard rho is silliness. A faster
algorithm, unless a trivial variation of some existing method,
is worth posting.

Pollard's rho, though much faster than trial division, is
exponential time. To find factors, it essentially ues trial-
GCD, but with a clever trick to guide the search. Below is a
simple implementation and quick demo of Pollard's factoring
method in the Python language. (Python is free software; see
www.python.org.)

--Bryan

def gcd(x, y):
""" Return the greatest common divisor of x and y.
"""
while x > 0:
x, y = y % x, x
return y

def pollard_split(n):
""" Pass a positive composite. Returns a non-trivial factor.
"""
if n % 2 == 0:
return 2
increment = 1
while increment < n:
a, b = 2L, 2L
d = 1
while d == 1:
a = (a * a + increment) % n
b = (b * b + increment) % n
b = (b * b + increment) % n
d = gcd(abs(a - b), n)
if d < n:
return d
increment += 2
assert 0, "Cannot factor %d" % n

jhfail = [
2348221831L, 3172590413L, 2514657533, 2335689907L,
2095611269L, 135247262314741L, 239937525733091L,
119059652313451L, 177805283351779L, 140979690859369L,
156432070838873L, 84697211728937L, 151766760236149L,
137083650684517L]

for n in jhfail:
f = pollard_split(n)
assert n % f == 0
print n, '=', f, '*', n / f