Fractii continue. Atacul lui Wiener

Fie a si b numere naturale, b 6= 0.

a = q1 · b + r1, 0 < r1 < bb = q2 · r1 + r2, 0 < r2 < r1

r1 = q3 · r2 + r3, 0 < r3 < r2...

rk−2 = qk · rk−1 + rk, 0 < rk < rk−1

rk−1 = qk+1 · rk

(1)

Fractia ab

poate fi scrisa dupa cum urmeaza:

ab

= q1b+r1

b

= q1 + 1b

r1

= q1 + 1q2+ 1

r1r2

...= q1 + 1

q2+ 1

...qk+ 1

qk+1

Ultimul termen va fi referit ca fractia continua asociata fractiei ab

si va fi no-tat prin [q1, q2, . . . , qk+1]. Expresiile [q1, q2, . . . , qi], 1 ≤ i ≤ k + 1, vor fi numiteconvergentele fractiei continue [q1, q2, . . . , qk+1].

Consideram numerele naturale αi si βi date prin

α1 = q1, β1 = 1α2 = q1 · q2 + 1, β2 = q2

αi = qi · αi−1 + αi−2, βi = qi · βi−1 + βi−2,pentru orice 3 ≤ i ≤ k + 1

(2)

Atunci are loc relatia

[q1, q2, . . . , qi] =αi

βi

,

(αi, βi) = 1,

1

pentru orice 1 ≤ i ≤ k + 1.

Exemplul 1 Sa consideram a = 4, b = 11. Vom obtine

4 = 0 · 11 + 411 = 2 · 4 + 34 = 1 · 3 + 13 = 3 · 1

si [0, 2, 1, 3] = 0 + 12+ 1

1+13

, [0] = 01, [0, 2] = 1

2si [0, 2, 1] = 1

3.

Atacul lui WienerFie p si q numere prime astfel ıncat q < p < 2q, si n = p · q. Se aleg1 e, d ∈ Z∗φ(n)

astfel ıncate · d ≡ 1 mod φ(n),

unde φ(n) = (p− 1)(q − 1), si d <4√n3

.Exista l ∈ N astfel ıncat

e · d− 1 = l · φ(n).

Fie [q1, q2, . . . , qk+1] fractia contina asociata fractiei en. Atunci exista 1 ≤ i ≤ k + 1

astfel ıncat [q1, q2, . . . , qi] = ld.

Avand e si n, se pot determina l si d ın felul urmator:

i:=0;repeta

i:=i + 1;determina αi, βi folosind relatiile (1) (pentru a = e si b = n) si (2);l := αi; d := βi;

pana cand criteriu(l, d) = 1

unde

criteriu(l, d) =

{1, daca sistemul

{x · y = n

(x − 1) · (y − 1) = ed−1l

are solutii ıntregi

0, altfel

1In loc de φ(n) se poate pune λ(n), unde λ(n) = [p− 1, q − 1].

2