-
8/16/2019 Apresentacao Tenani
1/55
-
8/16/2019 Apresentacao Tenani
2/55
-
8/16/2019 Apresentacao Tenani
3/55
-
8/16/2019 Apresentacao Tenani
4/55
m ≥ a b
m m | (a − b )
a
b
m
a ≡ b (mod m)
m (a − b )
a ≡ b (mod m)
≡
(mod
)
≡ (mod )
(
|(
−
) =
-
8/16/2019 Apresentacao Tenani
5/55
m ∈ Z m
a
a ≡ a(mod m)
a
b
a ≡ b (mod m)
b ≡ a(mod m)
a
b
c
a ≡ b (mod m)
b ≡ c (mod m)
a ≡ c (mod m)
m
Z
m
Zm
· · · ≡ −
≡ −
≡
≡
≡
. . . (mod
)· · · ≡ −
≡ −
≡
≡
≡
. . . (mod )
· · · ≡ − ≡ −
≡
≡
≡
. . . (mod
)
· · · ≡ − ≡ −
≡
≡
≡
. . . (mod
)
· · · ≡ − ≡ − ≡ ≡
≡ . . . (mod )
-
8/16/2019 Apresentacao Tenani
6/55
a b c m
m > a ≡
b (mod m)
a + c ≡ b + c (mod m)
a − c ≡ b − c (mod m)
ac ≡ bc (mod m)
≡ (mod )
=
+
≡
+
=
(mod
)
= − ≡ −
= (mod )
=
× ≡ × =
(mod )
-
8/16/2019 Apresentacao Tenani
7/55
a, b , c , m ∈ Z
c = m >
mdc (c , m) = d
ac ≡ bc (mod m)
a ≡ b (mod m
d )
= × ≡ =
× (mod )
mdc ( , ) =
×
≡ ×
(mod
), ≡ (mod
).
a, b , c , m ∈ Z
c = m >
mdc (c , m) =
ac ≡ bc (mod m)
a ≡ b (mod m)
-
8/16/2019 Apresentacao Tenani
8/55
ax ≡ b (mod m),
x ∈ Z
x ≡
(mod
)
-
8/16/2019 Apresentacao Tenani
9/55
a, b , m ∈ Z
m >
mdc (a, m) = d
d b
ax ≡ b (mod m) d |b
ax ≡ b (mod m) d
m
x i = x
+ m
d ×,
x
x ≡
(mod
)
mdc (
,
) =
|
x
=
x
= +
× = ,
x
= +
×
=
,
x
= +
×
=
,
x =
+
×
= .
-
8/16/2019 Apresentacao Tenani
10/55
a mdc (a, m) =
ax ≡ (mod m)
a
m
x ≡ (mod )
x ≡ (mod
),
-
8/16/2019 Apresentacao Tenani
11/55
×
a, b , c , d , e , f ,
m ∈ Z m >
mdc (∆, m) = ∆ = ad −
bc =
ax + by ≡ e (mod m)
cx + dy ≡ f (mod m)
m
x ≡ ∆̄(de −
bf )(mod m)
y ≡ ∆̄(af − ce )(mod
m),
∆̄
∆
m
-
8/16/2019 Apresentacao Tenani
12/55
×
x +
y ≡
(mod
)
x +
y ≡
(mod
)
.
∆ = ad − bc =
×
−
×
=
mdc (∆, m) = mdc ( ,
) =
x ≡ × (de − bf )
=
× (
.
−
.
) = −
≡
(mod
)
y ≡ × (af − ce )
= × ( . − .
) = ≡ (mod
).
-
8/16/2019 Apresentacao Tenani
13/55
-
8/16/2019 Apresentacao Tenani
14/55
-
8/16/2019 Apresentacao Tenani
15/55
f P
C
f
f −
f
P f −→ C
f −
−−→ P
-
8/16/2019 Apresentacao Tenani
16/55
A, B , . . . Z , ,
. . .
P ∈ { ,
,
, . . .
}
f
{ , , , . . .
}
f (P ) = P +
, x <
,
P − , x ≥
,
,
.
-
8/16/2019 Apresentacao Tenani
17/55
f − (P ) =
P − , x
< ,P +
,
x ≥
.
-
8/16/2019 Apresentacao Tenani
18/55
f
C = f (P ) ≡
P + b (mod m).
C ∈ {
,
, . . . , m −
}
P = f − (C ) ≡
C − b (mod m).
-
8/16/2019 Apresentacao Tenani
19/55
-
8/16/2019 Apresentacao Tenani
20/55
-
8/16/2019 Apresentacao Tenani
21/55
C = f (P ) ≡
P + b (mod m)
P = f − (C ) ≡
C − b (mod m).
.
b
≡
+ b (mod
),
b =
QHGKYCUTUI =
→ = ARQUIMEDES
-
8/16/2019 Apresentacao Tenani
22/55
f
C ≡ aP + b (mod m),
a
b
a =
b =
C ≡
P +
(mod
),
ARQUIMEDES =
→
= MBUWQSOHOI
-
8/16/2019 Apresentacao Tenani
23/55
n
-
8/16/2019 Apresentacao Tenani
24/55
A
B
n × k
Z
A
B
m aij ≡ b ij (mod m)
≤ i ≤ n
≤ j ≤ k A
B
m
A ≡ B (mod m),
A ≡ B (mod m).
≡ −
(mod ).
-
8/16/2019 Apresentacao Tenani
25/55
a
x
+ a
x
+ . . . a
nx n ≡ b
(mod m)
a
x
+ a
x
+ . . . a nx n
≡ b (mod m)
. . . . . . . . . . . .
. . . . . . . . . . . .
an x + an
x + . . . annx n
≡ b n(mod m)
n
AX ≡ B (mod m),
A =
a
a
. . . a
n
a
a
. . . a n
: : : :
an
an
. . . ann
, X =
x
x
:
x n
B =
b
b
:
b n
.
-
8/16/2019 Apresentacao Tenani
26/55
A Ā n × n
AĀ ≡ ĀA ≡ I (mod m),
I
n
Ā
A
=
≡
(mod
)
=
≡
(mod
)
-
8/16/2019 Apresentacao Tenani
27/55
A
n × n
Z
m ∈ Z
mdc (∆, m) = ∆
Ā = ∆̄Adj (A)
A
m
∆̄
∆
m
A =
a b
c d ∆ = detA =
ad − bc
m
Ā = ∆̄
d −b −c a
∆̄
∆
m
-
8/16/2019 Apresentacao Tenani
28/55
A =
.
∆ = −
mdc (∆, ) =
∆̄ =
Ā = (adj (A)) =
− − −
−
≡
(mod ).
A
m
AX ≡ B (mod m),
X = ĀB (mod m)
-
8/16/2019 Apresentacao Tenani
29/55
n
n
E n×n
, , , . . . m −
m
n
-
8/16/2019 Apresentacao Tenani
30/55
E n×n
m
m −
t
n
p i n ×
E
p
, p
, . . . , p t
c
= Ep
, c
= Ep
, c
= Ep
, . . . ,
c t = Ep t
c
, c
, . . . , c t
-
8/16/2019 Apresentacao Tenani
31/55
E =
.
detA = − ≡ (mod
)
PASCAL.
.
-
8/16/2019 Apresentacao Tenani
32/55
.
P
×
P =
.
E
P
C = EP =
.
≡
(mod
).
−→ EBQMHK .
-
8/16/2019 Apresentacao Tenani
33/55
D = Ē (mod m)
C
P = DC
P
-
8/16/2019 Apresentacao Tenani
34/55
(mod ) =
C
AJXGTRJXDGKKIXL
-
8/16/2019 Apresentacao Tenani
35/55
C =
P = DC =
P
→
TEORIADOSNUMEROS →
.
-
8/16/2019 Apresentacao Tenani
36/55
C = EP
C
P
P
C = EP
E = C P
E
D
n
-
8/16/2019 Apresentacao Tenani
37/55
CRIPTOGRAFIAELEGAL.
n =
n =
-
8/16/2019 Apresentacao Tenani
38/55
n =
n =
→
.
→
→
,
→
,
−→
, . . .
-
8/16/2019 Apresentacao Tenani
39/55
n =
×
P =
det (P ) = −
P
-
8/16/2019 Apresentacao Tenani
40/55
P
P =
det (P ) = −
≡
(mod
)
= E
E =
(mod
) =
-
8/16/2019 Apresentacao Tenani
41/55
CRIPTOGRAFIAELEGAL.
P =
,
C = EP =
.
-
8/16/2019 Apresentacao Tenani
42/55
n =
E
×
C = EP
= E
.
×
P =
,
-
8/16/2019 Apresentacao Tenani
43/55
P =
.
det (P )(mod
) =
= E
.
E =
−
(mod ) =
.
-
8/16/2019 Apresentacao Tenani
44/55
=
-
8/16/2019 Apresentacao Tenani
45/55
-
8/16/2019 Apresentacao Tenani
46/55
-
8/16/2019 Apresentacao Tenani
47/55
mdc (∆, m)
¯∆
-
8/16/2019 Apresentacao Tenani
48/55
E
-
8/16/2019 Apresentacao Tenani
49/55
E
-
8/16/2019 Apresentacao Tenani
50/55
-
8/16/2019 Apresentacao Tenani
51/55
E
−→
−→
-
8/16/2019 Apresentacao Tenani
52/55
E
P
C
−→
-
8/16/2019 Apresentacao Tenani
53/55
-
8/16/2019 Apresentacao Tenani
54/55
-
8/16/2019 Apresentacao Tenani
55/55
