Computing Jacobi symbols modulo sparse integers and polynomials and some applications

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

We describe a polynomial time algorithm to compute Jacobi symbols of exponentially large integers of special form, including so-called sparse integers which are exponentially large integers with only polynomially many nonzero binary digits. In a number of papers sequences of Jacobi symbols have been proposed as generators of cryptographically secure pseudorandom bits. Our algorithm allows us to use much larger moduli in such constructions. We also use our algorithm to design a probabilistic polynomial time test which decides if a given integer of the aforementioned type is a perfect square (assuming the Extended Riemann Hypothesis). We also obtain analogues of these results for polynomials over finite fields. Moreover, in this case the perfect square testing algorithm is unconditional. These results can be compared with many known NP-hardness results for some natural problems on sparse integers and polynomials.

Original languageEnglish
Pages (from-to)241-252
Number of pages12
JournalJournal of Algorithms
Volume36
Issue number2
DOIs
Publication statusPublished - 2000

Fingerprint Dive into the research topics of 'Computing Jacobi symbols modulo sparse integers and polynomials and some applications'. Together they form a unique fingerprint.

Cite this