Re: A factoring algorithm

<wbhart@sbcglobal.net> writes:
> I've been trying to post a reply to the group for a couple of days,
> but google groups appears to not work with this group.

There's a lesson to be learnt from that.
 
> Just to summarise, those who pointed out that my algorithm is of no
> cryptographic interest are of course correct. Any extremely sparse
> class is easy to factor because it is sparse. No need to adjust RSA.
> But then again, what classes of special numbers DO need to be filtered
> these days. They are all sparse aren't they, compared to 200 digit
> moduli? Well I wouldn't know, I'm a pure mathematician, not a
> crytographer.

The cost of checking for a few sparse forms is very low. However,
the risk is utterly minimal. So the value for money, so to speak,
of such checks is fairly close to zero.
 
> The main interest in my algorithm, if any, is that it factors enormous
> numbers (albeit of a kind which could easily be factored some other
> way), but without being a contrived algorithm. For example, the
> algorithm suggested by the other posters of writing the number out in
> base b and trying the small number of possible factors, will not factor
> general numbers....well, not really.

That suggestion I made is remarkably similar to how Fermat's method
works. Effectively you assume it satisfies a simple polynomial form,
and try to search for solutions by brute force.

> In answer to another poster, the base b in my algorithm must be the
> same for both primes, but a and c can vary. The n's probably want
> to be close to the same, but other incarnations of my algorithm will
> allow more flexibility there, up to a point.
>
> My algorithm in its most simple form will factor general numbers in
> time O(n^(1/3)). A heuristic improvement will speed that up to
> O(n^(1/4))... so far. I don't think it competes well with SQUFOF (and I
> can't recall if SQUFOF is O(n^(1/5)) anyhow). One can also apply some
> standard tricks to my algorithm to make it subexponential, though it
> doesn't sieve, so it is only about as good as the continued fraction
> algorithm and appears to lose all its special powers (I think).

This is curious. I really would liketo see some more concrete
figures regarding the work-factor at various sizes - actual
atomic operation counts. A comparison with SQUFOF is again
curious - noone really uses SQUFOF over aboout 25-30 digits, due
to how unpleasant its Big-Oh gets. And yet you mention that you
are factoring large numbers. It seems as if most of the terms
in your Big-Oh expression must be artificially decreased due to
the special form of the numbers you use. i.e. not 'n', the number
being factored, as you hae above.

> But as noted by the above poster, the interest in new factoring
> algorithms is not necessarily in what they will factor, but in the
> methods they use. In my case, there is only one new idea, which has
> probably been tried by numerous others and overlooked. The only reason
> I noticed it was that I had been customarily using numbers of the form
> nextprime(10^n)*nextprime(10^(n+2)) to calibrate my factoring software.
> I was suddenly shocked one day when an algorithm of mine that I was
> fiddling with, suddenly began factoring numbers of many thousands of
> digits almost instantly. After some work I determined the exact form of
> the numbers that the naieve algorithm would factor quickly.
>
> Since then I have been unable to determine the exact form of the
> various other numbers it will factor quickly, in the other incarnations
> of the algorithm that I have. I'm a research mathematician and know not
> to expect that overnight. More may come of it, but that is all for now.
> Obviously since it is the subject of ongoing research I'm not prepared
> to say much more about it at this point. It's only early stages. I may
> get a paper out of it in a wayward journal, or you never know,
> something interesting might turn up.
>
> I've been spending more of my time working on something of
> greater interest (to me at least). I've been implementing the
> quadratic sieve. So far my code is faster at factoring 60 digit
> numbers than the MPQS implementation in the number theory
> package (due to various people, but most recently maintained
> by Gerhard Nicklasch who apparently works for Sun) called
> Pari.

What version of Pari. Pari's QS has undergone several revisions
over the last few years.

> But unlike Pari, there are some major tricks that I do not use.
> For example I don't self initialise, don't use a large prime
> variation and don't use block Lanczos. There are still two major
> tricks I haven't applied that I can think of other than those. It is
> still slower for 70 digit and higher numbers so far though, by a factor
> of two.
>
> At the present moment I have some questions about how to
> make large prime variations work. I can find no regime in which it will
> cause a significant speedup of the code I am using and am rather
> curious as to why that might be.

The implementation to compare against is Jason Papadopoulos' msieve.
It's not just exceptionally fast, even up to 90+ digits, but also
exceptionally clearly written. (As long as you're familiar with
techniques for being cache-friendly.)

Do keep us posted. There are a fair number of mathematicians here
who have an active interest in factoring algorithms.

Phil

-- 
What is it: is man only a blunder of God, or God only a blunder of man?
-- Friedrich Nietzsche (1844-1900), The Twilight of the Gods