Где можно применить теорию чисел

Теория чисел-раздел математики, в котором изучаются свойства чисел.

Основной объект теории чисел-натуральные числа (см. Число). Главное их свойство, которое рассматривает теория чисел, — это делимость . Первый круг задач теории чисел-разложение чисел на множители. Основными «кирпичиками» в таком разложении являются простые числа, т. е. числа, делящиеся только на 1 и на себя; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 — вот первые десять простых чисел (число 1 не относят к простым). Замечательная теорема, называемая основной теоремой арифметики, гласит: всякое натуральное число раскладывается на простые множители, причем единственным способом (с точностью до порядка их расположения). Разложив два числа на простые множители, несложно определить, делится одно из них на другое или нет. Но до сих пор бывает трудно выяснить, является ли данное большое число простым, т. е. делится ли оно на какое-либо другое число, кроме себя и единицы.

С разложением чисел на простые множители связан ряд арифметических функций. Укажем некоторые из них. φ(n)-функция Эйлера-количество чисел от 1 до n, взаимно простых с числом n (т. е. не имеющих с n общих множителей, кроме единицы); α(n)-количество делителей числа n, τ(n) — сумма всех делителей числа n, π(n)- функция Чебышева — количество простых чисел, не превосходящих n. С помощью этих функций выражаются многие свойства натуральных чисел. Теорема Евклида утверждает, что простых чисел бесконечно много. Это означает, что π(n) → ∞ при возрастании числа n. Удалось выяснить, как быстро функция π(n) стремится к бесконечности. Оказалось, что примерно так же, как функция

Эта теорема носит название асимптотического закона распределения простых чисел. Она была сформулирована и в существенной части доказана П.Л. Чебышевым (1849), а полностью доказала лишь 50 лет спустя.

Асимптотический закон распределения простых чисел — это результат так называемой аналитической теории чисел, которая широко использует методы математического анализа для исследования теоретико-числовых функций. Обнаруженный во второй половине XIX в. факт связи такого дискретного объекта, как целые числа, с глубокими свойствами функций оказал большое влияние на развитие теории чисел.

Разложение чисел на множители учитывает только структуру множества натуральных чисел, связанную с умножением, наиболее глубокие и трудные задачи теории чисел возникают при сравнении сложения и умножения. К числу таких задач можно отнести, например, проблему Гольдбаха — можно ли всякое четное число представить как сумму двух простых; великую теорему Ферма (см. Ферма великая теорема)-можно ли n-ю степень числа представить как сумму n-х степеней двух каких-либо чисел и т.п.

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

Классическим методом теории чисел является метод сравнений. Отождествляя между собой числа, дающие одинаковые остатки при делении на выбранное число, часто удается установить невозможность какого-либо соотношения. Например, рассматривая остатки от деления на 3 (или, как говорят, по модулю 3), легко доказать неразрешимость в натуральных числах уравнения Зх 2 + 4у 2 = 5z 2 .

Аналитический метод состоит, как мы уже говорили, в том, что, отправляясь от чисел, строят функции, которые исследуют методами математического анализа. Так, советский ученый академик И. М. Виноградов доказал вариант проблемы Гольдбаха — представимость достаточно большого нечетного числа в виде суммы трех простых.

Геометрический метод теории чисел мы проиллюстрируем на примере великой теоремы Ферма. В этой теореме идет речь о разрешимости в целых числах уравнения х n + у n = z n . Поделив обе части уравнения на z n и заменив x/z на u, a y/z на v, получим уравнение u n + v n = 1. Это уравнение задает на плоскости с координатами (u, v) некоторую кривую. Решения исходного уравнения в целых числах соответствуют решениям нового уравнения в рациональных числах. О каждом таком решении (u, v) можно говорить как о точке с рациональными координатами на этой плоскости. Теперь можем попытаться применить геометрические методы к кривой u n + v n = 1 для исследования на ней множества точек с рациональными координатами.

Большой раздел теории чисел, занимающийся нахождением решений уравнений в целых и рациональных числах, носит название теории диофантовых уравнений, по имени древнегреческого ученого Диофанта (III в.).

К числу очень старых и известных задач теории чисел относится задача представления чисел суммами квадратов. Перечислим некоторые из полученных результатов:

каждое целое число можно представить как сумму четырех квадратов целых чисел (например: 7 = 2 2 + 1 2 + 1 2 + 1 2 );

каждое простое число вида 4n + 1 можно представить в виде суммы двух квадратов целых чисел (например: 5 = 2 2 + 1 2 , 41 = 4 2 + 5 2 и т. п.), а ни одно целое (не только простое) число вида 4n + 3 нельзя представить в таком виде;

каждое простое число, кроме чисел вида 8n — 1, можно представить в виде суммы трех квадратов целых чисел.

Простое алгебраическое тождество

(а 2 + b 2 ) (х 2 + у 2 ) = (ах + by) 2 + (ay — bx) 2

позволяет сделать вывод: если два числа представимы суммами двух квадратов, то и их произведение представимо суммой двух квадратов. Алгебраические методы в последнее время широко применяются в теории чисел. Этому способствовало развитие такого общего алгебраического понятия, как поле, само появление которого во многом стимулировалось задачами теории чисел.

Чем особенно ценна теория чисел? Ведь найти непосредственное применение ее результатам трудно. Тем не менее задачи теории чисел привлекают как пытливых молодых людей, так и ученых в течение многих столетий. В чем же здесь дело? Прежде всего эти задачи, как уже говорилось, очень интересны и красивы. Во все времена человека поражало, что на простые вопросы о числах так трудно найти ответ. Поиски этих ответов часто приводили к открытиям, значение которых далеко превосходит рамки теории чисел. Достаточно упомянуть о так называемой теории идеалов немецкого математика XIX в. Э. Куммера , которая родилась в связи с попытками доказать великую теорему Ферма.

Теория чисел

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

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

Теория чисел не только широко использует методы, разработанные в смежных математических дисциплинах, но и сама влияет на формирование этих дисциплин. Так, например, начало глубоких исследований в теории алгебраических чисел было связано с так называемой проблемой Ферма о возможности существования целых положительных решений диофантова уравнения $x^n+y^n=z^n$ при . Дальнейшее развитие этой теории оказало решающее влияние на современную алгебру, а возникшие в теории чисел понятия «кольца» и «идеала» являются одними из основных понятий математики нашего времени.

Современную теорию чисел можно разбить на следующие разделы:

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

Алгебраическая теория чисел . К этому разделу относят вопросы, связанные с изучением различных классов алгебраических чисел.

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

Аналитическая теория чисел . К этому разделу относят вопросы теории чисел, для изучения которых приходится применять методы математического анализа.

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

Исторические сведения

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

В трудах Евклида теоретико-числовые исследования занимают сравнительно небольшое место, однако уже у него мы встречаем ряд основных положений теории делимости и хотя простой, но чрезвычайно важный результат: бесконечность множества простых чисел.

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

В период упадка античной культуры работы Диофанта были почти совсем забыты. В VIII—IX веках в арабских странах возникает своеобразная математическая культура. Арабская математика, культивируя исследования по алгебре и тригонометрии, проявляла незначительный интерес к теоретико-числовым задачам. Некоторые арабские ученые комментировали Диофанта, рассматривали арифметические задачи того же типа, что и Диофант, однако ничего существенно нового ими не было получено.

В Европе, начиная с эпохи крестовых походов вплоть до XVII века, развитие теории чисел, как, впрочем, и всей математики, было очень медленым. Математики обычно рассматривали только отдельные конкретные задачи теоретико-числового характера. Общие методы были почти неизвестны. В этот период в основном развилась практическая арифметика действий. Из работ этого времени наибольший след в дальнейшем развитии теории чисел оставили весьма незначительные для этой эпохи работы Леонардо Пизанского и работы Региомонтана, который нашел труды Диофанта и впервые в Европе стал систематически их изучать.

В XVI и в начале XVII века на латинском и французском языках были изданы сочинения Диофанта, и ряд математиков того времени, из которых в первую очередь можно назвать Виета, занялись комментированием этих сочинений, несколько дополняя их новыми результатами.

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

В XVIII веке Л. Эйлер значительно продвинул вперед развитие теории чисел. Эйлер обобщил основной результат Ферма для случая делимости на составные числа, создал общую теорию так называемых степенных вычетов, получил очень большое число разнообразных результатов о представимости чисел в виде форм определенного типа, исследовал ряд систем диофантовых уравнений и получил интересные результаты о разбиении чисел на слагаемые. У Эйлера мы впервые встречамся с идеей применения методов математического анализа к задачам теории чисел. Рассмотрение бесконечных рядов и произведений явилось у Эйлера действенным орудием для получения теоретико-числовых результатов.

$ax^2+bxy+cy^2$

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

Большое влияние на дальнейшее развитие теории чисел оказали и работы А.Лежандра по теории диофантовых уравнений высших степеней. Лежандр нашел также эмпирическую формулу для числа простых чисел в заданных пределах. Работы Эйлера, Лагранжа и Лежандра создали базу для цельной теории, получившей позже у Гаусса название теории сравнений.

Замечательные работы немецкого математика К.Гаусса имели особенно большое значение для всей теории чисел. Работы Гаусса по теории сравнений 2-й степени придали ей законченный вид, так что в настоящее время вся эта область теории чисел базируется на результатах, изложенных им в книге «Арифметические исследования». В этой книге рассматривается также теория квадратичных форм, в которой им были получены фундаментальные результаты. Гаусс наряду с изучением обычных целых чисел начал рассматривать также и арифметику чисел, получивших название целых гауссовых чисел. Эти его исследования положили начало алгебраической теории чисел.

После работ Гаусса в течение всего XIX века и до сегодняшнего дня исследования по теории приобретают все увеличивающийся размах.

Теория чисел. Новый метод анализа распределения чисел, в том числе и простых

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

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

Если честно, то никогда бы не подумал, что случится подобное.

Предисловие. Или для чего нужны простые числа

С точки зрения арифметики большинство чисел отличается, так сказать, «хорошим поведением». Четные числа всегда чередуются с нечетными, каждое третье число всегда кратно трем, квадраты чисел подчиняются определенному закону. Поэтому мы можем составить длинный ряд чисел, которые ведут себя так, как им положено, независимо от длины этого ряда и величины самих чисел. Но простые числа похожи на неуправляемую толпу. Они появляются там, где им захочется, без предварительного предупреждения, на первый взгляд, совершенно хаотично, без какой-либо закономерности. А самое главное — их нельзя проигнорировать: простые числа необходимы для арифметики и для математики в целом.

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

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

Источник. (Простые числа [Долгая дорога к бесконечности]. Грасиан Энрике)
По ссылке выше находится весьма интересная статья, про простые числа. Тем кто плохо знаком с темой — настоятельно рекомендую!

Загадки распределения простых чисел, всегда будоражили умы многих выдающихся математиков: Эйлер, Ферма, Гаусс, Риман и многие многие другие, пытались разгадать сей загадочный пазл. До сих пор, существует множество гипотез и нерешенных вопросов, которые связанны с простыми числами, и которые остаются неизученными:

Посмотреть список гипотез

гипотеза о простых числах-близнецах – о бесконечном количестве пар простых чисел, отличающихся друг от друга на 2
гипотеза Гольдбаха: любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел
бесконечно ли количество простых чисел вида ?
всегда ли можно найти простое число между ? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26.
бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
– простое число для 0 ≤ n ≤ 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы Эти числа простые для 0 ≤ n ≤ 79.
бесконечно ли количество простых чисел вида n# + 1? (n# — результат перемножения всех простых чисел, меньших n)
бесконечно ли количество простых чисел вида n# -1 ?
бесконечно ли количество простых чисел вида n! + 1?
бесконечно ли количество простых чисел вида n! – 1?
если p – простое, всегда ли не содержит среди множителей квадратов простых чисел.
содержит ли последовательность Фибоначчи бесконечное количество простых чисел?

Гипотеза Римана: о нетривиальных нулях дзета-функции.

Пожалуй, понятно насколько было велико мое удивление, когда вывел формулу и стало ясно, что аналогов (кроме дзета-функции Римана) похоже что нет. Что же, теперь настало время поговорить о самой формуле, которая приоткрывает загадочную завесу тайны в распределении простых чисел: предоставляет инструмент для дальнейшего анализа — иной способ факторизации числа.

Очень надеюсь, что специалисты в области теории чисел и криптографии будут довольны!

Вступление

Посмотрите, на эти хаотичные, на первый взгляд, движения точек. Но нет, это далеко не Броуновское движение. Эти движения раскладывают на множители любое натуральное число или показывают расположение простого числа… Любопытное зрелище. Длиною в бесконечность и историей в без малого 2000 лет (первый известный алгоритм поиска простых чисел — Решето Эратосфена, 273–194 до н. э.):

Вот, например, точки находятся на оси абсцисс — значит это множители числа а=12:

На рисунке представлены множители 1,2,3,4,6,12 числа 12. Само число лежит на круге, радиусом a=12.

A здесь нет пересечений точек с целой координатой х, или иначе — нулей функции.
Перед нами простое число:

Множители: 1, 29

Гипотеза о распределении нулей натурального ряда

Итак, формула имеет следующий вид:

Где:
, заданное число.

Теперь о свойствах функции:

Если результат уравнения , то значит, такое число является множителем числа а.
Каждое пересечение синусоиды с осью ОХ, является показателем кратности числа а.
Так, если a=12, то и т.д.

Очевидно, что на периодах (между пересечениями) (На рисунке, это интервалы 1/2, 1/3, и т.д. соответственно), y функции нет нулей. — Свойств у функции, скорее всего больше. Нужно, проводить более тщательный анализ. Для упрощения алгоритма разложения числа на множители, коэффициент перед синусом можно убрать. Т.е. формула определяет нули и их отсутствие
в таком виде:

Гипотеза о предсказании появления простых чисел

Можно заметить, как свободные члены, не занятые в построении числа выстраиваются в ряды по некоторой траектории:

И действительно, они всегда занимают свободные “орбитали” (на рис. светло-зелёные линии)

Формирование орбиталей

Введу несколько терминов:
Положительная орбиталь, — орбитали которые находятся выше оси ОХ.
Отрицательная орбиталь, — ниже оси, соответственно.

Итак, положительная орбиталь порождается каждый раз при:
a mod 5 = 0 (или когда начало периода 1/5 — становится нулем)
Отрицательная орбиталь создается при:
a mod 3 = 0 (или когда начало периода 1/3 — становится нулем)

Так, например, если a=19, то

Каждая из орбиталей задается формулой:

где или иными словами:

В общем, если имеем число a = 41, то всего орбиталей будет:
плюс — Ось нулей

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

Попытаемся, графически предсказать проявление следующего простого числа, при a=22. Изобразим стрелками на какие орбитали сместятся числа для а+1=23

Вот так. Смотрим на позиции чисел на орбиталях и на то куда перейдут эти числа (на следующем шаге или через n-шагов с учетом добавления новых орбиталей), и предсказываем появление следующего простого числа, зная, что при простом числе нули будут отсутствовать.

Что же, похоже на то, что к математической загадке найден очередной ключик. Осталось, пожалуй, найти строгое доказательство всему этому добру. Да более детально исследовать все особенности поведения функции, скачков чисел (так и хочется сказать — электронов) по орбиталям. Пожалуй, что предоставлю сие удовольствие более серьезных исследований и открытий связанных с изучением функции — Математикам, специалистам по теории чисел и анализу, а так же всему научному сообществу!

→ Поиграться с функцией можно здесь: desmos.com

Заключение

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

И тем не менее, если гипотеза Римана делает предположение о нулях, то здесь на более простом (школьном) уровне делается предположение о способе предсказания нулей. А это, в свою очередь, позволяет применить более широкий арсенал математических методов для более глубокого изучения простых чисел.

Надеюсь, что более детальное исследование специалистами данной функции позволит сделать еще массу полезных и удивительных открытий в теории чисел. Как и все заинтересованные буду ждать новых исследований и достижений!

В заключение слова благодарности

Спасибо авторам YouTube каналов, которые смогли заинтересовать математикой. Без вас и вашей мотивации я навряд ли бы полез разбираться с данной темой.

Где можно применить теорию чисел

КАК ТЕОРИЯ ЧИСЕЛ ПОМОГАЕТ В ШИФРОВАЛЬНОМ ДЕЛЕ (УСПЕНСКИЙ В.А. , 1996), МАТЕМАТИКА

Можно ли придумать такой способ шифрования, чтобы шифровать сообщения мог каждый, а расшифровать — только знающий секретный ключ? В статье рассказывается о решении, которое теория чисел предлагает для поставленной задачи.

КАК ТЕОРИЯ ЧИСЕЛ ПОМОГАЕТ В ШИФРОВАЛЬНОМ ДЕЛЕ

Московский государственный университет

им. М.В. Ломоносова

1. ПОСТАНОВКА ЗАДАЧИ

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

1. Расшифровать зашифрованное сообщение может только Получатель. Ключ к расшифровке настолько секретен, что неизвестен даже Отправителям.

2. Напротив, ключ к шифровке публикуется Получателем совершенно открыто, так что зашифровать сообщение может всякий желающий. Такой ключ называется открытым ключом.

Всякая система шифровки и дешифровки, удовлетворяющая сформулированным выше двум требованиям, называется системой тайнописи с открытым ключом (по-английски: public-key cryptosystem). Естественно встает вопрос, возможна ли подобная система. Оказывается, да, возможна [5, n? 6.2]. Одна их таких систем была указана тремя математиками, РивОстом (R.L. Rivest), Шамиром (F. Shamir) и Адлеманом (L.M. Adleman), в их совместной публикации [4]. По начальным буквам фамилий система носит название Система РША (в оригинале RSA). Она опирается на факты из теории чисел. Цель настоящей статьи — изложить в доступной форме Систему РША.

2. ОБЩИЕ ПРЕДСТАВЛЕНИЯ О ШИФРАХ

2.1. Сообщения и шифрограммы

«Шифрование производится путем замены целых фраз, слов, слогов или отд. букв цифрами или буквами в различных комбинациях на основе заранее принятой системы, являющейся соответственно ключом для расшифровки текста», — указывает Большая Советская Энциклопедия (изд. 3-е, т. 29, стлб. 1241). Эта формулировка не совсем точна: ведь при тайнописи с открытым ключом система шифрования не является ключом для расшифровки.

В общем случае ситуация выглядит так. Сообщение шифруется Отправителем и расшифровывается Получателем. Таким образом, от Отправителя к Получателю идет не само исходное сообщение М, а его зашифрованный образ С, который будем называть шифрограммой исходного сообщения. Получив шифрограмму С, Получатель восстанавливает М. Перескажем то же на математическом языке. В распоряжении Отправителя имеется шифровальный ключ, то есть функция E, преобразующая сообщение М в шифрограмму С. В распоряжении Получателя имеется дешифровальный ключ, то есть функция D, преобразующая шифрограмму С в исходное сообщение М, так что D (E (M )) = M, откуда E (D (C )) = C.

Каждое сообщение есть конечная последовательность каких-то символов: букв, цифр, знаков препинания и т.п. (Пробел есть особый знак препинания; удобно изображать его каким-либо символом, например, решеткой #; тогда, скажем, фраза «4 мая» запишется так: «4#мая».) Все эти символы выбираются из заранее указанного конечного списка. Любой такой список символов называется алфавитом, члены этого списка — буквами, а произвольная конечная цепочка букв — словом в данном алфавите. (Так, выражение «ъъыйЩйь» есть слово в русском алфавите.) Если расширить русский алфавит за счет цифр, знаков препинания и некоторых других стандартных знаков, то любой русский текст можно считать словом в этом расширенном алфавите. А любой английский, французский и т.д. текст можно считать словом в расширенном латинском алфавите. Теперь ясно, что каждое сообщение есть слово в подходящем Алфавите Сообщений. А каждая шифрограмма есть слово в Алфавите Шифрограмм.

2.2. Переход к двоичному алфавиту

Вот простое и замечательное соображение: можно ограничиться двоичным алфавитом, то есть алфавитом, состоящим всего лишь из двух букв 0 и 1; слова в таком алфавите называются двоичными. В самом деле, пусть в рассматриваемом нами алфавите m букв и пусть 2s $ m. Количество слов длины s в двоичном алфавите равно 2s ; поскольку этих слов оказалось не меньше, чем букв в исходном алфавите, то каждую букву исходного алфавита можно взаимно однозначно закодировать в виде некоторого двоичного слова длины s. Каждое слово длины k в исходном алфавите превратится после замены каждой его буквы на ее двоичный код в свой двоичный образ, а именно, в двоичное слово, имеющее длину sk. При этом исходное слово легко восстанавливается по его двоичному образу.

Пример. Алфавит, достаточный для записи сообщений на русском языке, должен включать 33 прописные и 33 строчные русские буквы, 10 цифр, знаки препинания, знаки номера, параграфа и т.д. Можно надеяться, в этом алфавите будет менее, чем 27 букв. Поэтому каждую из этих букв можно закодировать посредством 7-буквенного двоичного слова. Пусть, например, двоичные слова 0000001, 0011010, 1000001, 1000110, 1111111 служат, соответственно, кодами для букв а, м, я, 4, #. Тогда для выражения «4#мая» его двоичным образом будет слово 10001101111111001101000000011000001.

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

2.3. Переход к числам

Числа в нашей статье будут только целые, как правило неотрицательные.

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

Замечание. А как же все-таки быть, если сообщение, закодированное в соответствии с п. 2.2., начиналось с 0? Простейший способ разрешения проблемы таков: после создания двоичного образа надо к этому образу приписать спереди 1.

Мы совершили простую, но важную процедуру: арифметизацию ситуации. Теперь функции E и D становятся числовыми функциями, аргументами и значениями которых служат положительные целые числа. А сама ситуация выглядит так. Отправитель располагает достаточно большим запасом чисел, называемых сообщениями. На множестве этих чисел-сообщений определена функция Е с числовыми же значениями. Выбрав сообщение М, Отправитель направляет Получателю число Е(М ). Получатель, пользуясь функцией D, находит исходное М в качестве D (E(M )).

Коль скоро сообщения стали числами, мы можем интересоваться их числовыми свойствами, например, четностью или нечетностью или, вообще, делимостью.

Пусть даны неотрицательное a и положительное b; тогда a можно и притом единственным образом представить в виде a = bq + r, где q и r суть числа и 0 # r
Похожие публикации:

Где можно применить теорию чисел