World Scientific
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.

AN EFFICIENT SEVENTH POWER RESIDUE SYMBOL ALGORITHM

    https://doi.org/10.1142/S1793042110003770Cited by:5 (Source: Crossref)

    Power residue symbols and their reciprocity laws have applications not only in number theory, but also in other fields like cryptography. A crucial ingredient in certain public key cryptosystems is a fast algorithm for computing power residue symbols. Such algorithms have only been devised for the Jacobi symbol as well as for cubic and quintic power residue symbols, but for no higher powers. In this paper, we provide an efficient procedure for computing 7th power residue symbols. The method employs arithmetic in the field ℚ(ζ), with ζ a primitive 7th root of unity, and its ring of integers ℤ[ζ]. We give an explicit characterization for an element in ℤ[ζ] to be primary, and provide an algorithm for finding primary associates of integers in ℤ[ζ]. Moreover, we formulate explicit forms of the complementary laws to Kummer's 7th degree reciprocity law, and use Lenstra's norm-Euclidean algorithm in the cyclotomic field.

    AMSC: 11R18, 11A15, 11A05, 11Y16
    Remember to check out the Most Cited Articles!

    Check out new Number Theory books in our Mathematics 2021 catalogue