| EPSRC Reference: |
EP/L001454/1 |
| Title: |
Detecting squarefree numbers |
| Principal Investigator: |
Booker, Dr AR |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Mathematics |
| Organisation: |
University of Bristol |
| Scheme: |
Standard Research |
| Starts: |
01 July 2013 |
Ends: |
30 June 2015 |
Value (£): |
83,865
|
| EPSRC Research Topic Classifications: |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
22 May 2013
|
Developing Leaders Meeting - LF
|
Announced
|
|
|
Summary on Grant Application Form |
In number theory, one of the most basic questions posed about a given natural number N is whether it has any square factors larger than 1. As far as anyone knows at present, answering this question is no easier than factoring N, which is believed to be a very hard problem in general. On the other hand, the same question can be asked about polynomials, and in that setting it turns out that there is a very simple procedure to find the answer. This apparent discrepancy has led number theorists to wonder for centuries whether there might be such a simple method for ordinary natural numbers.
This proposal builds on work of the PI and collaborators at Bristol which describes an algorithm for determining if a given N has any non-trivial square factors without factoring it. However, the method as presented in that work turns out to be slower than the expected speed of the current best known factoring algorithms. The proposed project will explore several strategies for going beyond that initial work, with the goal of improving the performance of the algorithm, possibly even reaching the holy grail of the field, a polynomial-time algorithm for squarefree testing.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
http://www.bris.ac.uk |