Research topics

[Robert Holmes]

What are some open areas of research in integer factorization today?

I'm nearing the end of my degree, and have an opportunity to pursue a PhD. Thus, I'm looking for some interesting topics. They don't have to be related to factorization necessarily, but that can be a starting point.

I have a mainly CS background, so I'd be more comfortable with computational aspects than pure mathematics.

What are your thoughts?

[R.D. Silverman]

Originally Posted by Robert Holmes

What are some open areas of research in integer factorization today?

I'm nearing the end of my degree, and have an opportunity to pursue a PhD. Thus, I'm looking for some interesting topics. They don't have to be related to factorization necessarily, but that can be a starting point.

I have a mainly CS background, so I'd be more comfortable with computational aspects than pure mathematics.

What are your thoughts?

I'm not sure that I understand the question.

Methods for factorization is an open research topic. What more could
you be looking for?

I can almost guarantee that without the germ of an idea that might lead
to a new algorithm, no advisor will approve a thesis whose goal is a new
algorithm.

It is likely in any event that development of a new algorithm will require
a degree in math and not in C.S.

Allow me to ask: do you know what an Abelian variety is? Do you
know the difference between a general linear transform, a projective
linear transform, and an affine linear transform? Do you have any
background in analysis of algorithms? Have you read Knuth's
"Mathematics for the Analysis of Algorithms"?

Consider, for example, the pursuit of an improved version of ECM.
Perhaps there is an algebraic variety over Q, which when localized over
p yields a group who order is (say) a fractional power of p???

Pursuing such an algorithm is pointless. Do you know why?

If you want to pursue such things you will need a degree in math, rather
than CS.

[jasonp]

A window on current research is here.

In addition, within NFS I can think of:
- within NFS poly selection, optimizing the stage 2 root sieve for degree six polynomials with extreme amounts of skew (see here for background)
- finding a practical measure for estimating the runtime of NFS given only the polynomial and maybe some test sieving
- using GPUs / FPGAs / dedicated hardware for NFS poly selection and/or sieving and/or linear algebra (there's been a lot of work on this one, see the SHARCS conference slides)
- there's a lot of interest in co-factorization, batch methods of factoring the huge number of intermediate quantities generated by NFS sieving.
- there's also interest in choosing multiple NFS polynomials for a single factorization, and somehow getting it to be practical

[philmoore]

PRIME NUMBERS, A Computational Perspective by Richard Crandall and Carl Pomerance contains at the end of each chapter some suggested research problems. That might be a good place to start to get some ideas.

[R.D. Silverman]

Originally Posted by jasonp

A window on current research is here.

In addition, within NFS I can think of:
- within NFS poly selection, optimizing the stage 2 root sieve for degree six polynomials with extreme amounts of skew (see here for background)
- finding a practical measure for estimating the runtime of NFS given only the polynomial and maybe some test sieving
- using GPUs / FPGAs / dedicated hardware for NFS poly selection and/or sieving and/or linear algebra (there's been a lot of work on this one, see the SHARCS conference slides)
- there's a lot of interest in co-factorization, batch methods of factoring the huge number of intermediate quantities generated by NFS sieving.
- there's also interest in choosing multiple NFS polynomials for a single factorization, and somehow getting it to be practical

I can't imagine any advisor allowing any of these to be a PhD research
project. The problems just are not deep enough. A Master's Thesis, yes.

[jasonp]

Do you think NFS is mined out as a source of deep problems?

[R.D. Silverman]

Originally Posted by jasonp

Do you think NFS is mined out as a source of deep problems?

Yes and no.

As far as improving its speed, I think it has no more deep problems.

In terms of its abstract mathematics, no.

For example, a rigorous PROOF of its run time is a deep problem
(and worthwhile solving).

Developing the theory of what makes a good polynomial beyond the
heuristics given in Brian's thesis would be a good problem.


But just finding ways to speed up the polynomial search, or speeding
splitting of the cofactors, or improving the parallelization of the LA
etc. etc. are not PhD worthy problems.

[Robert Holmes]

Originally Posted by R.D. Silverman

I'm not sure that I understand the question.

Methods for factorization is an open research topic. What more could
you be looking for?

I can almost guarantee that without the germ of an idea that might lead
to a new algorithm, no advisor will approve a thesis whose goal is a new
algorithm.

It is likely in any event that development of a new algorithm will require
a degree in math and not in C.S.

Allow me to ask: do you know what an Abelian variety is? Do you
know the difference between a general linear transform, a projective
linear transform, and an affine linear transform? Do you have any
background in analysis of algorithms? Have you read Knuth's
"Mathematics for the Analysis of Algorithms"?

Consider, for example, the pursuit of an improved version of ECM.
Perhaps there is an algebraic variety over Q, which when localized over
p yields a group who order is (say) a fractional power of p???

Pursuing such an algorithm is pointless. Do you know why?

If you want to pursue such things you will need a degree in math, rather
than CS.

First off, thanks to everyone for the replies.

I was purposely vague in the initial post to give the reader more freedom in the topics suggested. I do NOT expect to come up with a new algorithm to factor integers - given my background, it'd be ludicrous to do so.

My initial thoughts were more in the direction of what jasonp later suggested - (speed) improvements to existing factoring algorithms (NFS). It is unclear to me whether that is worthy at all of a PhD thesis. I should also point out that the PhD would eventually be in CS, not Mathematics.

[xilman]

Originally Posted by R.D. Silverman

...
But just finding ways to speed up the polynomial search, or speeding
splitting of the cofactors, or improving the parallelization of the LA
etc. etc. are not PhD worthy problems.

Perhaps not in mathematics but, IMAO, the last of your examples could be the basis of a good PhD in CS.

Finding an algorithm which gives markedly better than sqrt(N) speed-up (where N is the number of processors) for parallel Lanczos under physically reasonable models of computation, or proving under properly stated conditions that such a speed-up is impossible, would definitely be a good result.

Paul

[R.D. Silverman]

Originally Posted by xilman

Perhaps not in mathematics but, IMAO, the last of your examples could be the basis of a good PhD in CS.

Finding an algorithm which gives markedly better than sqrt(N) speed-up (where N is the number of processors) for parallel Lanczos under physically reasonable models of computation, or proving under properly stated conditions that such a speed-up is impossible, would definitely be a good result.

Paul

Finding a better algorithm:
I don't think that such a result would be deep enough for a PhD.

Proving it impossible under a suitable model would be suitable.
Currently, omega results are few and far between.

[xilman]

Originally Posted by R.D. Silverman

Finding a better algorithm:
I don't think that such a result would be deep enough for a PhD.

Perhaps. Perhaps not. Do you know how to perform linear algebra over F_2 on a quantum computer markedly faster than it can be done on a classical TM, for instance?

Can't say I do, but neither do I know that it's impossible. I'm in a position of profound ignorance in this regard. For far too many subjects that's my ground state, as the quantum theorists would term it.

Paul