Четверг, 25.07.2024, 04:54
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                              Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ
МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ
В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
МАТЕМАТИКА ВЧЕРА, СЕГОДНЯ, ЗАВТРА [12]
УДИВИТЕЛЬНЫЙ МИР ЧИСЕЛ [17]
ЗАНИМАТЕЛЬНАЯ МАТЕМАТИКА В РАССКАЗАХ ДЛЯ ДЕТЕЙ [18]
ЗАНИМАТЕЛЬНАЯ МАТЕМАТИКА ДЛЯ ВЗРОСЛЫХ И ДЕТЕЙ [31]
ШКОЛЬНИКАМ О ШИФРАХ [26]
ЗАГАДКИ И ДИКОВИНКИ В МИРЕ ЧИСЕЛ [68]
ВСЕМИРНАЯ ИСТОРИЯ СИММЕТРИИ [16]
Главная » Статьи » ЗАНИМАТЕЛЬНАЯ МАТЕМАТИКА » ШКОЛЬНИКАМ О ШИФРАХ

Проблемы факторизации чисел и дискретного логарифмирования

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

Криптографические приложения проблемы факторизации чисел и, особенно, заинтересованность пользователей банковских систем цифровой подписи привели к резкому увеличению исследований, связанных с разложением чисел на множители. В последние годы благодаря применению тонких методов теории чисел и алгебраической геометрии было разработано несколько эффективных алгоритмов факторизации. Наилучший из таких алгоритмов еще не является полиномиальным, но уже и не экспоненциальный, он относится к классу так называемых субэкспоненциальных алгоритмов (говоря строго, его сложность превосходит любой полином от n, но меньше, чем 2N, где N=nε для любого ε>0).

Среди последних достижений в этой области можно упомянуть об успехе Ленстры и Монасси, разложивших в июне 1990 года 155-разрядное число на три простых. Для этого они использовали 1000 объединенных ЭВМ и шесть недель их машинного времени. Вычисления проводились с помощью алгоритма английского математика Дж. Полларда. Ленстра и Монасси считают, что в настоящее время (1991 г.) можно в течение года разложить новые классы целых чисел длиной до 155 разрядов, затратив на это $200 млн.

Еще одна большая проблема — дискретное логарифмирование в конечных полях. Пусть, например, нам даны элементы a и b из конечного поля F, причем известно, что a=bx при некотором натуральном x. Задача дискретного логарифмирования состоит в том, чтобы определить это x. Можно, разумеется, просто перебирать последовательно все натуральные числа, проверяя, выполнено ли указанное равенство, но это будет экспоненциальный алгоритм. Пока наилучший из разработанных математиками алгоритмов дискретного логарифмирования является субэкспоненциальным.

Категория: ШКОЛЬНИКАМ О ШИФРАХ | Добавил: admin (15.07.2013)
Просмотров: 866 | Теги: криптография, шифры, защита информации, шифрограмма, ключ к шифру, занимательная информатика, дидактический материал по инф | Рейтинг: 5.0/1
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ
ИНФОРМАТИКА В ШКОЛЕ
ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"

ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ИГРОВЫЕ ЗАДАНИЯ ПО ИНФОРМАТИКЕ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты
  • Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0
    Форма входа


    Copyright MyCorp © 2024
    Яндекс.Метрика Top.Mail.Ru