mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-02-08, 16:04   #1
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

1528 Posts
Default 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?
Robert Holmes is offline   Reply With Quote
Old 2010-02-08, 17:04   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by Robert Holmes View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-02-08, 17:11   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24×13×17 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2010-02-08, 17:16   #4
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2010-02-08, 17:30   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-02-08, 17:40   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24·13·17 Posts
Default

Do you think NFS is mined out as a source of deep problems?
jasonp is offline   Reply With Quote
Old 2010-02-08, 18:01   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-02-08, 19:05   #8
Robert Holmes
 
Robert Holmes's Avatar
 
Oct 2007

2·53 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.
Robert Holmes is offline   Reply With Quote
Old 2010-02-08, 19:29   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·2,659 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
...
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
xilman is offline   Reply With Quote
Old 2010-02-08, 20:53   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2010-02-08, 21:35   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×2,659 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Collaborative Research a1call Information & Answers 7 2017-01-29 17:55
PhD Research Proposal pinhodecarlos Soap Box 2 2012-08-18 22:01
To CPU or to GPU: stage1 polyselect research Karl M Johnson Msieve 8 2011-11-12 19:46
Research of 2^n - 3 questions gd_barnes Riesel Prime Search 3 2007-05-10 17:26
Unable to View Help Topics on Prime95 jinydu Software 7 2006-11-04 18:30

All times are UTC. The time now is 05:03.

Sun Apr 11 05:03:08 UTC 2021 up 2 days, 23:44, 1 user, load averages: 1.53, 1.84, 1.72

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.