Composite degree residues

• Jul 15th 2012, 04:30 PM
mrproper
Composite degree residues
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 $Z_{n^2}^*}$. It's not (directly) mentioned in the text but this is the multiplicative group of integers modulo n $n^2$. As wikipedia says: blah-blah - the congruence classes modulo $n^2$, relative prime to n form an abelian group.

Example: $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)
$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 $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 $\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 $\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 $n^2$ if there exists a number $y \in Z_{n^2}^*$ such that
$z=y^n\ mod\ n^2$"
Had not idea what this means, so I tried to do examples:
Started with
$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 $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 $y\inZ_{n^2}^*$ of order $\phi(n)$"
$\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 $\phi(6)=2$

So either

"The set of n-th residues is a multiplicative subgroup of $Z_{n^2}^*$ of order $\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.
• Jul 19th 2012, 01:12 AM
Deveno
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.
• Jul 22nd 2012, 08:39 AM
mrproper
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}. $\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.