Can we generate "RSA-safe" values of polynomials

2:00pm, Wednesday 23 July

Abstract

A crucial part of various cryptosystems such as RSA is to generate composite numbers n=pq that are almost impossible to factorise. Among other restrictions, that means that n needs to be huge (e.g. 2048 bits) and p and q need to be primes of a similar size. Such numbers are not difficult to generate. But what if, on top of that, we require n to be a value P(m) of a given polynomial P with integer coefficients at an integer point m? Then the problem becomes much less trivial. In this talk I will discuss how one can randomly generate such triples (p,q,m) for quadratic and cubic polynomials P. We will also see that p and q can be generated in such a way that p/q is close to any given positive real number.