1 1
- , , () ( ) , , ( ) (-22487-77). , . .1.
. 1.
, , - , , , . , / - , - .
1 2
́ ́ .
. , .
ø , , , , . , , .
́ ø ́ ́ ́ ø [~ 1] , , , : , 0, 1, .
, , .
, , , .
ø 1930 ( 1931) .
- 1 ;
- , , ;
- 1 ;
- , , ;
- ( ) - 1 ( ) , , , ( ), .
|
|
, .
- ;
- ;
- ;
- ;
- .
:
- ;
- ;
- ;
- .
, .
- 1 ;
- ;
- 1 ;
- ;
- .
, 0 :
2 1
2 1
2 2
́ ́ ́ :
n > 1 , , .
, .
, n
, .
n .
.
:
p , p x y. |
. n , . . , . n , . , , n . .
. n , . . , p . p , p n / p, . p , p, ( , . ), .
́ ́ ́ ( ) ; , . 1995 .
, :
n > 2 a, b c. |
|
|
́ ́ ́ , ,
p , a p, a p − 1 ≡ 1 (mod p) ( a p − 1 − 1 p). |
:
p a, (a p − a) p. |
- p , m n , , . RSA.
- , , , .
- .
́ ́ :
a m , , φ(m) . |
φ(n), n , , n
, , 1.
, . , , π(n) 1 n n , :
, , 1 n .
k - pk: ,
( : ).
3 1
, , , | |||
( ) | |||
, | |||
, | |||
- () |
. 1.
- ( , -, - . .).
- - - (, , , , . .).
- (, , . .).
- ( ) .
- .[. 1]
- ( , ) .
4 1
82
4 2
- , . , . , .
, . () , () . . ,
. . :
|
|
- , .
- () .
- ( ).
,
- , - , ( ) - ;
- , .
, , () , .
, ( , ):
,
abbc , :
, , ( ), .
2. , , , , . "*". , , 2 : , , . "!", , . 0 "a", 1 - "b". "a" "b" , "a" "b" ( "*"), , , "!" "?", . "a" "b", 0 1 . :
10:
5 1
84
6 1
(). . , ( ). , , , , . , , . , , , .. .
|
|
, . . . , . . , . ( ) , , . MENTOR GRAPHICS .
, , , , -- (System-on-Package, SiP) (silicon compiler, SC ). , . exe- , . , -, , . , , SC. 1984. . (Mead) . .., .. . 2000. SC.
1979 . , . , -, , -, . , . , , . , .
6 2
G () (), . .
n - G n . , 0 - . , . , , , ( ) ( ).
|
|
, ,
, .
, , a b.
.
, , .
, : .
.
, a a −1, , .
, , , . ('+').
, .
- , ( )
: , , : .
.
, .
, .
, .
́ , . . , . . , , .
G (G, *), :
1. : ;
2. : ;
3. :
]
a − 1, a, .
2- 3- :
. () () . e a − 1:
́ F + ( , ) ( , ), ( ) c , .
, F + () () , , , .
n , n :
, 0 .
k , , k. ( k , k, k)
, .
, .
, .
0 .
0 , .
p , .
pn .
pn ( ) pn , .
.
.