An RSA problem and a new Groebner basis algorithm
Michael Monagan, SFU
I wish to present an unsolved number theoretic problem which comes from the RSA encryption system. After this I wish to briefly present a new result of Faugere for computing Grobner bases which was presented last week at ISSAC in Lille. A theorem of Direchlet from 1849 states: If a and b are random integers then the probability that they are relative prime is 6/Pi^2 = 0.60793... If we could show that a sequence of integers c1, c2, c3, ... arising from RSA encryption are sufficiently random, then we would have a new proof that computing the decryption exponent d in the RSA encryption system is (random) polynomial time equivalent to factoring n. I will show how the integers c1,c2,c3, arise and give some evidence that they are reasonably random. It remains to show that the algorithm always works. Buchberger's algorithm for computing a Grobner basis needs to reducd so called S-polynomials by the current basis. Since most of the time is wasted reducing S-polynomials to zero Buchberger and others have identified ``tests'' that can, with little work, identify which S-polynomials will reduce to zero in advance. Faugere has presented a new test which essentially eliminates all redundant S-polynomial reductions.