RSA

[Geliriell]

Kod algoritama za faktorizaciju n-a iz poznavanja d-a, imamo jednostavan algoritam uz pretpostavku ed < n^(3/2) i 2 < p < q < 2p.
Bi li mi netko mogao raspisati dokaz da je fi(n) > n/2?
(U knjizi je to stranica 107)

[duje]

fi(n)=(p-1)(q-1)=n+1-p-q.
p < sqrt(n);
q^2 < 2pq =2n, pa je q< sqrt(2n).
Dakle, p+q < (1+sqrt(2))*sqrt(n) < n/2,
pa je f(n) > n+1 -n/2 >n/2.
(Nejednakost (1+sqrt(2))*sqrt(n) < n/2 je zadovoljena za n>24, a jedini n<24 koji je trazenog oblika je n=15, i za njega se direktno provjeri da je fi(15)=8 > 15/2.)

[Geliriell]

Puno hvala profesore.