Cryptography Reference
In-Depth Information
where
M
i
=
M
/
m
i
and
y
i
is an inverse of
M
i
modulo
m
i
∀ i
= 1, 2, . . . ,
n
.
2
Proposition 28.
If
p
is an odd prime and
p ≠ a
, then the congruence
x
a
(mod
p
)
has either no solutions or exactly two incongruent solutions modulo
p
.
Proposition 29. (Fermat's Little Theorem.)
Let
p
be prime and
b
an integer
b
p
1
such that
p
b
. Then
1 (mod
p
).
Proposition 30.
p
a
Let
be a prime congruent to 3 modulo 4, and
an integer such that
p
a
x
2
a
p
x
a
(
p
1)/4
(mod
p
. Then if the congruence
(mod
) has solutions, they are
),
x
a
(
p
1)/4
(mod
p
and
).
Proposition 31.
Let
n
=
pq
where
p
and
q
are primes congruent to 3 modulo 4, and let
a
be an integer such that 0 <
a
<
n
. Suppose the equation
x
2
a
(mod
n
) has a solution. Then
all the solutions are given by
x
(
zqq
p
wpp
q
) (mod
n
)
where
z
=
a
(
p
1)/4
,
w
=
a
(
q
1)/4
,
q
p
is an inverse of
q
modulo
p
, and
p
q
is an inverse of
p
mod-
ulo
q
.
Proposition 32.
Let
n
=
pq
, where
p
and
q
are primes congruent to 3 modulo
n
. Sup-
pose
a
is an integer relatively prime to
n
, and that the congruence
2
+
ax
bx
+
c
0 (mod
n
)
has a solution. Then all the solutions are given by
)
2
))
(
p
1)/4
)
2
))
(
q
1)/4
x
(
(
a
((2
b
ac
2
ab
)
qq
p
+ (
(
a
((2
b
ac
2
ab
)
pp
q
(mod
n
).
Proposition 33.
There are infinitely many primes of the form 4
k
+ 3.
Proposition 34.
p
x
2
p
x
p
Let
be prime, and suppose
1 (mod
). Then
1 (mod
) or
x
p
1 (mod
).
Proposition 35.
If
n
is prime and
b
is a positive integer such that
n
b
, then
n
passes
Miller's test for the base
b
.
Proposition 36.
Suppose
n
is an odd, composite positive integer. Then
n
fails Miller's
test for at least 75 percent of the test bases
b
where 1
≤ b ≤ n
1.
Proposition 37.
If
p
is prime and
b
an integer such that
p
b
, then
b
x
a.
the positive integer
x
is a solution to
1 (mod
p
) iff |
b
|
p
divides
x
.
b.
|
b
|
p
divides
p
1.
Proposition 38.
Suppose
p
is prime and
b
an integer such that
p
b
. Then, if
i
and
j
b
i
b
j
(mod
are nonnegative integers,
p
) iff
i
j
(mod |
b
|
p
).
Search WWH ::
Custom Search