Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By Deveno

Thread: Composite degree residues

  1. #1
    Apr 2011
    Somwhere in cyberspace.

    Composite degree residues


    I'm trying to read a report on cryptography - "Public-key Cryptosystems Based on Composite Degree Residuosity Classes", authored by Pascal Paillier and presented on EUROCRYPT'99.
    And I'm definitely unprepared. I have almost no knowledge of number theory beyond some elementary results (say the ones that concern RSA). But I've recently read a big nasty book on abstract algebra, so I know what group and ring are and so I gave it a try.
    The problem with the report (or more exactly with the online version I got) is that it starts simple enough but out of nowhere it states something that I do not understand and moreover either I failed to get the point completely or it's not completely true. Latter is impossible, since this is very seminal paper from very serious scientist.
    So I need someone to check me up, if possible.

    The report starts with discussion of the group $\displaystyle Z_{n^2}^*}$. It's not (directly) mentioned in the text but this is the multiplicative group of integers modulo n $\displaystyle n^2$. As wikipedia says: blah-blah - the congruence classes modulo $\displaystyle n^2$, relative prime to n form an abelian group.

    Example: $\displaystyle Z_{5^2}^*$ is isomorphic to {1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23, 24} under multiplication (the numbers are coprime with 25)
    $\displaystyle Z_{6^2}^*$ is isomorphic to {1,5,7,11,13,17,19,23,25,29,31,35} under multiplication (the numbers are coprime with 36)
    Not sure I can prove the group axioms, but for now I'm willing to take it as it is. The identity is obvious, I did some examples regarding if this sets are indeed closed under multiplication modulo $\displaystyle n^2$ and they didn't contradict that.

    Say 4 x 11 x 18 x 23 mod 25 = 16
    And so on ...

    The order of these groups is equal to $\displaystyle \phi(n)n$ where the phi thingie is the Euler's totient function. It's multiplicative so if n=pq and p,q are prime, which is exactly what the Paiilier cryptosystem provisions, then $\displaystyle \phi(n^2)=\phi(p^2q^2)=\phi(p^2)\phi(q^2)=(p^2-p)(q^2-q)=pq (p-1)(q-1)=n\phi(n)$

    This gets us (somehow) trough section 1 "Background".
    Now section 2 on page 3 - "Deciding Composite Residuosity" starts with definition:

    "Definition 1. A number z is said to be a n-th residue modulo $\displaystyle n^2$ if there exists a number $\displaystyle y \in Z_{n^2}^*$ such that
    $\displaystyle z=y^n\ mod\ n^2$"
    Had not idea what this means, so I tried to do examples:
    Started with
    $\displaystyle y\inZ_{n^5}^*$ and calculated
    The way formula is given there are only two types of group members - the ones that are 5-th residues modulo $\displaystyle 5^2$ and the ones that aren't.
    List of 5-th residues mod 25
    1^5 = 1 mod 25
    2^5 = 7 mod 25
    3^5 = 18 mod 25
    4^5 = 24 mod 25
    6^5 = 1 mod 25
    7^5 = 7 mod 25
    8^5 = 18 mod 25
    9^5 = 24 mod 25
    and they repeat

    so the set of 5-th residues mod 25 is {1,7,18,24} and they are closed under multiplication mod 25.

    7x18 mod 25 = 1
    7x24 mod 25 = 18
    18x24 mod 25 = 7

    The report said just that right after the definition:

    "The set of n-th residues is a multiplicative subgroup of $\displaystyle y\inZ_{n^2}^*$ of order $\displaystyle \phi(n)$"
    $\displaystyle \phi(5)=4$ So everything fits nice perfectly.

    Then I remembered that the report talked about non-prime n. So p=2 q=3 n=6. But....

    List of 6-th residues mod 36
    1^6 = 1 mod 36
    5^6 = 1 mod 36
    7^6 = 1 mod 36
    11^6 = 1 mod 36
    13^6 = 1 mod 36
    17^6 = 1 mod 36
    everything ^6 = 1 mod 36

    So the order of the subgroup = 1 and $\displaystyle \phi(6)=2$

    So either

    "The set of n-th residues is a multiplicative subgroup of $\displaystyle Z_{n^2}^*$ of order $\displaystyle \phi(n)$"

    is not correct (it's correct for 5 and 7 (all the primes i tried before burning out the MOD function in Excel) and seems incorrect for 6 and 8)


    With the bare minimum of knowledge, I'm completely wrong and you just had a great laugh ;-). In any case, any help will be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Mar 2011

    Re: Composite degree residues

    i believe the paper you are reading is incorrect. although U(36) has φ(36) = 12 elements, it is of exponent 6, meaning the 6-th residues are all trivial.

    of course the next n to try would be 15, and U(225) has 120 elements, which is a bit more work than i'm prepared to go through, at the moment.
    Thanks from mrproper
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Apr 2011
    Somwhere in cyberspace.

    Re: Composite degree residues

    With some custom-made excel functions for exponentiation modulo n, U(225) seems to be very easily doable. The set of 15-th residues modulo 225 is
    {1,143,199,118,107,26,82,224}. $\displaystyle \phi(15)$. Still haven't finished the report, but so far it seems that the fact in question is not used anywhere....
    Thanks for the check.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Nov 18th 2011, 04:38 PM
  2. Replies: 4
    Last Post: Apr 7th 2011, 10:08 AM
  3. residues
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: May 7th 2010, 05:18 AM
  4. About sum of residues
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: May 18th 2009, 11:54 AM
  5. residues 2
    Posted in the Calculus Forum
    Replies: 4
    Last Post: Feb 10th 2009, 08:19 AM

Search Tags

/mathhelpforum @mathhelpforum