The approximate GCD problem

Speaker: 

Randell Heyman

Affiliation: 

UNSW

Date: 

Wed, 15/04/2015 - 1:30pm

Venue: 

OMB 145 (Old Main Building)

Abstract: 

The approximate GCD problem seeks to efficiently determine the GCD of a set of numbers.
We do not know most or all of the numbers; rather we are given numbers that lie close by.
As well as discussing some methods to solve the problem I will explore two applications of the problem; namely attacks on RSA and fully homomorphic encryption.
I will finish with a dual problem and some related problems from joint work with Igor Shparlinski.
The talk is for a more general audience than one would expect at the number theory seminar.

School Seminar Series: