Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some Applications
✍ Scribed by Igor E. Shparlinski
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 94 KB
- Volume
- 36
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 Hypoth-. esis . 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.