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