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.