Computing Jacobi symbols modulo sparse integers and polynomials and some applications

Igor E. Shparlinski

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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
Issue number2
Publication statusPublished - 2000


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