Re: Generator of a group
From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 6 Jan 2005 12:13:44 -0800
In article <firstname.lastname@example.org>,
Tobias Ruske <email@example.com> wrote:
>the next problem is:
>I search the generator of the group of quadratic residues for a prime p
>and p is a 1024-bit value.
>The group of quadratic residues has the order n = (p-1)/2, right? Now I
>need the prime factorization of n (see HAC 4.80). But n is a 1023-bit
>value (or?) and it's hard to find the factorization for such a big
>value. And now my question is: Is there another way to find the
>generator (without the need of a factorization)?
I'm not aware of any way to do it without knowing
the factors of p-1, and I have a strong feeling
that there can't be one, but I'd be happy to be
corrected on this.
Do you get to choose p? If so, you can easily
construct a prime p such that you already know
its factorization. See, for example, the way
moduli are chosen for the Digital Signature
Standard, FIPS-186-2. Or construct it such that
(p-1)/2 is prime. Or just try to factor p-1, and
see where you get to... on average, large numbers
have a few small factors and a single large one
(which you can check for primality). Unless you're
unlucky, you shouldn't need to try too hard.
If you don't get to choose P, you might be out of
-- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C Qualcomm Australia: http://www.qualcomm.com.au