Greetings,

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)

OR

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.