Re: Probabilistic polynomial time algorithm for solving the DLOG problem

Am 29.05.2011 02:19, schrieb Benjamin Kreuter:
On 05/28/2011 07:46 PM, Mok-Kong Shen wrote:
Am 29.05.2011 01:20, schrieb Jeffrey Goldberg:
On 11-05-28 1:59 AM, Mok-Kong Shen wrote:

This thread is rather large for my humble math knowledge to oversee.
But is the above the kernel of what is being argued about? If yes,
I wonder why one doesn't try to prove it directly, i.e. consider the
set { 0, 1*n, 2*n, ... c*n } with c = m/n -1 and show according to
the definition of a group that this is indeed one. (Pardon, should
I gravely err.)

That bit I proved straight off. The difficulty for me was proving the
converse. That *only* such sets formed subgroups. (Of course now that
I've succeeded in the rest of it, it seems obvious in retrospect).

I might err, but offhand I am not clear that one could prove the
converse, i.e. that there is (generally, for "arbitrary" m) only one
subgroup of order m/n (corresponding to a given value of n), though
(in case more than one) these are homomorphic to one another. Was
such a proof already given in this thread? If yes, please give the
reference. If no, please kindly show your proof. I like to learn that.

For general groups, that is not true. For example, consider the group
(Z/2Z)^2 -- that is, ordered pairs of integers modulo 2 under addition,
which is called the Klein-4 group. There are clearly two subgroups with
two elements:

{(0,0), (0,1)} and {(0,0), (1,0)}

What I wrote was meant only for the case considered by Goldberg, i.e.
his claim of a converse seems to be not provable (if my intuition
turns out to be right).

M. K. Shen

Relevant Pages