Research Perspectives - Tools for Visualisation of Portfolios
EPSRC logo

EPSRC Database


Source RCUK EPSRC Data

EP/L001454/1 - Detecting squarefree numbers

Research Perspectives grant details from EPSRC portfolio

http://www.researchperspectives.org/gow.grants/grant_EPL0014541.png

Dr AR Booker EP/L001454/1 - Detecting squarefree numbers

Principal Investigator - Mathematics, University of Bristol

Scheme

Standard Research

Research Areas

Number Theory Number Theory

Start Date

07/2013

End Date

06/2015

Value

£83,865

Similar Grants

Automatic generation of similar EPSRC grants

Similar Topics

Topic similar to the description of this grant

Grant Description

Summary and Description of the grant

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.

Structured Data / Microdata


Grant Event Details:
Name: Detecting squarefree numbers - EP/L001454/1
Start Date: 2013-07-01T00:00:00+00:00
End Date: 2015-06-30T00:00:00+00:00

Organization: University of Bristol

Description: 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 ...