Phơng pháp tính toán chỉ số
Phơng pháp tính toán chỉ số khá giống với nhiều thuật toán phân tích thừa số tốt
nhất. Trong phần này sẽ xét tóm tắt về phơng pháp. Phơng pháp này dùng một cơ
sở phân tử là một tập chứa các số nguyên tố nhỏ. Giả sử = { p
1
, p
2
, , p

} Bớc
đầu tiên ( bớc tiền xử lý ) là tìm logarithm của B số nguyên tố trong cơ sở phần tử
bằng cách dùng hiểu biết về các log của phần tử trong cơ sở.
Trong quá trình tiền xử lý, ta sẽ xây dựng C = B + 10 đồng d thức theo
modulo p nh sau:
1 j C. Cần để chú ý rằng, các đồng d này có thể viết tơng đơng nh sau:
X
j
a
1j
log

p
1
+ + a
Bj
log

p
B
( mod p - 1)
1 j C. C đồng d thức đợc cho theo B giá trị log

p
2
c2
p
B
cb
( mod p)
Điều đó tơgn đơng với

log

+ s c
1
log

p
1
+ + c
B
log

p
B
(mod p -1)
vì mọi giá trị đều đã biết trừ giá trị log

nên có thể dẽ dàng tìm đợc log

.
Sau đây là một ví dụ nhỏ minh hoạ 2 bớc của thuật toán.

ta tìm đợc hai đồng d thức nữa:
log
5
2 + 3log
5
3 5136 (mod 10006)
3log
5
3 + log
5
7 9865 ( mod 10006)
Bây giờ ta có 3 đồng d thức theo 3 giá trị log cha biết. Giải phơng trình đồng d
này, ta có log
5
2 = 6578, log
5
3 = 6190, và log
5
7 = 1301.
Bây giờ giả sử ta cần tìm log
5
9451, và ta chọn số mũ ngẫu nhiên = 7736 và
tính:
9451 ì 5
7736
mod 10007 = 8400
Vì 8400 = 2
4
3
1