Лидовский В.В., Теория информации

|E 205 CD 157 9D 221 DD 252 FC 1069 042D |

97

pRILOVENIE d. |LEMENTY TEORII ^ISEL

kANONI^ESKIM RAZLOVENIEM ^ISLA m NAZYWAETSQ RAZLOVENIE EGO NA PROSTYE SOMNOVITELI W WIDE m = p1 1 p2 2 pkk , GDE p1; p2; : : : ; pk | WSE RAZLI^NYE PROSTYE DELITELI ^ISLA m, A 1; 2; : : : ; k | CELYE POLOVITELXNYE ^ISLA.

fUNKCIEJ |JLERA NAZYWAETSQ, OTOBRAVENIE ': N ! N,

'(m) = p1 1 1(p1 1)p2 2 1(p2 1) pkk 1(pk 1);

\TO WESXMA TRUDOEMKIJ SPOSOB. pOLU^IM RE[ENIQ ISKOMOGO URAWNENIQ ^EREZ FORMULU DLQ RE[ENIQ \KWIWALENTNOGO URAWNENIQ ax my = 1.

pO ALGORITMU eWKLIDA DLQ POLU^ENIQ nod DWUH ZADANNYH ^ISEL NUVNO ODNO ^ISLO DELITX NA DRUGOE, ZATEM DELITX DELITELX NA POLU^A- EMYJ OSTATOK DO TEH, POKA OSTATOK NE STANET RAWNYM NUL@. pOSLEDNIJ BOLX[IJ NULQ OSTATOK BUDET ISKOMYM nod.

dLQ ^ISEL a I m POSLEDOWATELXNOSTX [AGOW ALGORITMA eWKLIDA WYGLQDIT KAK

a = mq0 + a1; m = a1q1 + a2; a1 = a2q2 + a3;

: : :

an 2 = an 1qn 1 + an; an 1 = anqn;

a

GDE a1; a2; : : : ; an | OSTATKI. rAZLOVENIE m W CEPNU@ DROBX PO POSLE-

98

oBOZNA^IM ZA Pk=Qk DROBX, POLU^AEMU@ IZ PRIWEDENNOJ CEPNOJ DROBI OTBRASYWANIEM ^LENOW S INDEKSAMI, BOLX[IMI k. nAPRIMER, P0=Q0 = q0, P1=Q1 = q0+1=q1 = (q0q1+1)=q1 I T.D. ~ISLITELX, Pk, I ZNAMENATELX, Qk, MOVNO WY^ISLQTX REKURRENTNO PO SLEDU@]IM FORMULAM:

P 2 = 0; P 1 = 1; Q 2 = 1; Q 1 = 0;

PRI k > 0 Pk = qkPk 1 + Pk 2; Qk = qkQk 1 + Qk 2:

pO OPREDELENI@ Pn = a I Qn = m. kROME TOGO,

Fn = PnQn 1 Pn 1Qn = (qnPn 1+Pn 2)Qn 1 Pn 1(qnQn 1+Qn 2) = = Pn 1Qn 2 +Pn 2Qn 1 = Fn 1 = = Fn 2 = = ( 1)n+1F 1 = = ( 1)n+1(P 1Q 2 P 2Q 1) = ( 1)n+1

ILI

( 1)n+1PnQn 1 Pn 1( 1)n+1Qn = 1;

^TO OZNA^AET

a( 1)n+1Qn 1 m( 1)n+1Pn 1 = 1; T.E. x = ( 1)n 1Qn 1 I y = ( 1)n 1Pn 1.

pROCESS POLU^ENIQ ^ISLITELEJ I ZNAMENATELEJ UDOBNO OFORMITX W WIDE TABLICY:

99

tAKIM OBRAZOM, ISKOMYJ x RAWEN 151925.

gIPOTEZA. zADA^A RAZLOVENIQ CELOGO ^ISLA S ZADANNYM ^ISLOM RAZRQDOW NA MNOVITELI QWLQETSQ TRUDNORE[AEMOJ*.

nA SEGODNQ[NIJ DENX SU]ESTWU@T WESXMA BYSTRYE ALGORITMY DLQ PROWERKI DANNOGO ^ISLA NA PROSTOTU, NO DLQ RAZLOVENIQ 200-ZNA^NOGO ^ISLA NA MNOVITELI LU^[IM SOWREMENNYM KOMPX@TERAM PO LU^[IM SOWREMENNYM ALGORITMAM MOVET POTREBOWATXSQ MILLIARDY LET.

|TA GIPOTEZA LEVIT W OSNOWE METODOW dIFFI-hELLMANA.

* zADA^A NAZYWAETSQ TRUDNORE[AEMOJ, ESLI WREMQ EE RE[ENIQ ZAWISIT OT OB_EMA WHODNYH DANNYH PO \KSPONENCIALXNOMU ZAKONU I NE MOVET BYTX SWEDENO K POLINOMIALXNOMU

100

pRILOVENIE e. iSPOLXZUEMYE OBOZNA^ENIQ

P (A) | WEROQTNOSTX SOBYTIQ A.

P (A=B) | WEROQTNOSTX SOBYTIQ A, ESLI IZWESTNO, ^TO SOBYTIE B PROIZO[LO. uSLOWNAQ WEROQTNOSTX.

P (A; B) | WEROQTNOSTX ODNOWREMENNOGO NASTUPLENIQ SOBYTIJ A I

B.

N | MNOVESTWO NATURALXNYH ^ISEL. Z2 | MNOVESTWO IZ 0 I 1, f0; 1g.

R | MNOVESTWO WE]ESTWENNYH ^ISEL. R2 | ^ISLOWAQ PLOSKOSTX.

i xi | SUMMA xi PO WSEM WOZMOVNYM ZNA^ENIQM INDEKSA i.

k=0

ILI ^ISLO WOZMOVNYH RAZNYH WYBOROK k \LEMENTOW IZ MNOVESTWA IZ n

a b DELITSQ NA n NACELO.

f: A ! B | FUNKCIQ f S OBLASTX@ OPREDELENIQ A I OBLASTX@, SODERVA]EJ WSE ZNA^ENIQ f, B.

f g | KOMPOZICIQ FUNKCIJ f I g, T.E. (f g)(x) = f(g(x)).

(X; +; ) | POLE NAD MNOVESTWOM X S ADDITIWNOJ OPERACIEJ + I MULXTIPLIKATIWNOJ OPERACIEJ .

101

pRILOVENIE v. sPISOK LITERATURY

1.bIRKGOF g., bARTI t. sOWREMENNAQ PRIKLADNAQ ALGEBRA | m.: mIR, 1976.

2.bLEJHER r. tEORIQ I PRAKTIKA KODOW, KONTROLIRU@]IH O[IBKI | m.: mIR, 1986.

3.bORN g. fORMATY DANNYH | kIEW: tORGOWO-IZDATELXSKOE B@RO

BHV, 1995.

4.bUK^IN l. w., bEZRUKIJ `. l. dISKOWAQ PODSISTEMA IBM-SOW- MESTIMYH PERSONALXNYH KOMPX@TEROW | m.: FIRMA \mikap", 1993.

5.wINER n. kIBERNETIKA | m.: nAUKA, 1983.

6.wODOLAZKIJ w. kOMMER^ESKIE SISTEMY [IFROWANIQ: OSNOWNYE ALGORITMY I IH REALIZACIQ //\mONITOR" 6{8/92.

7.wOROBXEW n. n. pRIZNAKI DELIMOSTI | m.: nAUKA, 1988.

8.gLU[KOW w.m. oSNOWY BEZBUMAVNOJ INFORMATIKI | m.: nAUKA, 1987.

9.dVORDV f. oSNOWY KIBERNETIKI | m.: rADIO I sWQZX, 1984.

10.kENCL t. fORMATY FAJLOW Internet | spB: pITER, 1997.

11.nELXSON m. wERIFIKACIQ FAJLOW //\vURNAL D-RA dOBBA" 1/93.

12.nE^AEW w. i. |LEMENTY KRIPTOGRAFII | m.: wYS[AQ [KOLA, 1999.

13.mASTR@KOW d. aLGORITMY SVATIQ INFORMACII //\mONITOR" 7/93{6/94.

14.pITERSON r., u\LDON |. kODY, ISPRAWLQ@]IE O[IBKI | m.: mIR, 1976.

15.pLOTNIKOW w. aLGORITMI^ESKAQ REALIZACIQ KRIPTOGRAFI^ESKOGO METODA RSA //\mONITOR" 2/94.

16.pERSPEKTIWY RAZWITIQ WY^ISLITELXNOJ TEHNIKI: W 11 KN.: sPRAWO^NOE POSOBIE/pOD RED. `. m. sMIRNOWA. kN. 9. | m.: wYS[AQ [KOLA, 1989.

17.tITCE u., {ENK k. pOLUPROWODNIKOWAQ SHEMOTEHNIKA | m.: mIR, 1983.

18.~ISAR i., k•ERNER q. tEORIQ INFORMACII | m.: mIR, 1985.

19.{ENNON k. rABOTY PO TEORII INFORMACII I KIBERNETIKI | m., iZDATELXSTWO INOSTRANNOJ LITERATURY, 1963.

20.qGLOM a., qGLOM i. wEROQTNOSTX I INFORMACIQ | m.: nAUKA, 1973.

21.wWEDENIE W KRIPTOGRAFI@ /pOD OB]EJ REDAKCIEJ w. w. q]ENKO. | m.: mcnmo: "~ErO", 2000.

22.HTML 4.01 Speci cation /Edited by D. Ragget, A. L. Hors, I. Jacobs | W3C: http://www.w3c.org/TR/REC-html401-19991224, 1999.

102

23.The Unicode Standard, Version 3.0 | Addison Wesley Longman Publisher, 2000, ISBN 0-201-61633-5.

103

pRILOVENIE z. pREDMETNYJ UKAZATELX

104

105

106