Cryptography Reference
In-Depth Information
mod 2
k
+
1
≡
(
)
=
...
2.1 and so
p
i
1
for each
i
1
j
, from which it follows that
mod 2
k
+
1
. Therefore 2
k
+
1
≡
(
)
|
−
<
n
1
n
1, which implies that
k
s
and hence that
n
−
1
Z
n
:
m
|
. Let us now consider the following subsets of
2
∈ Z
n
|
b
n
−
1
J
={
b
≡
1
(
mod
n
)
}
,
mod
p
e
i
i
∈ Z
n
|
b
m
K
={
b
≡±
1
(
)
for all
i
=
1
...
j
}
,
∈ Z
n
|
b
m
L
={
b
≡±
1
(
mod
n
)
}
,
∈ Z
n
|
b
m
M
={
b
≡
1
(
mod
n
)
}
.
Z
n
and, since
m
n
−
1
Each of these subsets is a subgroup of
|
, we have the following
2
chain of subgroups:
Z
n
.
M
⊆
L
⊆
K
⊆
J
⊆
, then either
b
t
Next we show that
S
(
n
)
⊆
L
. Indeed, if
b
∈
S
(
n
)
≡
1
(
mod
n
)
,
in which case we have that also
b
m
≡
1
(
mod
n
)
(since
m
is a multiple of
t
)
L
,or
b
2
i
t
and hence
b
∈
≡−
1
(
mod
n
)
for some
i
,0
≤
i
<
s
. In this case
b
2
k
t
k
and hence
b
m
Z
n
we have that
i
≤
≡
(
mod
n
)
is a power of
−
1in
so
that we also have
b
m
≡±
1
(
mod
n
)
and hence
b
∈
L
. Now, since
S
(
n
)
⊆
L
,it
Z
n
suffices to show that the index of
L
in
is at least 4, for then we will have that
|≤|Z
n
|
/
|
S
(
n
)
|≤|
L
4
=
φ(
n
)/
4.
mod
p
e
i
i
∈ Z
n
|
Now let
G
={
b
b
≡±
1
(
)
for all
i
=
1
...
j
}
which is clearly a
mod
p
e
i
i
Z
n
. There are 2
j
systems of congruences
x
subgroup of
j
(where
j
is the number of distinct prime factors of
n
) and, by the Chinese remainder
theorem, each of them corresponds to an element of
G
so that
≡±
1
(
)
,
i
=
1
...
2
j
. Moreover,
|
G
|=
b
m
mod
n
for all
b
the function
f
:
K
→
G
defined by
f
(
b
)
=
∈
K
is a group
homomorphism and it is clear that Ker
f
=
M
. Next we show that
f
is surjective. Let
∈ Z
n
by setting
b
∈
G
and, using the Chinese remainder theorem, define an element
c
mod
p
e
i
i
mod
p
e
i
i
mod
p
e
i
i
mod
p
e
i
i
a
2
c
≡
a
(
)
if
b
≡−
1
(
)
and
c
≡
(
)
if
b
≡
1
(
)
,for
Z
n
that satisfies
a
2
k
=
,...,
≡−
(
))
all
i
1
j
(where
a
is an element of
1
mod
n
. Then
c
2
k
mod
p
e
i
i
c
2
k
t
mod
p
e
i
i
j
and hence also
c
m
≡
b
(
)
for all
i
=
1
,...,
≡
≡
b
(
)
(since
t
is odd). From this it follows that
c
m
,
proving that
f
is surjective. Now, using Proposition 2.7 we obtain the index of
M
in
K
which is
≡
b
(
mod
n
)
and hence that
b
=
f
(
c
)
2
j
. On the other hand, we also have
(
:
)
=|
/
|=|
|=
K
M
K
M
G
b
m
mod
n
. It is clear
:
→{−
,
}
→
a surjective homomorphism
g
L
1
1
given by
b
b
m
that Ker
g
={
b
∈
L
|
≡
1
(
mod
n
)
}=
M
, so that, again by Proposition 2.7,
M
=
{−
2
j
−
1
.
L
/
1
,
1
}
and
(
L
:
M
)
=
2. Therefore,
(
K
:
L
)
=
Z
n
2
j
−
1
Suppose now that
j
≥
3. Then we have that
(
:
L
)
≥
(
K
:
L
)
=
≥
4
Z
n
:
and we are done. Thus it remains to show that
(
L
)
≥
4 also when
j
≤
2.
2 then, by Korselt's criterion (Theorem 6.5),
n
cannot be a Carmichael
number. Thus there exists
b
If
j
=
∈ Z
n
such that
b
n
−
1
≡
1
(
mod
n
)
, which implies that
Z
n
and hence that
(
Z
n
J
is a proper subgroup of
:
J
)
≥
2. Since
(
J
:
L
)
≥
(
K
:
2
j
−
1
(
Z
n
)
=
(
Z
n
L
)
=
=
2 we have that
:
L
:
J
)(
J
:
L
)
≥
4 and we are done in
this case.
