, . .
.
, ( ), . .
( - " " "-" hashing to hash ).
, . . - F(p) .
. 30- . , 23 , . , , 23 365, , , 0,4927, .. . , Pi ¹ Pj F(pi)=F(pj). . .
- f(p) .
i= f(p),
i () ;
- .
f :
;
, , ; ;
- 10-20% .
-.
, - ,
0 <=F(p) < . (1)
, . :
i=-, - .
' ". = ' - 1. " - ' +1 . - , () .
|
|
13,11,14,11,15,18, 14,16 i = - . 6.1
Æ | Æ | Æ | Æ |
. 6.1. i = -
q i= f(q) i- . .
i = - - , "- ' , .
, -, (c).
- , . ( ). , - (, ).
, , . , = 1000 f(p) , - . 000 999 ; , " , .
, , .
;
i= (/m). (2)
m - ; - m.
i , i = p mod m. ( )
m , .
, , F {p) p , . , , p mod p, , . , , , , 3 ( , 22n mod 3 = 1 10n mod 3 =1). , , rk , k , " " - ( r = 64, 256 100), . , , , rk ¹ ( ) k . .
|
|
. , m .
2 - . m . .
. , , , . .
, 17, 9, 4, 14, 25, 21, 20, 11 m=7, =8 ( m=19). . . , =11, i = (11/7)=4, 4 11, 25 11 .. - 3/8.
, , , . w [6]. A/w, , (, , -1 ) . , w,
F(p) = [M((A/p)mod 1) ]. (3)
, F(p) A*
F(p) . .
, (2), , , w/M; . (3) , : , .
(3); p (3). , w ', , ' mod w = 1; , p = (A'(A.pmod w)) mod w. , F(p) ,
1¹2 h(1) ¹ h(2) (4)
, h(p) 0 w-1, - -. (scrambling function), . . , (4) . ( ), .
- , . , , {, +d, +2d,..., +td}. , {PART1, PART2, PART3} {TYPEA, TYPEB, TYPEC}. -
|
|
f{K), f{K + d), f(K + 2d),... -, . . .
. 37 . , A/w f -1 = (Ö5- l)/20.6180339887;
f(P), f(P + 1), f(P +2),... , - f(0), f(l), f(2),..., : [0..1] {f-1},{2f-2}, {3f-3},.... {} (.. - ½ ½ mod 1) .37, !
, (Hugo Stein haus) (Vera Turan Sos)
S. q . {q }, {2 q },..., {q } [0..1] n + 1 . , {(+1) q } .
, {q }, {2 q },..., {q } 0 1 . q - , ( , n, q). S[7]
, f-1w , w. ,
(7)
LIST1, LIST2, LIST3. - , SUMl_, SUM2_,SUM3_ - , , S q = {100/w} =.80339887 q =. 6180339887 = A/w. , q=f-1, . Al___ A2___, A3___ - q 0.9887, , , 1.
(7); , . , , rk1.. XY YX ! S. q . " . , q
, "" ( ),
. ( - . (R. W. Floyd).)
|
|
- .
a) .
b) .
() , (b) . , -; (b) , .