Nontrivial Solutions to the Cubic Sieve Congruence Problem: x³ ≡ y² z mod p
Author
Maitra, Subhamoy
Rao, Subba, Y.V.
Stănică, Pantelimon
Gangopadhyay, Sugata
Date
2009Metadata
Show full item recordAbstract
In this paper we discuss the problem of finding nontrivial solutions to the Cubic Sieve Congruence problem, that is,
solutions of x³ ≡ y² z (mod p), where x, y, z < p½
and x³≠ y²z. 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.
Keywords: Cubic Sieve Congruence, Discrete Log Problem, Prime Numbers.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Nontrivial solutions to the cubic sieve congruence problem x^3=y^2 z (mod p)
Maitra, Submahoy; Rao, Subba, Y. V.; Stănică, Pantelimon; Gangopadhyay, Sugata (2009);In this paper we discuss the problem of finding nontrivial solutions to the Cubic Sieve Congruence probem, that is, solutions of x2 = y2z (mod p), where x,y,z < p1/2 and x3 = y2z. The solutions to this problem are useful ... -
Design and Control of Libration Point Spacecraft Formations
Infeld, Samantha I.; Josselyn, Scott B.; Murray, Walter; Ross, Michael I. (The American Institute of Aeronautics and Astronautics (AIAA), 2007-07);We investigate the concurrent problem of orbit design and formation control around a libration point. Concurrency implies that the design and control problem are simultaneously investigated. Separating the two problems is ... -
Optimization of low thrust trajectories with terminal aerocapture
Josselyn, Scott B. (Monterey, California. Naval Postgraduate School, 2003-06);This thesis explores using a direct pseudospectral method for the solution of optimal control problems with mixed dynamics. An easy to use MATLAB optimization package known as DIDO is used to obtain the solutions. The ...