Re: surrogate factoring


Tim Peters wrote:
[gjedwards@xxxxxxxxx]
A previous poster was right - having anything to do with JH's posts is
like rubbernecking a traffic accident. Sad but difficult to resist.
Anyway ...

The bit I don't get (well one of the bits) is what specifically JH
*thinks* is the point of surrogate factoring. I know it's total
nonsense but does anyone have a clue *why* he thinks it's worthwhile? I
guess I find the nature of the delusion somewhat puzzling and it's an
amusing diversion to work out what he actually thinks.

I really should get out more.

Me too, but so long as we're both house-ridden today, and I've enjoyed more
quality "SF time" than anyone other than James ...

First, "surrogate factoring" doesn't really mean anything specific. There
are literally dozens of distinct methods James has _called_ "surrogate
factoring" over the past two years. While they've all been wrong (in the
sense that none have been efficient factoring methods, and for some it was a
miracle if they ever found a factor), "total nonsense" is either
overstatement or understatement :-)

The general idea is that you want to factor T, but factor some "related"
integer S ("the surrogate") instead and hope to relate the factors of S to
T's factors. That's perfectly sensible so far as it goes. [...]

As a digression, I'll repost what I considered a useful offshoot of
this idea:

Suppose you know T, and you know that T = p * q, where p and q are
distinct (maybe odd) primes, and you want to find p and/or q. Now
suppose you have an integer which factors the same way; i.e., as the
product of two distinct (maybe odd) primes; thus:

S = p' * q'.

(I wanted to avoid S = r * s here.) Now, IF you can find a function f:
Z -> Z such that
f(p') = p and f(q') = q, without using the specific values of p and
q, then the factors of S will map to the factors of T.

This, of course, appears to be impossible, but seemed the only viable
approach to anything which can properly be called "surrogate
factoring".

You could also extend the idea by supposing you know how T factors,
perhaps as

T = p^2 * q * r^3,

where p, q, and r are all distinct primes (possibly with p < q < r),
construct a function f, using the fact that

15435 = 3^2 * 5 * 7^3,

then calculate f(3), f(5), and f(7), to get p, q, and r.

And if you can get _that_ to work, well, you're on your way to
Milliways!

--- Christopher Heckman

.

Relevant Pages

  • Reality check, surrogate factoring
    ... Surrogate factoring is meant to beat the tactic of picking two hard ... and it will be really big for a big target. ... of the time for rationals x's. ...
    (sci.math)
  • Reality check, surrogate factoring
    ... Surrogate factoring is meant to beat the tactic of picking two hard ... and it will be really big for a big target. ... of the time for rationals x's. ...
    (sci.crypt)
  • Re: JSH: Surrogate factoring, periodic behavior
    ... That is the primary decision relation that determines if a surrogate ... Remember the surrogate factorization involves factoring a target ... as human curiosity is such a wonderful thing. ... You are the cruel jocks picking on the kid you call nothing. ...
    (sci.math)
  • Re: Surrogate factoring explained
    ... as the way it works is you get two primes ... > from the hard target to an easier surrogate, which is factored, and its ... > factors are then used to factor the target. ... so surrogate factoring is still mostly a theoretical concept. ...
    (sci.math)
  • Re: Surrogate factoring explained
    ... as the way it works is you get two primes ... > from the hard target to an easier surrogate, which is factored, and its ... > factors are then used to factor the target. ... so surrogate factoring is still mostly a theoretical concept. ...
    (sci.crypt)
Loading