اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدStructure computation and discrete logarithms in finite abelian p-groups
148
0
0.0
(
0
)
تأليف
Andrew V. Sutherland
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 a
rguments 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 thi
s speculation to the finite general linear groups $mathrm{GL}_mleft(mathbb{F}_qright)$ and $mathrm{SL}_2left(mathbb{F}_qright)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
