| EPSRC Reference: |
EP/C015126/1 |
| Title: |
Computational Number Theory and Numerical Analysis |
| Principal Investigator: |
Tourigny, Dr Y |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Mathematics |
| Organisation: |
University of Bristol |
| Scheme: |
Discipline Hopping Pre-FEC |
| Starts: |
05 September 2005 |
Ends: |
04 September 2006 |
Value (£): |
51,142
|
| EPSRC Research Topic Classifications: |
| Algebra & Geometry |
Fundamentals of Computing |
| Numerical Analysis |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Numerical Analysis is the branch of applied mathematics concernedwith obtaining answers to mathematical problems in numerical form,such as one obtains with a calculator.Many recipes (algorithms) have been devised to solve large-scale problems arising in science and engineering. Cryptography is the branch of Computational NumberTheory concerned with the development of algorithms for exchanginginformation in a confidential and secure way (secret passing).There is considerable scope for a fruitfulinteraction between the two subjects, and the project'saim is to use some ideas from Numerical Analysisto improve existing--- and develop new--- algorithmsto solve problems of cryptography. The rough pattern of progressin the field of cryptography goes like this: a method of encryptinginformation is proposed, and the research communityresponds by devising ``attacks'' to``break'' the system. One of the most importantproblem in this context is that of finding theprime factors of a given large integer.There are many algorithms to do this, but for verylarge numbers, they are very slow, and this formsthe basis of current methods of passing secrets.A key concept in the proposed research is thatof continued fraction expansion; this is a way of expandinga real number without using any particular base number (suchas 10 in the decimal expansion). The concept of continued fractioncan be generalised in many different directions; it has foundsome powerful applications in Numerical Analysis, whereit is used for the purpose of approximating numbers. At the same time, the mostsuccessful algorithms for factoring integers make use of a concept called lattice basis reduction and, as it turnsout, this can be interpreted in terms of generalised continuedfractions. The main objective of the research will be to use this connection to develop faster ways of factoring large integers efficiently.If successful, the research would lead to better methods of passing secrets. This is an area of critical importance to national securityand to e-commerce.
|
|
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 |