Re: Factoring problem and the SFT

[Rick Decker]
[...]
> Now if we knew A = p * q was the product of two distinct
> primes and if we had no reason to assume anything about
> some set of N numbers, then we would expect N/p of them
> to be divisible by p, N/q to be divisible by q, and
> N/pq to be divisible by both p and q. So we'd expect
>
> N/p + N/q - N/pq
>
> useful factors.

Sheesh: you and Nora _both_ lying to James about this, week after week. No
wonder he calls Nora "a liar" and you "lying scum" <wink>.

Each integer divisible by both p and q was counted once in N/p, and again in
N/q, so you need to subtract 2N/pq to get the count of integers divisible by
p or q but not both. The result holds exactly then if the universe from
which we choose consists of a contiguous range of exactly iN integers (for
some non-negative integer i).

Note that this favors James, because it lowers the chance of winning by luck
(i.e., makes random-gcd easier to beat). The difference becomes negligible
as min(p, q) increases, but all SFT-ish algorithms to date have done so
poorly that nobody ever gets to RSA-sized p and q before giving up (e.g., in
the last round of this stuff, I never went beyond testing products of pairs
of 20-bit primes, and toward the end cut that to 15-bit primes as the
algorithms got ever more expensive to try).

BTW, I'd be happy to test SFT with that framework too, except James has
never given an actual algorithm for this one. I'm not going try to picking
arbitrary rationals out of thin air at the end. If looking (just) "at all
integer factors of B^2(A^2 - B^2)" would satisfy James, that would be
non-insane enough to test.

> ... If this held in general, it would mean that SFT would yield useful
> results at a rate NO BETTER THAN RANDOM CHOICE.
>
> I've tried enough examples to be mostly convinced
> that's just what happens with your theorem.

Having tested some dozen of these before, and seeing nothing essentially new
in this one, I'm almost entirely sure of that outcome.

> If it is, then you're in deep doo-doo when you attempt
> to factor a big A: if A = pq and p and q are hundred-digit
> primes, that would give you about a 2 in 10^100 chance
> that one of your choices of g_1 and g_2 would lead
> to a useful factorization of A. I wouldn't hold my breath.

Exactly so, but JSH can't believe it. He "believes in the math, and math
doesn't lie" -- which in this case is an absurd argument about infinite
sets:

The set of all integers divisible by 101 is (countably) infinite.
The set of all integers not divisible by 101 is (countably) infinite.
Therefore half of all integers are divisible by 101.

I don't believe he understands enough set theory to recognize that this _is_
his argument, so with a bit of luck I'll rate "lying scum" too for pointing
out that it is (he doesn't appear to know that there's a bijection between
_any_ two countably infinite sets, and spaced out when that was explained
before).


.

Relevant Pages