Re: A factoring algorithm

"Pubkeybreaker" <Robert_silverman@raytheon.com> wrote in message
news:1136815553.973692.199870@g44g2000cwa.googlegroups.com...

> Your post lacks specifics. Define "small"

Oh, "small", yes, I forgot to define that. As in time is at least
exponential in "small". Four or five digits if you only have time for a
quick coffee.

Actually, I'll be completely honest here. I had noooo idea of who posted to
sci.crypt. It's a newsgroup right, so you don't expect much.

So I purposely worded my original post to sound like a crank - "small", "new
algorithm", "fast". I expected the usual response:

"yeah, well if you have such an algorithm, factor this {insert 2000 digit
number of the form I specified, here}",

at which point I would promptly supply them with the factors. That may have
worked on sci.math.

Unfortunately I would have been better off sticking to my original plan,
which was to make the algorithm available publicly on the number theory list
on April 1st with some suggested 1000-2000 digit numbers to try factoring
with it.

OK, so I have a warped sense of humour.

The algorithm does exist, and may or may not lead to something. The original
question I asked was genuine, if misguided, but I admit, the wording of the
original post was purposely trollish. It was my intention to have a bit of a
laugh (obviously some people would understand the joke immediately) at the
same time as ask a serious question of those who did know something.
Unfortunately I only got the latter. Doh!

Just so you don't feel too upset, I am a number theorist who works in
Iwasawa theory, Modular forms and various related things. Factoring is only
a hobby for me. My last newsgroup posting before the original one here, was
probably a couple of years ago. I HAD given up. I don't recall ever posting
about a factoring algorithm or any other trollish topic in the past.
Hopefully you will forgive my one and only outburst.

Incidentally, on a more serious note, I would be quite interested to hear
about any non-contrived algorithms which factor numbers in sparse classes
very fast. I know about the SNFS and Zhang's sieve, Pollard-Brent, p-1,
William's p+1 (perhaps you'd include ECM), all of which it could be argued,
have this property. I suppose many other algorithms also factor certain
numbers very fast (with the exception of the general sieves), but it may not
be the case that one knows explicitly what the class is, except in the case
of Fermat's algorithm, where the "class" isn't an interesting one. I'm
interested primarily in non-contrived algorithms where the class is actually
known.

So, if there are others, I'd find that a worthwhile topic of conversation,
and perhaps dignified enough for a newsgroup such as this one. Obviously
such algorithms aren't going to have any practical benefit unless they
factor a positive proportion of all numbers quickly, but they are still of
interest to me for theoretical reasons, and for study.

Many algorithms have never seen the light of day because they are not better
than the current best algorithms at the time. For example, Lenstra once told
me about an algorithm which would factor any number in a polynomial number
of arithmetic operations (not due to him BTW AFAIK - and for those who don't
know, I'm not trolling - think carefully about the statement - there's an
obvious catch). Admittedly, that algorithm wasn't really of interest, since
it was quite contrived, and of no practical use, however there must be
others which people can describe which at least have theoretical interest.

Bill.
Received on Tue Jan 17 16:49:21 2006