⎔ Сәби адымы - Алып адымы алгоритмі (BSGS)

Бұл алгоритм дискретті логарифм есебін шешу үшін қолданылады:

a^x ≡ b (mod p)

Параметрлерді енгізіңіз:

База (a): Модуль (p): Нәтиже (b):

Нәтиже:

адымыдар:

Алгоритм жұмыс принципі:

m = ⌈√p⌉ есептеу
Сәби адымы: a^j mod p, j = 0...m-1
Алып адымы: b·(a^-m)ⁱ mod p, i = 0...m-1
Сәйкестік табу: a^j ≡ b·(a^-m)ⁱ (mod p)
x = i·m + j формуласы бойынша шешім

Мысал:

2^x ≡ 5 (mod 101)

m = ⌈√101⌉ = 11

Табылған шешім: x = 28

Тексеру: 2²⁸ mod 101 = 5