Неоспоримые цифровые подписи

  • Добавили16.06.2006
  • Размер103,34 Kб
  • Скачали856

Лежандра на составные модули, он определяется для любого целого а и любого нечетного р. Ja,р определен только, если р нечетно. J0,р 0 Если p простое число, то 1 Ja,p 0, если a делится на p 2 Ja,p1, если a - квадратичный вычет по модулю p 3 Ja,p-1, если a - квадратичный невычет по модулю p Если p составное число, то Ja,р Ja, p1 Ja, p2 Ja, pm, где p1 pm простые множители все p.

Правило 1 J1,р1 Правило 2 Jab,р Ja,р Jb,р Правило 3 J2,p1, если p2 -18 четно и J2,p-1, если p2 -18 нечетно Правило 4 Ja,p Ja mod p,p Правило 5 Ja, b1 b2 Ja, b1 Ja, b2 Правило 6 Если НОДa,b1 и a и b нечетны, то Ja,bJb,a, если a-1b-14 четно, Ja,b-Jb,a, если a-1b-14 нечетно. П р и м е р Вычислим J21,109 По правилу 2 имеем J21,109J37,109 J3,109 J7,109 По правилу 6 имеем НОД3,1091, НОД7,109 и 3 и 7 и 109 нечетны, тогда 2108454, то J3,109 J109,3 61084162, то J7,109 J109,7 По правилу 4 имеем J109 mod 3,3 J1,31 J109 mod 7,3 J4,7 По правилу 2 J4,7 J2,7 J2,7 По правилу 3 72 -186 - четно, то J2,71 Получаем, что J21,109 J1,3J2,7 J2,71. Итак, 21 является квадратичным вычетом.

Проверка чисел на простоту. Тест Соловея-Штрассена. Для проверки простоты числа p в этом алгоритме используется символ Якоби.

p нечетное, большое число 1. Выберите случайное число a, меньше р. 2.

Если НОДa,p 1, то р - составное число и не проходит тест. 3. Вычислите j ap-12 mod p.

4. Вычислите символ Якоби Ja,p. 5.

Если j Ja,p,то число р определенно не простое. a-свидетель 6. Если j Ja,p,то вероятность того, что число р не является простым и не превышает .

Повторить эту процедуру t раз. 5 П р и м е р Пусть требуется проверить на простоту число 109. 1.

Выберем случайно а21. 2. НОДа,рНОД21,1091 вычисляем по алгоритму .

Скачать
Диплом Радиоэлектроника 23.12.1998

Коммутатор цифровых каналов системы передачи

www trunk.5ballov.ru data referats downloads new tmp dir 3288820.3576 Результаты Расчета Выбора Технологии Построения БИС Технология Критерии ВЕС ТТЛ Ш ЭСЛ пМДП КМДП 1.Быстродействие 0,07 0,19 0,65 0,07 0,09 2.Помехоустойчивость 0,11 0,21 0,09 0,29 0,41

Контрольная Гражданское право и процесс 27.12.2007

Сделки

Сделки являются основной правовой формой, в которой опосредуется обмен между участниками гражданского оборота, с чем они сталкиваются ежедневно. Посредством сделок осуществляется нормативный процесс имущественных отношений в обществе граждане пользуются

Реферат Компьютерные сети 22.06.2006

Защита информации. Основные методы защиты.

- 2 - Угрозы компьютерной безопасности - 2 - Компьютерная преступность - 2 - Internet как среда и как орудие совершения компьютерных преступлений - 2 - Синдром Робина Гуда - 2 - Компьютер глазами хакера - 2 - Кто такие хакеры - 2 - Методы взлома компьютерных

Реферат Транспорт 09.10.2009

История компании и модельный ряд Сузуки

В 1952 году вышла разработка Сузуки - моторизованный велосипед, названный Power Free. Он был оснащен двухтактным моторчиком объемом 36 куб. см и оригинальным приводом, который позволял пользоваться педалями как при выключенном, так и при заведенном моторе.

5ballov.qip.ru рекомендует:

  • Выбор ВУЗа

    С приходом лета начался период, когда выпускники школ выбирают куда пойдут учиться дальше. Конечно, это совсем не легкий выбор, но помочь в выборе может рейтинг вузов на нашем сайте. Также в этом разделе представлена вся нужная для абитуриентов информация.

  • Как сдать ЕГЭ

    Прежде, чем идти в выбранный вуз с документами, нужно сначала получить аттестат, который выдается после сдачи экзаменов. А подготовиться к ним можно в нашем разделе ЕГЭ. Там также представлены варианты за прошлые года.

  • Подготовка к ГИА

    Для девятиклассников не менее важно окончание учебного года. Их также ждет государственная итоговая аттестация. Подготовиться к ней можно на нашем сайте в разделе ГИА. Главное помнить: самоподготовка - это путь к успешной сдаче.

Облако тегов