Re: A factoring algorithm

Joseph Ashwood wrote:
> <hart_wb@yahoo.com> wrote in message
> news:1136613824.569396.118650@o13g2000cwo.googlegroups.com...
> > I have a new factoring algorithm which seems to be very fast with
> > certain kinds of numbers.
>
> Any advances, or even new paths in factoring is always a welcome advance. If
> your algorithm is as fast as you say, it is likely that new qualifications
> may need to be created for RSA keys, this is a well established area of
> advancement, and will be appreciated. Even if it results in triviality as
> Amling and Carmody have said the knowledge the an additional avenue is
> available is often very useful.
> Joe

Hi,

thanks for the kind words.

I've been trying today to post a reply to the group, but google groups
seems to have lost the posts I made.

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 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.

In answer to another poster (since my postings through this service are
limited), 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).

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.

People here might be more interested in my implementation of the
quadratic sieve which is faster at factoring 60 digit numbers than
Pari, and yet doesn't self initialise, doesn't use a large prime
variation and doesn'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.

If there is anyone here interested in that subject, please email me
(hart_wbATyahoo.com.nospamplease). 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.

As for my wierd algorithm, the subject is dead for now. Not the least
reason for which is that I simply don't have reliable free newsgroup
access with my expensive broadband internet connection.

Anyhow, wow! I didn't realise JSH posted on here too. And he is still
carrying on about his factoring "algorithm". He's had half the PhD's on
the planet trying to perceive what all those polynomials actually mean
at one point or another, for almost 12 years now, IIRC. Little did I
know I would be posting my own rantings about a factoring algorithm on
the same group as him all these years later. I feel somehow honoured to
be in the good company of such crankery.

I did start thinking about a factoring algorithm that used a group of
2x2 matrices the other day. That led me to think about one involving a
group of polynomials. But nothing has come of it yet. It's a shame JSH
has never taught himself something other than high school arithmetic. I
can only spend small amounts of time here and there on my factoring
hobby. He has all the time in the world. Of course he'd have to take
his meds.

Till later.

Bill Hart.
Received on Tue Jan 17 16:49:03 2006