Abstrakt. I detta papper presenterar vi flera baby-steg jätte-steg algoritmer för låg hamming vikt diskret logaritm problem. I denna version av den diskreta logg problem, Vi är skyldiga att hitta en diskret logaritm i en ändlig grupp av ordning ungefär 2 m, Med tanke på att den okända logaritm har ett angivet antal 1 s, säger t, i sin binära representation. Heiman och Odlyzko presenterade de första algoritmerna för detta problem.. Vi utför en genomsnittlig analys av Coppersmiths deterministiska algoritm. Den genomsnittliga komplexiteten ger bara en konstant faktorupptrappning i värsta fall. Därför presenterar vi en generaliserad version av Coppersmiths algoritm, med hjälp av ett kombinatoriskt system som vi kallar ett delningssystem. Med hjälp av probabilistiska metoder, visar vi en ny existens resultat för dessa system som ger en (icke-uniform) deterministisk algoritm med komplexitet. Vi presenterar också några explicita konstruktioner för delningssystem som använder sig av perfekta hashfamiljer.
Det bevisas i REF att den genomsnittliga komplexiteten endast uppnår en konstant faktorupptrappning jämfört med det värsta fallet.
Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem
{'venue': 'Mathematics of Computation', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}