Nontrivial Solutions to the Cubic Sieve Congruence Problem: x3 is congruent to y2z mod p: Soluciones no Triviales al problema de Congruencia de Criba Cubica: x3 is congruent to y2z mod p
Abstract
In this paper we discuss the problem of finding nontrivial solutions to the Cubic Sieve Congruence problem, that is solutions of x3 is congruent to y2z (mod p), where x, y, z < p 1/2 and x3 not equal to y2z. The solutions to this problem are useful in solving the Discrete Log Problem or factorization by index calculus method. Apart from the cryptographic interest this problem is motivating by itself from a number theoretic point of view. Though we could not solve the problem completely, we could identify certain sub classes of primes where the problem can be solved in time polynomial in log p. Further we could extend the idea of Reyneri's sieve and identify some cases in it where the problem can even be solved in constant time. Designers of cryptosystems should avoid all primes contained in our detected cases.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 2009
- Accession Number
- ADA548909
Entities
People
- Pantelimon Stanica
- Subhamoy Maitra
- Sugata Gangopadhyay
- Y. V. Subba Rao
Organizations
- Naval Postgraduate School