International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On differences of quadratic residues

Authors:
Guillermo Morales-Luna
Download:
URL: http://eprint.iacr.org/2008/433
Search ePrint
Search Google
Abstract: Factoring an integer is equivalent to express the integer as the difference of two squares. We test that for any odd modulus, in the corresponding ring of remainders, any element can be realized as the difference of two quadratic residues, and also that, for a fixed remainder value, the map assigning to each modulus the number of ways to express the remainder as difference of quadratic residues is non-decreasing with respect to the divisibility ordering in the odd numbers. The reduction to remainders rings of the problem to express a remainder as the difference of two quadratic residues does not diminish the complexity of the factorization problem.
BibTeX
@misc{eprint-2008-18119,
  title={On differences of quadratic residues},
  booktitle={IACR Eprint archive},
  keywords={foundations /},
  url={http://eprint.iacr.org/2008/433},
  note={ gmorales@cs.cinvestav.mx 14160 received 8 Oct 2008},
  author={Guillermo Morales-Luna},
  year=2008
}