Cryptography Reference
In-Depth Information
TABLE 13.1
2
b
3
b
4
b
5
b
6
b
1
1
1
1
1
1
2
4
1
2
4
1
3
2
6
4
5
1
4
2
1
4
2
1
5
4
6
2
3
1
6
1
6
1
6
1
All operations done mod 7;
Inr is retained
13.1
ORDER OF AN INTEGER
Definition
Let
n
z
be a positive integer and b an integer. Then the least positive integer
for which
b
z
n
b
n
b
1 (mod
) is called the order of
modulo
. We denote this as |
|
n
. If the modulus
n
b
is clear from the context, we simply write |
|.
E
XAMPLES
.
From the previous table, we see that
|2|
7
= 3, |3|
7
= 6, |4|
7
= 3, |5|
7
= 6, and |6|
7
= 2.
Using this property, we can derive the following propositions:
PROPOSITION 37
If
p
is prime and
b
an integer such that
p
b
, then
x
b
x
p
b
x
a) the positive integer
is a solution to
1 (mod
) iff |
|
p
divides
.
b
p
b) |
|
p
divides
1.
Proof.
a) Suppose |
b
| divides
x
; then
x
=
k
|
b
| for some positive integer
k
. Thus,
b
x
=
b
k
|
b
|
= (
|
b
|
)
k
b
1 (mod
p
).
b
x
On the other hand, suppose
1 (mod
p
). Then, if
x
=
q
|
b
| +
r
0
≤
r
< |
b
|
Search WWH ::
Custom Search