Some remarks on computing the square parts of integers
type: Item
instance of: scholarly article
title: Some remarks on computing the square parts of integers
zbMATH Open document ID: 0661.10007
DOI: 10.1016/0890-5401(88)90028-4
author: Susan Landau
published in: Information and Computation
publication date: 1988-01-01T00:00:00Z
review text: The complexities of the computation of values of several number theoretic functions are compared. For a natural number \(n\in {\mathbb{N}}\) with prime factorization \(\prod p_ i^{a_ i}\) these functions are defined as follows: \(\phi (n)=\prod p_ i^{a_ i-1}(p_ i-1)\) Euler's function; \(\lambda (n)=lcm\{p_ i^{a_ i-1}(p_ i-1)\}\) Carmichael's function; \(\lambda '(n)=lcm\{p_ i-1\}\); \(\theta (n)=\prod p_ i^{a_ i-1}\), square part of n. It is shown that the computation of \(\theta\) is in polynomial time Turing reducible to the computation of \(\phi\) or \(\lambda\). In addition it is shown that the computation of \(\lambda\) ' is in polynomial time reducible to that of \(\lambda\) and the computation of \(\lambda\) is reducible in polynomial time to the computation of both \(\theta\) and \(\lambda\) '. It is conjectured that it is not possible that the computation of \(\theta\) can be reduced to that of \(\lambda\) '.
Mathematics Subject Classification ID: 11A25
Mathematics Subject Classification ID: 11A41
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4079503
zbMATH Keywords: arithmetical functions
zbMATH Keywords: factoring
zbMATH Keywords: complexity
zbMATH Keywords: computational number theory
zbMATH Keywords: Euler's function
zbMATH Keywords: Carmichael's function
zbMATH Keywords: square part
zbMATH Keywords: polynomial time Turing reducible
MaRDI profile type: Publication
full work available at URL: 0890-5401(88)90028-4
OpenAlex ID: W1991495399
cites work: Sums of Divisors, Perfect Numbers and Factoring
cites work: Riemann's hypothesis and tests for primality
cites work: Reductions among number theoretic problems
description: scientific article; zbMATH DE number 4079503