20100208, 16:04  #1 
Oct 2007
6A_{16} Posts 
Research topics
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? 
20100208, 17:04  #2  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,889 Posts 
Quote:
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. 

20100208, 17:11  #3 
Tribal Bullet
Oct 2004
5×23×31 Posts 
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 cofactorization, 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 
20100208, 17:16  #4 
"Phil"
Sep 2002
Tracktown, U.S.A.
19·59 Posts 
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.

20100208, 17:30  #5  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}·1,889 Posts 
Quote:
project. The problems just are not deep enough. A Master's Thesis, yes. 

20100208, 17:40  #6 
Tribal Bullet
Oct 2004
6755_{8} Posts 
Do you think NFS is mined out as a source of deep problems?

20100208, 18:01  #7 
"Bob Silverman"
Nov 2003
North of Boston
1110110000100_{2} Posts 
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. 
20100208, 19:05  #8  
Oct 2007
2×53 Posts 
Quote:
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. 

20100208, 19:29  #9  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·5·11·107 Posts 
Quote:
Finding an algorithm which gives markedly better than sqrt(N) speedup (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 speedup is impossible, would definitely be a good result. Paul 

20100208, 20:53  #10  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×1,889 Posts 
Quote:
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. 

20100208, 21:35  #11  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
10110111111010_{2} Posts 
Quote:
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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Collaborative Research  a1call  Information & Answers  7  20170129 17:55 
PhD Research Proposal  pinhodecarlos  Soap Box  2  20120818 22:01 
To CPU or to GPU: stage1 polyselect research  Karl M Johnson  Msieve  8  20111112 19:46 
Research of 2^n  3 questions  gd_barnes  Riesel Prime Search  3  20070510 17:26 
Unable to View Help Topics on Prime95  jinydu  Software  7  20061104 18:30 