Re: Proof factoring solution is closed form

From: Décio Luiz Gazzoni Filho (decio_at_decpp.removethis.net)
Date: 02/11/05 

Date: Fri, 11 Feb 2005 12:59:50 -0200

Tim Peters wrote:

> [Nora Baron, to JSH]
> [...]
>> Whether your approach to factoring leads to anything remains to
>> be seen. You replace factoring a large number M with factoring of
>> a number T = M^2 - j^2, where in general you might choose j to be
>> relatively small. There are two possibilities regarding T which
>> need to be considered. One is that it has two or more extremely
>> large prime factors, very possibly with almost twice the digit-length
>> of the factors of M itself.
>
> M^2-j^2 = (M+j)*(M-j), so nothing as large as 2*M remains to be factored
> in
> T. Pick any odd j, 0 < j < M, and both halves are even, and the largest
> remaining piece (after dividing out 2s) is smaller than M. Pick an even j
> s.t. M+j and M-j are both prime (a strong argument was made by Décio Luiz
> Gazzoni Filho that this can probably be done efficiently),

Actually I found what appears to be an even more efficient way to pick
those. The idea is that M mod p, for small p, is never 0 because otherwise
it'd be divisible by p. As you pointed out, j must be even, and since
neither of M - j, M, M + j can divide 3, then j must be a multiple of 3 as
well, i.e. j = 2*3*k for some integer k. I took the idea further -- why not
have j = 2*3*5*7*...*maxp*k? A restriction is that maxp < log M, because
log(2*3*5*7*...*maxp) ~ maxp. Now, in this construction, M - j == M == M +
j mod 2, 3, 5, 7, ... up to the bound you choose. Thus you automatically
prevent both M - j and M + j to be divisible by these small primes, and
Mertens' theorem allows to quantify this gain. A concrete example, with
RSA1024 and all primes up to 1000 would suggest that, individually, each of
M - j and M + j is 4.1 times more likely to be prime than other candidates
of the same size (already taking into account that candidates must have j =
6k). Then use a sieve to further remove invalid values of k, and PRP-test
what remains once that sieve is taking too long to remove further
candidates.

I didn't implement this, because I'm busy implementing the previous sieve in
C, but anyone is welcome to try.

Décio

Relevant Pages

  • Re: Proof factoring solution is closed form
    ... >> Whether your approach to factoring leads to anything remains to ... RSA1024 and all primes up to 1000 would suggest that, individually, each of ... M - j and M + j is 4.1 times more likely to be prime than other candidates ... Then use a sieve to further remove invalid values of k, ...
    (sci.math)
  • msieve is FAST!!
    ... intialising quadratic sieve for factoring numbers, ... the sieve size critical in terms of fitting everything into the processor ... small selection of the primes at once. ... that data in the cache at once. ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.crypt)
  • Re: JSH: Contradictory behavior, issue of math fraud
    ... But if the idea turns out to be a brilliant one which means factoring ... No one has said math journals routinely publish ... current methods in speed for counting primes. ... about being a genius. ...
    (sci.math)
Quantcast