Computational aspects of rational residuosity

DOI10.1142/S1793042118500380zbMATH Open1476.11009arXiv1604.07791OpenAlexW3102087929MaRDI QIDQ4609564FDOQ4609564

Authors: Markus Hittmeir 

Publication date: 4 April 2018

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

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.

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

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

zbMATH Keywords

factorizationreciprocityprimalitypower residues

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A rational octic reciprocity law
• A generalization of Scholz' reciprocity law
• Rational reciprocity laws
• A rational sixteenth power reciprocity law
• A Simple Proof of the Zolotareff-Frobenius Theorem
• Permutations of rational residues

Cited In (8)

• Some theorems on residues
• Little extension of Euler's criterion for quadratic residue
• 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
• Title not available (Why is that?)

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)