Re: Surrogate factoring, surprising result

jstevh_at_msn.com
Date: 03/06/05 

Date: 6 Mar 2005 05:20:28 -0800

Tim Peters wrote:
> [...]
>
> [Tim Peters]
> >> I'm not clear on what your algorithm is now. Is this it?
> >>
> >> Given odd composite M not the square of a prime:
> >>
> >> 1. Pick an odd j in 1..M-1.
> >>
> >> 2. T = M^2 - j^2.
> >>
> >> 3. For each integer f (positive or negative) dividing T,
> >> compute g = gcd(f+1, M). Report that g is a factor if
> >> 1 < g < M (gcd in my universe always returns a non-negative
> >> result, so in your example above my gcd(-8+1, 77) = 7 and
> >> reports success).
> >>
> >> Right? Wrong?
>
> [JSH]
> > That is the basic algorithm, but in any case where f_1 +/- 1 shares
a
> > prime factor with j then the factorization is blocked.
>
> As I said, I tried 1000 products of random 20-bit primes, all with
j=1, and
> none factored. It's obvious that nothing can share a prime factor
with j=1,
> right?
>
> > Solution? Factor Tj^2, and the problem goes away.
>
> As above: factoring Tj^2 is the same as factoring T when j=1. The
smallest
> M that didn't factor at j=1 is 893, as was shown in the table in my
original
> post. Details:
>
> M = 893 = 19 * 47
> j = 1
> T = Tj^2 = M**2 - j**2 = 797448
>

Well, it's simpler now to go back to the derivation to see what's going
on.

Starting at

(r^2 - r)Az = r^2 j^2 - M^2

(r - 1)Az = r j^2 - M^2/r

let r = 19, then

18 Az = 19 - 41971

so Az = -6992/3

so for some reason 3 is still a blocking prime.

Trying r = -19, gives

-20 Az = -19 + 41971

so Az = -10488/5

and this time it's 5.

Well, looks like it's time for more theory.

I have

(r - 1)Az = r j^2 - M^2/r

but it's possible to prove that an integer Az that has a single prime
factor of M must exist, so let's go find that integer Az.

x = z(-Az +/- sqrt((Az - 2M^2)^2 - 4TM^2))/(2j^2 - 2Az)

and focusing on the square root I have

sqrt((Az - 2(893^2))^2 - 4(797448)(893)^2)

and I want Az to have 19 as a factor, so dividing through by 19, I get

sqrt((Az/19 - 2(19)(47^2))^2 - 4(797448)(47)^2)

and a solution should be given by

Az/19 = 33227 + 53016 + 2(19)(47^2) = 170185

and checking

sqrt((170185 - 2(19)(47^2))^2 - 4(797448)(47)^2) = 19789

so I have that

Az = 19(170185)

now using

(r^2 - r)(19)(170185) = r^2 - 797449

which is

3233514 r^2 - 3233515 r + 797449 = 0

so

r = ( 3233515 +/- sqrt((3233515)^2 - 4(3233514)(797449))/2(197889)

r = (3233515 +/- 375991)/2(197889)

r = 1804753/197889 = ( 19 )( 43 )( 47^2 )/( 3 )( 65963 )

or

r = 1428762/197889 = ( 2 )( 3 )( 19 )( 83 )( 151 )/( 3 )( 65963 )

so both are fractions, which explains why that particular solution
didn't come up.

That means my assumption about r being an integer is the one that's
suspect.

Looking at

Az = (j^2(r + 1) - T/(r-1))/r

with r a fraction, letting r = n/d, gives

Az = (j^2(n + d) - d^2 T/(n-d))/n

where n is still a factor of M, but there's that d, which may mean I
jumped the gun yet again.

Looking at

(r - 1)Az = r j^2 - M^2/r

the issue has to do with prime factors of r-1 where r-1 is a factor of
M, so that's not good.

Oh well, time to do more research...

James Harris

Relevant Pages

  • Re: Surrogate factoring, surprising result
    ... Tim Peters wrote: ... >> prime factor with j then the factorization is blocked. ... so both are fractions, which explains why that particular solution ... the issue has to do with prime factors of r-1 where r-1 is a factor of ...
    (sci.math)
  • Re: Basically a sieve method, relation to quantum
    ... Tim Peters wrote: ... >> odd numbers until the square root). ... However, I didn't get 100% factorization which I assumed I would get, ...
    (sci.crypt)
  • Re: Simple answer, surrogate factoring
    ... Tim Peters wrote: ... and I need 169A to be an integer, so I need the factorization of ... Plugging in 6972, gives ... so you screwed up somewhere as 169is an integer solution for Ax. ...
    (sci.crypt)
  • Re: Simple answer, surrogate factoring
    ... Tim Peters wrote: ... and I need 169A to be an integer, so I need the factorization of ... Plugging in 6972, gives ... so you screwed up somewhere as 169is an integer solution for Ax. ...
    (sci.math)