Computational aspects of rational residuosity

DOI10.1142/S1793042118500380MaRDI QIDQ4609564zbMATH OpenOpenAlexFDO

Authors Markus Hittmeir

Publication date 4 April 2018

Published in International Journal of Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.07791

zbMATH Keywords

factorizationreciprocityprimalitypower residues

Mathematics Subject Classification ID

Power residues, reciprocity (11A15) Factorization; primality (11A51)

Abstract: In this paper, we consider an extension of Jacobi's symbol, the so called rational $2^k$-th power residue symbol. In Section 3, we prove a novel generalization of Zolotarev's lemma. In Sections 4, 5 and 6, we show that several hard computational problems are polynomial-time reducible to computing these residue symbols, such as getting nontrivial information about factors of semiprime numbers. We also derive criteria concerning the Quadratic Residuosity Problem.

Recommendations

• A new theorem about the quadratic residuosity problem
• On the optimality of the binary algorithm for the Jacobi symbol
• scientific article; zbMATH DE number 919915
• scientific article; zbMATH DE number 3954815
• Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some Applications

Cites work

• scientific article; zbMATH DE number 1452559 (Why is no real title available?)
• scientific article; zbMATH DE number 2231186 (Why is no real title available?)
• scientific article; zbMATH DE number 3091928 (Why is no real title available?)
• A Simple Proof of the Zolotareff-Frobenius Theorem
• A generalization of Scholz' reciprocity law
• A rational octic reciprocity law
• A rational sixteenth power reciprocity law
• Permutations of rational residues
• Rational reciprocity laws

Cited in

(8)

• Little extension of Euler's criterion for quadratic residue
• Some theorems on residues
• On a certain nilpotent extension over \(\mathbb Q\) of degree 64 and the 4-th multiple residue symbol
• The Legendre and Jacobi symbols for \(k\)-ic residues
• Public-key cryptosystem based on \(n\)-th residuosity of \(n=p^2q\)
• Computational rationality: A converging paradigm for intelligence in brains, minds, and machines
• A new theorem about the quadratic residuosity problem
• scientific article; zbMATH DE number 919915 (Why is no real title available?)

This page was built for publication: Computational aspects of rational residuosity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4609564)