Upper bounds for least witnesses and generating sets (Q4345837)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1039316
Language Label Description Also known as
default for all languages
No label defined
    English
    Upper bounds for least witnesses and generating sets
    scientific article; zbMATH DE number 1039316

      Statements

      Upper bounds for least witnesses and generating sets (English)
      0 references
      30 July 1997
      0 references
      upper bounds
      0 references
      least witnesses
      0 references
      generating sets
      0 references
      primality tests
      0 references
      strong pseudoprime
      0 references
      For \(n,y\in \mathbb{Z}^+\), let \({\mathcal G}_n(y)\) denote the subgroup of \((\mathbb{Z}/n \mathbb{Z})^*\) generated by the elements of \((\mathbb{Z}/n \mathbb{Z})^*\) with representatives not exceeding \(y\). Define \(G(n)\) to be the smallest \(G\) such that \({\mathcal G}_n (G)= (\mathbb{Z}/n \mathbb{Z})^*\). The author proves that for all \(n\), \[ G(n)\ll n^{1/(3 \sqrt e)+ \varepsilon}, \] and for \(8\nmid n\), \[ G(n) \ll n^{1/(4 \sqrt e)+ \varepsilon}. \] He also shows the connection between \(G(n)\) and primality tests. Let \(n\) be an odd integer \(>1\) with \(n-1=2^st\), where \(t\) is odd. For \(a\in [1, n-1]\), we say that \(n\) is a strong pseudoprime to the base \(a\) if either \(a^t\equiv 1 \pmod n\) or \[ a^{2^it} \equiv- 1\pmod n\text{ for some } i\in [1,n-1]. \tag{1} \] If (1) fails for some \(a\in [1, n-1]\), then \(a\) is called a witness of \(n\). Denote the smallest witness of \(n\) by \(W(n)\). The author proves that \(w(n)\ll n^{1/(6 \sqrt e)+ \varepsilon}\) for all odd composite \(n\).
      0 references

      Identifiers