Re: Probabilistic polynomial time algorithm for solving the DLOG problem

On 11-05-26 9:22 PM, Jeffrey Goldberg wrote:
On 11-05-26 7:37 PM, Maaartin G wrote:

Using the hint that Pubkeybreaker gave that "Subgroups with size
5,7,8,9,10,11 are impossible" along with your example of even numbers
then a first guess is that [turned out to be wrong]

I'll play with this this evening. Thanks!

I got stuck on the proof. The actual pattern is instantly clear.

For a Group {0, 1, ..., m-1} with a * b = a + b mod m, then for every n
such that n divides m there is a subgroup S_n containing all the
multiples of n mod m

So in the case of m = 12 there are six subgroups including {0} and also
the not quite proper subgroup where n = 1, {0, 1, ..., 11}.

That bit is obvious. And most of the proof is simple, but there are a
couple of place where I got stuck.

First a lemma. If x divides y and cx > y, then cx mod y is a multiple of
x. Proof. As x divides y the "mod y" operation is the same as
subtracting an multiple of x from cx. The result of that subtraction is
a multiple of x.

Part 1. First to prove that all sets meeting my definition are subgroups.

Because n divides m, there will be a multiple of n that equals m. m mod
m is zero, so 0 will always be in there.

Now for closure. Consider two elements, an and bn. an + bn is a multiple
of n. There are three cases

Case 1: an + bn < m; This is trivially in the set.
Case 2: an + bn = m; 0 is in the set (as shown earlier).
Case 3: an + bn > m; by the lemma above this is a multiple of n and by
definition of "mod" it is less then m. This also in the set.

What I haven't been able to prove (though the intuitions are there) is
that only those sets will be subgroups. Maybe I'll have to look up
Legrange's work after all. But I was hoping that I could prove this all
on my own. Maybe after I've slept a bit.

Cheers,

-j

--
Jeffrey Goldberg http://goldmark.org/jeff/
I rarely read HTML or poorly quoting posts
Reply-To address is valid
.

Relevant Pages

  • Re: Connecticut: Teacher leaves over evolution flap
    ... can't be sure of is whether their teachers are lazy, ... perhaps deliberately trying to raise student scores in the classroom ... same multiple in both and hence subtracting makes one variable drop out ...
    (talk.origins)
  • Re: Bring Math Arguments against this FERMAT LAST THEOREM PROOF
    ... He got to regnoise that the key ideea of the proof is original and ... > contradicting the ... > divides one of them, ... > multiple of 9. ...
    (sci.math)
  • Re: JSH: Point of logic
    ... jstevh@msn.com (James Harris) writes: ... > multiple, and dividing that multiple off divides 49 from the factors ... Clearly, it's not the distributive law that's relevant, because the ...
    (sci.math)
  • Re: Polynomials in Z(p)
    ... alert: your x was the polynomial variable; ... f=0 for all a in Z, then (x-a) divides ffor all a in Z. ... the zero function if and only if it is a multiple of x^p-x. ...
    (sci.math)
  • Re: Simple group of order 60
    ... I'm not saying that there are no subgroups of order 12. ... then the number of such elements is also a multiple of 20. ... These conjugates cannot overlap. ...
    (sci.math)