Казанский (Приволжский) федеральный университет, КФУ
КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
 
'СВИДЕТЕЛИ ПРОСТОТЫ В АЛГОРИТМЕ ШОРА И В АЛГОРИТМЕ МИЛЛЕРА-РАБИНА.' 'ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ. МАТЕМАТИКА.', № 12, 2008, СТР. 36-40. ДОКАЗАНО, ЧТО СВИДЕТЕЛИ ПРОСТОТЫ АЛГОРИТМА МИЛЛЕРА-РАБИНА ЕСТЬ СВИДЕТЕЛИ ПРОСТОТЫ АЛГОРИТМА ШОРА, ДЛЯ КОТОРЫХ ВЫПОЛНЕНО УСЛОВИЕ МАЛОЙ ТЕОРЕМЫ ФЕРМА. ОПИСАНО МНОЖЕСТВО НАТУРАЛЬНЫХ ЧИСЕЛ, ДЛЯ КОТОРЫХ СВИДЕТЕЛИ ПРОСТОТЫ АЛГОРИТМА МИЛЛЕРА-РАБИНА СОВПАДАЮТ СО СВИДЕТЕЛЯМИ ПРОСТОТЫ АЛГОРИТМА ШОРА. НАЙДЕНЫ ВСЕ ТАКИЕ ЧИСЛА МЕНЬШИЕ 100 000 000, И ЭКСПЕРИМЕНТАЛЬНО ИССЛЕДОВАНА СКОРОСТЬ РОСТА ОТНОШЕНИЯ КОЛИЧЕСТВА ТАКИХ ЧИСЕЛ К КОЛИЧЕСТВУ ЧИСЕЛ КАРМАЙКЛА.
Форма представленияСтатьи в российских журналах и сборниках
Год публикации2008
  • Лернер Эдуард Юльевич, автор
  • Библиографическое описание на языке оригинала "Свидетели простоты в алгоритме Шора и в алгоритме Миллера-Рабина." "Известия высших учебных заведений. Математика.", № 12, 2008, стр. 36-40. Доказано, что свидетели простоты алгоритма Миллера-Рабина есть свидетели простоты алгоритма Шора, для которых выполнено условие малой теоремы Ферма. Описано множество натуральных чисел, для которых свидетели простоты алгоритма Миллера-Рабина совпадают со свидетелями простоты алгоритма Шора. Найдены все такие числа меньшие 100 000 000, и экспериментально исследована скорость роста отношения количества таких чисел к количеству чисел Кармайкла.
    Место издания Казань
    Название журнала Известия высших учебных заведений. Математика.
    Издательство КФУ
    URL http://old.kpfu.ru/journals/izv_vuz/arch/2008/12/06-12.pdf
    Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку https://repository.kpfu.ru/?p_id=51353

    Полная запись метаданных