Re: REPOST: Arithmetic Problem

From: Gordon (gongz_at_00172.com)
Date: 10/29/05

  • Next message: Douglas Eagleson: "Re: 3 SAT instance generator from DES" 
    Date: 29 Oct 2005 04:08:43 -0700

    John McKormick wrote:
    > Hi, I have some troubles solving this problem. It would be nice if
    > someone can help me.
    > Thanks.
    >
    > let a,b,p,q 4 prime numbers
    > let n = a*b
    > c2 is a constant
    > and c1 = c2 ^ x (mod n) (1)
    >
    > a,b are large numbers.
    > p is 24bits.
    > q is 40bits.
    > x is 64bits.
    >
    > Za* is the multiplicative group (Za-{0},*)
    > Zb* is the multiplicative group (Zb-{0},*)
    >
    > order of c1 in Za* is p
    > order of c2 in Za* is p
    > order of c2 in Zb* is q
    >
    > That's to say, you have :
    >
    > c1 ^ p = 1 (mod a)
    > c2 ^ p = 1 (mod a)
    > c2 ^ q = 1 (mod b)
    >
    > The problem I have is to find x in (1)
    >
    > Regards,
    > J. McKormick
    >
    > PS: Excuse me for my poor english, it is not my native language.
    >
    --------------------------------------------------------------------
    I think this problem maybe can calculate in this way:
    Since c1 = c2^x mod n, and n=a*b, a,b are prime number
    Then with CRT, we get
      c1 = c2^x mod a
      c1 = c2^x mod b
    As
      c1 ^ p = 1 (mod a)
      c2 ^ p = 1 (mod a)
      c2 ^ q = 1 (mod b)
    So we only need search x's value in the set s={x|1<x<q}
    Because we need an x in 64bit
      x = k(a-1)(b-1) + x

    Since q is 40bit, it's possible to do this job

  • Next message: Douglas Eagleson: "Re: 3 SAT instance generator from DES"
    • Quantcast