lu.se

Matematikcentrum

Lunds universitet

Denna sida på svenska This page in English

Sparbanksstiftelsen Skånes pris för bästa kandidatarbete inom Naturvetenskapliga fakulteten har tilldelats matematikstudenten Raul Hindov för arbetet "Observations on continued fractions Ford's point of view". Här är priskommitténs motivering:

2017-06-07

Raul Hindov har skrivet ett mycket läsvärt examensarbete om kedjebråk baserat på ideer av L. R. Ford från 1938 och Bearden och Short från de senaste åren, som ger en mycket åskådlig och geometrisk bild av kedjebråken. Efter en förtjänstfull historisk tillbakablick följd av en genomgång av Fords ideer diskuteras hur kedjebråk kan användas för snabb faktorisering av stora tal såväl som till approximation av reella tal. Det är anmärkningsvärt att finna originalbidrag i ett examensarbete i matematik på kandidatnivå. Här är bevisen för sats 2 på s.24, lemma 3 på s.34 och sats 4 på s.42 nya. Följdsats 3.1 på s.36 förefaller vara ett helt nytt resultat. Kedjebråken utgör en del av talteorin, som ofta uppfattas som helt befriat från tillämpningar. Sedan s.k. public key kryptering infördes får några årtionden sedan gäller detta inte längre. Dessa metoder är i dag centrala i för många verksamheter, däribland banker, och bygger på svårigheten att faktorisera stora tal. Skall man bryta en sådan kryptering måste man finna metoder att snabbt utföra faktorisering. Raul visar hur kedjebråk kan användas för att betydligt snabba upp faktorisering.

 
Raul Hindov has written a very readable account of continuous fractions based on ideas
by L. R. Ford from 1938 and Bearden and Short in recent years, which gives a very
intuitive and geometric view of continuous fractions. After a nice historic retrospect
followed by an overview of Ford's ideas Raul discusses how continuous fractions may be
used for fast factorization of large numbers as well as for approximation of real numbers.
It is remarkable to find original contributions in a candidate thesis in mathematics.
Here the proofs of Theorem 2 on p.24, Lemma 3 on p.34 and Theorem 4 on p.42 are new.
Corollary 3.1 on p.36 appears to be completely new.
Continuous fractions are a part of number theory, which is often seen as completely
free of applications. Since public key encryption was introduced a few decades ago
this is no longer so. Public key encryption is today very important for many
organizations, including banks, and is based on the difficulty of factorizing large
numbers. To break such an encryption one must find fast methods to factorize numbers.
Raul shows how continuous fractions may be used to speed up factorization considerably.

 

 

Abstract

This is a project on a geometric method to visualise the calculation of continued fractions, which was developed by Lester R. Ford in the 1930s. The description of the method is followed by the use of the technique of Ford circles on three distinct cases. In contrast to a continued fraction with positive integer coefficients, which is always convergent, a continued fraction with real coefficients might diverge. This project provides an alternative geometric proof for one of the classical convergence theorems on continued fractions. Among the integer factorization methods there is one that uses continued fractions. We give an alternative geometric proof for the lemma that is the base for the method and for a corollary that reduces the factoring problem by a factor of 2. Continued fractions are also connected to the subject of Diophantine approximation, and the project presents an alternative geometric proof for the Dirichlet's approximation theorem. We assume the reader to be a mathematics student who has taken a course on Number Theory and on Analytic Functions, and has certain amount of time on her hands to read the paper.