Nontrivial Solutions to the Cubic Sieve Congruence Problem: x³ ≡ y² z mod p

Loading...
Thumbnail Image
Authors
Maitra, Subhamoy
Rao, Subba, Y.V.
Stănică, Pantelimon
Gangopadhyay, Sugata
Subjects
Discrete Log Problem
Cubic Sieve Congruence
Prime Numbers
Advisors
Date of Issue
2009
Date
2009
Publisher
Language
en_US
Abstract
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.
Type
Article
Description
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
15 p.
Citation
Maitra, S., Subba Rao, Y.V., Stanica, P. & Gangopadhyay, S. 2009, "Nontrivial solutions to the cubic sieve congruence problem x3=y2 z \pmod p", Special Issue on Applied Cryptography & Data Security in Journal of "Computacion y Sistemas" (eds. F. Rodriguez-Henriquez, D. Chakraborty), vol. 12, no. 3, pp. 253--266.
Distribution Statement
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