Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStructure computation and discrete logarithms in finite abelian p-groups
140
0
0.0
(
0
)
Authors
Andrew V. Sutherland
Ask ChatGPT about the research
No Arabic abstract
We present a generic algorithm for computing discrete logarithms in a finite abelian p-group H, improving the Pohlig-Hellman algorithm and its generalization to noncyclic groups by Teske. We then give a direct method to compute a basis for H without using a relation matrix. The problem of computing a basis for some or all of the Sylow p-subgroups of an arbitrary finite abelian group G is addressed, yielding a Monte Carlo algorithm to compute the structure of G using O(|G|^0.5) group operations. These results also improve generic algorithms for extracting pth roots in G.
rate research
Read More
A subset $B$ of a group $G$ is called a difference basis of $G$ if each element $gin G$ can be written as the difference $g=ab^{-1}$ of some elements $a,bin B$. The smallest cardinality $|B|$ of a difference basis $Bsubset G$ is called the difference size of $G$ and is denoted by $Delta[G]$. The fraction $eth[G]:=frac{Delta[G]}{sqrt{|G|}}$ is called the difference characteristic of $G$. Using properies of the Galois rings, we prove recursive upper bounds for the difference sizes and characteristics of finite Abelian groups. In particular, we prove that for a prime number $pge 11$, any finite Abelian $p$-group $G$ has difference characteristic $eth[G]<frac{sqrt{p}-1}{sqrt{p}-3}cdotsup_{kinmathbb N}eth[C_{p^k}]<sqrt{2}cdotfrac{sqrt{p}-1}{sqrt{p}-3}$. Also we calculate the difference sizes of all Abelian groups of cardinality $<96$.
As a consequence of the classification of finite simple groups, the classification of permutation groups of prime degree is complete, apart from the question of when the natural degree $(q^n-1)/(q-1)$ of ${rm L}_n(q)$ is prime. We present heuristic arguments and computational evidence to support a conjecture that for each prime $nge 3$ there are infinitely many primes of this form, even if one restricts to prime values of $q$.
We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shors algorithms for period finding and discrete log as subroutines. Thus proposed cryptosystems based on the presumed hardness of discrete logarithms in semigroups are insecure against quantum attacks. In contrast, we show that some generalizations of the discrete log problem are hard in semigroups despite being easy in groups. We relate a shifted version of the discrete log problem in semigroups to the dihedral hidden subgroup problem, and we show that the constructive membership problem with respect to $k ge 2$ generators in a black-box abelian semigroup of order $N$ requires $tilde Theta(N^{frac{1}{2}-frac{1}{2k}})$ quantum queries.
Refining a result of Erdos and Mays, we give asymptotic series expansions for the functions $A(x)-C(x)$, the count of $nleq x$ for which every group of order $n$ is abelian (but not all cyclic), and $N(x)-A(x)$, the count of $nleq x$ for which every group of order $n$ is nilpotent (but not all abelian).
In previous work, the authors confirmed the speculation of J. G. Thompson that certain multiquadratic fields are generated by specified character values of sufficiently large alternating groups $A_n$. Here we address the natural generalization of this speculation to the finite general linear groups $mathrm{GL}_mleft(mathbb{F}_qright)$ and $mathrm{SL}_2left(mathbb{F}_qright)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
