Re: Generator of a group

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 01/06/05 

Date: 6 Jan 2005 12:13:44 -0800

In article <41dd6080$0$1562$9b4e6d93@newsread4.arcor-online.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 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
luck.

Greg. 

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au

Relevant Pages

  • Re: Big Prime number prolem.
    ... it is insufficient to generate random primes ... p-1, it is impossible to determine if g, the generator does in fact ... full factorization of p-1 via their construction. ...
    (sci.crypt)
  • Re: Generator of a group
    ... Any generator of the multiplicative group must either be: ... P is prime, so it's odd, so p-1 is ... I know that you usually argue for argument's sake, ... Greg Rose ...
    (sci.crypt)
  • Re: Generator of a group
    ... >>I search the generator of the group of quadratic residues for a prime p ... >>value and it's hard to find the factorization for such a big ... prime factors of p-1 (elliptic curve factoring will do it with high ... Except with small probability, ...
    (sci.crypt)
  • Re: Easy test of surrogate factoring
    ... > Now I've accused some posters of lying, ... If you have an algorithm that claims to do factorization, ... There is no such thing as a "random number generator", ...
    (sci.math)
  • Re: Easy test of surrogate factoring
    ... > Now I've accused some posters of lying, ... If you have an algorithm that claims to do factorization, ... There is no such thing as a "random number generator", ...
    (sci.crypt)