Ро-метод Полларда для дискретного логарифмирования
Этот алгоритм осуществляет случайный поиск дискретных логарифмов, как и метод «шаг ребенка – шаг великана», но он требует меньшего объема памяти для хранения данных, поэтому предпочтительней для практических целей. В основе данного метода лежит та же идея, что и в основе ро-метода для факторизации – строится псевдослучайная последовательность, в которой находятся совпадающие элементы при помощи метода Флойда, а затем на основании полученной величины вычисляется искомый дискретный логарифм. Пусть требуется вычислить logga в конечной группе G порядка n. Группа G разбивается на три непересекающихся подмножества примерно равной мощности: G=S1US2US3, так чтобы 1 S2. Причем разбиение должно быть построено таким образом, чтобы проверка, к какому подмножеству принадлежит данный элемент x, была простой. Например, если G=Zp, где p – простое число, то можно задать разбиение S1={1,…, }, S2={ ,…, }, S3={ , … , p—1}, или разбиение может быть таким: если x mod 3=1, то x S1, если x mod 3=2, то x S2, если x mod 3=0, то x S3. Далее на G задается последовательность x0, x1, x2, … , где x0=1, xi+1 вычисляется по xi посредством функции f для i≥0: xi+1=f(xi)= Вычисления проводятся в группе G, то есть если G=Zm, то вычисления следует производить по модулю m. Такая последовательность групповых элементов может быть представлена двумя последовательностями u0, u1, u2,… и v0, v1, v2,… такими, что xi= , u0=v0=0, ui+1= , vi+1= Вычисления в последовательностях u и v производятся по модулю n. В силу того, что группа G – конечная, при помощи метода Флойда можно найти такие xi и x2i, что xi = x2i. Тогда = . Логарифмируя по основанию g обе части данного уравнения, получим (vi—v2i)logga≡(u2i—ui) (mod n) Решая это сравнение, получим искомый логарифм. (Заметим, что если G=Z*m, то n=φ(m)). Сложность данного метода составляет O( ) , где n – порядок группы G. Замечание. Метод может дать отказ в том случае, когда vi =v2i. Тогда следует назначить случайные значения от 0 до n—1 переменным u0, v0 , вычислить x0= и повторить все шаги алгоритма. Замечание. В том случае, когда имеется достаточно места для хранения данных в процессе вычислений (например, когда G невелико или вычисления производятся вручную), можно обойтись без метода Флойда. Тогда следует хранить все члены последовательностей x, u и v до того, как xi = xj и дискретный логарифм находится из сравнения (vi—vj)logga≡(uj—ui) (mod n).
Пример. G=Z*19, a=8, g=2. Тогда n=φ(19)=18. Поскольку решение будем производить вручную, то не будем пользоваться методом Флойда. Разбиение G на подмножества произведем следующим образом: если x mod 3=1, то x S1, если x mod 3=2, то x S2, если x mod 3=0, то x S3. Вычисления будут производиться по формулам: xi+1=f(xi)= ui+1= , vi+1=
x3=x8. Логарифм найдем из сравнения (v3—v8)log28≡(u8—u3) (mod 18) -5 log28≡3(mod 18) 13 log28≡3(mod 18) log28≡3·7(mod 18) log28≡3(mod 18). Действительно, 23≡8 (mod 19). Ответ: log28≡3(mod 18).
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1473)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |