Re: Generator of a group
From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 01/06/05
 Next message: Xcott Craver: "Re: Solution for safe internet based evoting"
 Previous message: MokKong Shen: "Re: Generator of a group"
 In reply to: Tobias Ruske: "Re: Generator of a group"
 Next in thread: MokKong Shen: "Re: Generator of a group"
 Reply: MokKong Shen: "Re: Generator of a group"
 Reply: Kristian Gjøsteen: "Re: Generator of a group"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: 6 Jan 2005 12:13:44 0800
In article <41dd6080$0$1562$9b4e6d93@newsread4.arcoronline.net>,
Tobias Ruske <tobias.ruske@arcor.de> wrote:
>the next problem is:
>I search the generator of the group of quadratic residues for a prime p
>and p is a 1024bit value.
>The group of quadratic residues has the order n = (p1)/2, right? Now I
>need the prime factorization of n (see HAC 4.80). But n is a 1023bit
>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 p1, 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, FIPS1862. Or construct it such that
(p1)/2 is prime. Or just try to factor p1, 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
luck.
Greg.
 Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C Qualcomm Australia: http://www.qualcomm.com.au
 Next message: Xcott Craver: "Re: Solution for safe internet based evoting"
 Previous message: MokKong Shen: "Re: Generator of a group"
 In reply to: Tobias Ruske: "Re: Generator of a group"
 Next in thread: MokKong Shen: "Re: Generator of a group"
 Reply: MokKong Shen: "Re: Generator of a group"
 Reply: Kristian Gjøsteen: "Re: Generator of a group"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
