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
0.8136197328567505
0 references
0.8019556999206543
0 references
0.790692925453186
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