Модель

Модель натурального числа. Часть I

25.06.2020 16:23:50 |

Автор: admin

Теоремы существования и теоремы перечисления. Модели

Ограниченность научных, теоретических знаний тормозит научное и общественное развитие.
Взять закон распределения простых чисел (ЗРПЧ) или ту же основную теорему арифметики (ОТА). Да, они фундаментальны, но что ОТА утверждает?

Это всего лишь (как и ЗРПЧ) теорема существования, для любого числа N существует произведение степеней простых чисел, которое единственно и равно этому числу N. Как получить и увидеть отдельные делители N в теореме не говорится. Аналогично и с простыми числами. Сами числа (большие и очень большие) получать умеем только квазипростыми.

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

Более того, большинство и других основных теорем теории чисел теоремы существования. Чтобы воспользоваться многими теоремами относительно простых или составных чисел N необходимо располагать разложением этого числа на делители. А этого-то мы и не умеем!
Где же ответ? Где ключевые направления для получения положительных решений?

Материал публикации представляется весьма обширным, поэтому для удобства ознакомления с ним разбивается на две части.

Предварительные результаты, необходимые для разработки модели числа

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

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

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

С учетом аудитории (надежда попасть на крутых спецов) и возможностей Habra (публикации в научных журналах не комментируются, что свойственно Хабру, журнальные рецензенты не в счет, это вопрос везения) в каждой публикации (в том числе и в рецензируемых журналах из списка ВАК) автору удается лишь в ограниченном объеме излагать отдельные новые оригинальные идеи подхода. Замечу, что нынешний рынок публикаций опубликует за деньги где хотите и что хотите академический журнал не панацея для истины.

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

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

Известно крылатое выражение электрон неисчерпаем, могу здесь его переиначить Натуральный ряд чисел загадочен и неисчерпаем. Какой объект из двух менее изучен наукой сказать не берусь. Обнадеживают мои скромные усилия, те люди, которые (даже при наличии минусовых оценок на Хабре) в копиях публикуют на своих сайтах научные результаты моих публикаций и дают на них ссылки своим читателям.

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

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

Например, публикация в 2010 г Арнольда В.И. Случайны ли квадратичные вычеты? обратила мое более пристальное внимание на этот объект, поскольку я был убежден в его неслучайности, детерминированности, а сомнения в этом академика РАН от математики для меня было просто удивительным.

В рамках фрагмента НРЧ, определяемого значением N, ряд при его формировании как бы самостоятельно определяет в какой позиции, что нужно вписать, где полный квадрат, а где другое значение. Более правильным вопросом относительно квадратичных вычетов (КВВ) мог бы быть: Почему они так распределены, почему так происходит?

Поиск причин конкретных распределений квадратичных вычетов в конечных числовых кольцах вычетов (КЧКВ) по составному модулю N, и в частности, квадратичных вычетов полных квадратов (КВК) привел к формулированию нового закона Распределения делителей числа в НРЧ.

Оказалось, что распределением, т. е. положением КВК в НРЧ естественным образом управляют делители составного модуля N, о значениях которых у нас нет никаких сведений, а у ряда натуральных чисел получается есть. В нужной позиции ряд ставит кратное одному из делителей, на нужном удалении от него ставит полный квадрат и на таком же удалении дальше ставит кратное другому делителю. Есть чему удивиться!

Законом вскрывается причинно-следственная связь положения в НРЧ делителей, их кратных и квадратичных вычетов-полных квадратов по модулю N.

Все с делителями оказалось очень просто, даже простые числа не потребовались для их поиска. Но остается не вполне ясным, как такое управление распределением КВК происходит. Если натуральному ряду сообщить, т. е. задать значение составного модуля (N) кольца или простого числа (Р) для алгебраического поля, то он как бы автоматически укажет позиции, в которых квадратичный вычет становится квадратом. Выполняя редукцию, мы заранее результата не знаем, а квадрат возникает как раз там, где он и должен быть.

Долгое время оставалось загадкой, почему так происходит. Математики это видели всегда, но проходили мимо, не обращая внимания на сам факт, не удивлялись этому, не задавались вопросом и не искали разгадки. А академик РАН Арнольд В.И. вопрос себе задал, выполнил исследование и позднее опубликовал его.

Именно КВК несут в себе информацию о делителях числа N (выполняют роль обнаружителей, детекторов делителей), и они вычисляются элементарными операциями. Так был открыт новый закон в теории чисел. Он мог быть открыт и раньше, но публикация, надоумившая меня серьезно заняться этим вопросом случайно попалась мне на глаза лишь в 2014 году.
Закон распределения делителей числа обнаруживает их положение в НРЧ и обеспечивает их перечисление для заданного составного числа N.

Модель отдельного нечетного числа

В рамках любой строгой теории обычно рассматриваются математические задачи и соответственно математические методы их решения, основные объекты и процессы которых моделируются на ЭВМ. Это удобно, особенно если требуются обширные вычисления.

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

В теории чисел значительное место отводится проблеме факторизации. Теорема факторизации устанавливает необходимость рассмотрения числового множества, ограниченного лишь подмножеством нечетных натуральных чисел (СННЧ) определенного вида (здесь), что является и достаточным для решения задачи факторизации. Это ограничение существенно упрощает проблему моделирования основного объекта (числа), но не делает ее простой.

Кроме модели числа важно располагать и более объемлющей моделью, в которой сами числа являются всего лишь отдельными элементами. Таким объемлющим числа объектом рассматривается НРЧ, модели которого также рассматриваются в предлагаемом новом подходе к проблеме факторизации. Это линейная модель (обычный НРЧ), плоскостные: контурная модель-спираль Улама (полная) и квадратичная Г² модель (модель усеченного НРЧ). (здесь)

В этой публикации начнем рассмотрение моделей отдельного числа. В каждой из названных моделей НРЧ элементами выступают отдельные числа: в линейной это индекс позиции регистрового разряда, в котором помещается число, в контурной модели нечетное число полуконтур (левый или правый) с множеством свойств, в квадратичной Г² модели число представляется разностью\суммой квадратов (целочисленными точками гиперблы, окружности) N=x1²xo².

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

Обоснование выбора списковой многострочной модели (СММ) числа

В статье предлагается концепция линейной алгебраической модели числа N, с погружением ее в множество подобных, представляемой многострочной таблицей. Модель достаточно простая. Будем представлять СННЧ N разбиением на две части N=x1+x0 всеми возможными способами.

Очевидно, таких способов представления числа N существует (N 1), при этом каждая сумма размещается в отдельной строке таблицы модели. Переменная x0 пробегает все строки от 1 до (N 1), т. е. играет роль текущего номера строки СМ-модели, который может совпадать в некоторой строке с конкретным делителем N и его кратными (см. табл.1).

Таблица 1 фрагмент СМ- модели

Обоснование выбора такой модели следующее. В линейной модели НРЧ присутствуют все числа без пропусков, что позволяет задать любое составное нечетное N = рq в соответствующей позиции. Очевидно, фрагмент НРЧ от 1 до N = рq, где р и q простые числа ( 2), содержит следующие подряд все числа, среди которых обязательно встретятся р и q и их кратные. Добавив к этому множеству чисел нулевой элемент получим конечное числовое кольцо вычетов (КЧКВ) по составному модулю N.

Если это множество чисел (фрагмент НРЧ) содержит среди элементов делители и кратные им значения, то возникает мысль, нельзя ли выудить из таких элементов сами делители р и q. Поставив целью исследования выуживание делителей из модели, модель должна сохранить полностью элементы фрагмента НРЧ.

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

Последовательность натуральных чисел СММ и ее фундаментальное свойство
Последовательность непрерывно следующих натуральных чисел используется в СМ-модели в двух колонках x1 и x0, в которых x0 играет роль текущего номера строки модели до середины исходного списка. Значение х1 = N хо дополнение до модуля снизу вверх записывается в строках модели. Для каждого из элементов (номера и дополнения) строки вычисляется rл(x0) и rл(x1) квадратичный вычет по модулю N. Эти КВВ совпадают, что допускает ограничиваться хо.

Для малых значений x0 редукция по N не меняет значений rл (x0) и строки, содержащие такие неизменяемые левые вычеты, всегда образуют для различных N область тривиальных КВК, обозначаемую ТКВК. Граница этой области называется левым верхним первым порогом, а ее значение вычисляется, например, для N=1961, как x0в1= N=1961=44,28, округляется до 44.

Полные квадраты из ТКВК области не используются ЗРД и не участвуют в факторизации. При движении вниз по строкам таблицы за пределами порога КВВ (x0>44) превышают модуль и редуцирование уменьшает значения. В некоторых строках при этом получаются дубли из ТКВК и они (и только они) используются для факторизации в рамках ЗРД .

Итак, последовательность содержит делители N и их кратные; начинается тривиальной ТКВК областью; некоторым значениям хо в дублях строк соответствуют КВВ полные квадраты.

Последовательность нечетных чисел СММ и ее фундаментальное свойство
В предлагаемой модели возникают последовательности нечетных чисел Т и Тп. Они играют существенную роль и на этом явлении остановимся подробнее. Ряды нечетных чисел (колонки 4 и 7) в таблице СММ встречно направлены, но состав их и структура идентичны
Т, Тп = {ti, i = 1(1)(N-1), ti =1(2) N-2}.

Они в НРЧ образуют бесконечную непрерывную последовательность нечетных значений, (но в примерах ограничены значениями от 1 до N 2). Каждый элемент t такого ряда (последовательности) будем представлять суммой смежных чисел t=t1+t0, где значение tо=t1-1. Слагаемые t1+t0 будем перемножать друг на друга р(t)=t1t0. Обозначим редуцированное произведение символом rc (t) =(t² -1) и назовем средним вычетом. Оказывается, такие произведения обладают рядом замечательных свойств.

Во-первых, произведения таковы, что их флексии принимают только три четных значения {0, 2, 6}. Флексии в нечетных рядах следуют пятерками строк, которые следуют в порядке 02620 (табл. 1) и повторяются периодически до бесконечности.

Во-вторых, значения произведения р(t) с ростом ti возрастают, но в рамках модели редуцируются при превышении модуля N. Произведения меньшие модуля при редукциях остаются без изменений, и обладают свойством сохранять смежность сомножителей (ССС). Множество строк, в которых ti следуют подряд и их произведения обладают свойством ССС называется тривиальной областью и обозначается ТССС (заливка в колонке 6 зеленый цвет).

Граница этой области называется нижним средним первым порогом, а ее значение вычисляется как 1892 = 44² 44, где значение 44=N=196144,2. В СММ (табл.1) в колонке 6 размещены строки ТССС средние вычеты rc(t) в строках с номерами хо = 937 по хо = 980 элементы.

В-третьих, те ti, для которых значения произведений превышают модуль, редуцируются и редукция уменьшает их значение. При этом в некоторых строках редуцированные значения повторяют (дублируют) некоторые значения из ТССС. Эта особенность произведений ti обладать свойством ССС после редукции оказывается весьма важной в процессе факторизации модуля N.

Итак, последовательность нечетных чисел t завершается тривиальной ТССС областью (колонка 6); некоторым значениям хо в дублях строк этой области соответствуют КВВ-полные квадраты, что свидетельствует о непустом пересечении двух нетривиальных областей ТКВКТССС

Пример 1. (Редуцированные значения со свойством ССС). Пусть в СММ (см табл.1) задано
N = 1961 = рq и значение t=t1+t0 = 45 = 22 + 23. Находим значение произведения смежных слагаемых р(t) = 2223 = 506. Результат не превышает модуля 506 <1961, следовательно, редукция оставляет результат без изменения, т.е. rс(р) = р(mod N) = 506(mod 1961)= 506.
Флексия 506(mod10)=6 {0, 2, 6} говорит о выполнимости свойства rс(р) ССС.

Изменим t=t1+t0 = 89 = 44 +45. Находим значение произведения смежных слагаемых
р(t) = 4445 = 1980. Результат превышает модуль 1980 >1961, следовательно, требуется редукция, уменьшающая результат произведения, т.е. rс(р) = р(mod N) =1980(mod 1961)= 19.
Флексия результата 19(mod10)=9 {0, 2, 6} показывает, что свойство rс(р) ССС не выполняется.

Рассмотрим явления, происходящие при моделировании отдельного числа N, в рамках СМ-модели. Удобно это сделать на числовом примере, сопровождаемом комментариями. Выбор числа сделаем таким, чтобы исключить простое угадывание делителей. Здесь ограничимся лишь строками нижней части основной таблицы СМ-модели, хотя и не столь малого объема.

Пример 2. Задано число N = 1961 = рq, которое подвергнем факторизации. Для этого воспользуемся оригинальной СМ-моделью (см. табл.1) и определим (заполнены) полные верхнюю
rл(1) = 1, х1=1960, хо =1, t=1959, rс(1) = 491, tп = 1, rп(1) = N rл(1) = 1961 1 = 1960 и нижнюю
rл(0) = 1471, х1=981, хо =980, t=1, rс(0) = 0, tп = 1959, rп(0) = N rл(0) = 1961 1471 = 490, строки СММ а также остальные элементы в области ТССС и в других строках. Дело в том, что свойства модели допускают заполнение всех полей строк основной таблицы ручным способом, даже не прибегая к использованию компьютерной программы.

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

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

Теперь можно в деталях описать фрагмент модели числа (таблицы 1).
Описание фрагмента таблицы СМ-модели отдельного числа. Полная таблица строк СММ для N = 1961 содержит 980 строк и 8 столбцов (левый столбец примечаний не обязателен). Предварительно заполним поля столбцов t, tп, верхнюю и нижнюю строки СМ-модели. Строки нумеруются подряд сверху вниз хо до середины списка (нижняя нулевая строка р = rc=0) и далее продолжение х1 снизу вверх в колонке слева (слева от хо = 980 стоит х1 = 981).

Строки имеют типовую начинку: левый квадратичный вычет rл(хо), номер хо строки, х1 дополнение номера до N, разность t=х1хо пробегает монотонно убывающие нечетные значения от N 2 до 1, произведение р(t)=t1tо= (t² 1), средний вычет rс(р) = р(mod N), tп нечетные числа от 1 до N 2, правый вычет произведения rп(хо) = хох1 (mod N) = N rл(хо). Кратными будем называть строки, номера которых кратны делителям N.

Из полного списка строк приводимый фрагмент (табл.1) включает лишь 57 строк: первую, 901-ю, и все с 925-й по 980-ю строки. Заливкой выделены пары строк: номера хо = 901 и хо = 954 которых кратны большему делителю (оранжевый цвет); номера хо = 925 и хо = 962 которых кратны меньшему делителю (зеленый цвет); номера хо = 958 и хо = 966 строк, содержащих квадратичные вычеты КВК полные квадраты (синий цвет).

Следовательно, оранжевые и зеленые строки кратные. В таблице замкнутый интервал строк между ближайшей парой кратных строк разного цвета хо = 954 и хо = 962 содержит 9 строк, средняя с номером хоц = (954 + 962) = 958 строка.

В соответствии с законом распределения делителей числа в этой хоц точке КВВ должен быть полным квадратом удаленности (в числе строк) от нее кратных строк (точек) с разным цветом заливки. Действительно, строки хо = 954 (оранжевая) и хо = 962 (зеленая) удалены от центральной хоц = 958 обе на 4 позиции (строки) каждая.

Более поучительный случай (синяя) строка, имеющая номер хоц = 966. Поскольку вычисление КВВ в этой точке дает результат rл(хоц) = хоц (t)²(mod N) = 966²(mod1961) = 41² равный полному квадрату (41²), то эта точка (по ЗРД) должна быть центром замкнутого интервала с нечетным числом строк в нем 83 = 241+ 1.

Удаленность (41 позиция) обеих границ интервала от центра. Действительно, такая пара строк (заливкой разного цвета) с номерами кратными делителям N, существует. Это строки с номерами хо = 925 (зеленая) и хо = 1007 (оранжевая). Удаленность границ равна разности
1007 966 = 966 925 = 41. Длина замкнутого интервала 83 = 241+ 1.

Наличие таких строк (даже одной синей из них) делает допустимым на основе ЗРД быстрое и успешное завершение ЗФБЧ. В соответствии с законом распределения делителей числа N в НРЧ в установленных строках определяются значения их текущих номеров. Это номера (точки хо) тех строк, в которых порождаются КВК.

Далее, следуя пунктам алгоритма (ниже) вычисления значений делителей р и q, находятся и сами делители. Вообще подряд все строки восстанавливать не обязательно, хотя и полезно для понимания и обучения. Важно уметь оперативно получать те из них, в которых КВВ полные квадраты.

Установление таких строк реализуется элементарными действиями над элементами СМ-модели. В приведенном фрагменте таблицы СММ такими строками являются строки с номерами хо = 958 и хо = 966 (выделены заливкой синего цвета).

Каким образом получаются окончательные решения, т. е. как вычисляются делители N?
На самом деле кратные делителям правая и левая границы Гп, Гл замкнутых симметричных относительно центров интервалов с нечетным числом строк неизвестны, так как неизвестны ни делители N, ни коэффициенты кратности номеров строк-границ.

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

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

Поэтому предлагаемый алгоритм факторизации начинается с определения полных квадратов (КВК) в колонке квадратичных вычетов СМ-модели. Это можно сделать, вычисляя очередной номер строки, при движении в СМ-модели сверху вниз, либо снизу вверх. Путем перебора для каждого очередного номера строки вычислять КВВ и проверять, является ли он полным квадратом.

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

При установленных в примере значениях таких квадратов (КВВ 16 и 1681) и точек хоц= 958, хоц= 966, в которых они получены возможно (обратная задача) построение замкнутого интервала с определением его границ Гп, Гл = хоц (rл )= 958 4 = 962, 954, а также
Гп, Гл = хоц (rл )= 966 41 = 1007, 925.

Для окончательного получения значений делителей используется алгоритм Евклида наибольшего общего делителя НОД. Для первого случая, строка
хоц= 958 (синяя) и rл(хоц) =16 =4² имеем
di = НОД(N, Гi ) = НОД (1961, 962) = 37; di = НОД(N, Гi ) = НОД (1961, 954) = 53.

Для второго случая, строка с номером хоц = 966 (синяя) и КВК rл(хоц) =1681 = 41² имеем di = НОД(N, Гi ) = НОД (1961, 925) = 37; di = НОД(N, Гi ) = НОД (1961, 1007) = 53.

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

Продолжим обоснование полученных результатов

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

Обратим внимание на замечательную особенность колонки КВВ таблицы СМ-модели. Значения КВВ при движении вверх монотонно возрастают. Их рост ограничивается значением N-модуля. Как только значение КВВ превысит N оно редуцируется и становится равным разности (КВВ N), которая всегда меньше N. Эта разность является новым значением КВВ и может оказаться полным квадратом, т.е. КВВ = КВК. Именно этой возможностью и воспользуемся в алгоритме факторизации.

Другая особенность СМ-модели состоит в замечательном свойстве самой модели. Вне модели воспользоваться свойством не удается. Оказывается, левый квадратичный вычет, может вычисляться не только через квадратичное сравнение. Он может представляться суммой левого квадратичного вычета нижней строки модели rл(0) и текущего среднего вычета строки. Используется и это свойство КВВ в СМ-модели: rл(хоц) = rл(0) + rс(хоц) = 1471 + 506 = 1977.

Выбор среднего вычета 506 специально сделан таким, чтобы сумма его с rл(0) превысила N.
Поскольку найденное значение превышает модуль N = 1961, то его следует редуцировать, т. е. привести по N модулю rл(хоц) = rл(0) + rс(хоц) (mod1961) = 1977 1961 = 16 = 4². Редукция суммы при этом равна разности, что для rл(хоц) ожидаемо как малое значение (получили квадрат =16).

Если бы был получен не квадрат, то выполняется переход в следующую строку и действия повторяются до тех пор, пока не возникнет квадрат, а его возникновение гарантируется. Поясним откуда взялось значение rс(хоц) = 506? Это достаточно простой трюк.

Среди прочих отыскивается наименьший средний вычет rс(хоц), который при суммировании его с КВВ нижней строки модели превысил бы значение модуля N. Само значение rс(хоц) = 506 получено из t нечетного числа, rс(t) до определенной границы не зависит от N. Для некоторых значений t их отображение р(t) = rс(t) = t1tо обратимо, т. е. по значению rс(t) можно восстановить t = р(р(t))^-1=р(rс(t))^-1.

Далее, для любых N набор rс(хо) одинаков до определенного предела (порога, зависящего от N). Зная значение rс(t) = 506, найдем и значение t. Извлекаем квадратный корень и округляем до меньшего целого t1 = 506 = 22,49, тогда значение tо= t1+1 и t = t1 + tо.
Фактически получены значения tо = 23, t1 = 22 их сумма t = t1 + tо =22 + 23 = 45. По значению t можно восстановить все элементы строки, в которой оно лежит.

Поиск центра интервала. Нам требуется определить точку хоц центра замкнутого интервала, в которой КВВ полный квадрат. Еще одно свойство СМ-модели обеспечивает решение и этой задачи. Свойство реализуется достаточно простой формулой
хоц(t) = (N t) = (1961 45) = 958. Итак, центр найден хоц(t) = 958.

Проверим, действительно ли, в этой точке КВК rл(хоц) = 16.
rл(хоц) = хоц (t)²(mod N) = 958²(mod1961) = 917764(1961) = 4²+ 4681961 = 16+ 0 = 16 =4².
Поиск границ интервала. При наличии центральной точки интервала и КВК в ней границы интервала находятся по зависимостям ЗРД Гп, Гл = хоц (rл(хоц)).

Алгоритм решения ЗФБЧ с учетом области ТКВК

Необходимость решения ЗФБЧ в большой мере диктуется и определяется требованиями информационной безопасности взаимодействия объектов и субъектов между собой при обмене сообщениями. Используются разнообразные алгоритмы, и эффективность части из них определяется стойкостью относительно проводимых нарушителем атак.

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

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

В алгоритме задается составное число N = рq = dmdб где р и q простые числа высокой разрядности. Для удобства изложения при описании воспользуемся числовым примером, в котором р и q простые числа не очень высокой разрядности, что позволит без больших усилий воспринимать текст и понимать (проверять) практически все результаты промежуточные и окончательные.

Задача 3. Пусть задано составное число N = рq = 2501, необходимо найти его делители р и q. Предварительно находим пороги ТКВК хов1 = N=2501= 50,0099, ТССС хон1=1201, rсн1(t) = 2450.

Алгоритм

1. Заполняется первая строка. Левый, средний и правый вычеты rл(1)=1, rс(1) = 626, rп(1)=2500.
х1 = 2500, хо = 1, t = N 2 = 2501 2 = 2499, tп = 1.
В последней строке СММ rл(0) = 1251 + 625 = 1876, смежные значения х1 + хо = N = 2501,
х1 = 1251, хо = 1250, разность t = х1 хо = 1, rс(t =1) = 0, tп = N 2, rп(0) = 625.

2. Определяем циклически в области ТКВК номер строки меньшего среднего вычета со свойством ССС (из перебора исключаются все строки до верхнего 1-го порога среднего вычета) хо = N=1876=43,3 квадрат этого значения (округление в меньшую сторону) дает для rс(хо) = 625 + 43² = 2474, это меньше 1-го порога равного 2501.

Повторяем цикл, увеличиваем еще на единицу номер строки хо = 43 +1 = 44.
Следующее значение rс(хо) = 625 + 44² 2501= 2561 2501 = 60 превышает порог на 60. Значение rс(хо) не соответствует ССС. Увеличиваем еще на единицу номер строки хо = 45, тогда rс(хо) = 625 + 45² 2501 = 2650 2501 = 149.

Значение rс(хо) превышает порог, но также не соответствует свойству ССС.
Увеличиваем еще на единицу номер строки хо = 46. Тогда средний вычет имеет свойство ССС rс(хо) = 625 + 46² 2501= 2741 2501 = 240 = 1516.

3. Вычисляем значение разности t = x1 -xо (нечетного t в области ТССС) t = 15 + 16 = 31.
4. Определяем для этого t номер центральной строки хоц (t) = (N t) = (250131) = 1235.
5. Находим для хоц (t) квадратичный вычет центральной строки замкнутого интервала.
rл(хо)=хо (t)²(mod N) =1235²(mod2501) = 46² КВК.

6. Вычисляем делители с использованием НОД
dб = НОД(N, 46+1235) = 61; dm = НОД(N, 1235 46) = 41.
7. Проверка N = рq = 4161 =2501. Делители N успешно найдены.

Задача может решаться иначе:

Известно (автору), что в области ТКВК для RSA-чисел появляются два средних вычета со свойством ССС вначале с большим (при меньшем хо) значением, и ниже его с меньшим (в примере это rс(хо) = 240). Начать поиск решения можно с большего rс(хо). Покажем на примере, как это происходит.

Задано составное число N = рq = 2501, необходимо найти его делители р и q. Предварительно находим пороги ТКВК хов1 = N=2501= 50,0099, ТССС хон1=1201, rсн1(t) = 2450.

Первая строка. Левый, средний и правый вычеты rл(1) = 1, rс(1) = 626, rп(1) = 2500.
х1 = 2500, хо = 1, t = N 2 = 2501 2 = 2499, tп = 1.
В последней строке Вычисляем сумму и разность смежных слагаемых N = 1250 +1251, rл(0) = 1251 + 625 = 1876, смежные значения х1 + хо = N = 2501, х1 = 1251, хо = 1250, разность
t = х1 хо = 1, rс(t =1) = 0, tп =N 2, rп(0) = 625.

В цикле по хо от хо = 1 вычисляем rс(хо) и проверяем его принадлежность области ТССС. Если rс(хо) принадлежит ТССС, то переходим к П.3 алгоритма, если не принадлежит, то увеличиваем значение хо = хо +1 и повторяем действия цикла.

На пятом шаге хо = 5 получаем значение t =N -2xо = 2501 -10 =2491 rс(хо =5) =(t² 1)(modN) =650. Флексия 650(mod10)=0 {0, 2, 6} говорит о том, что средний вычет может иметь свойство ССС. Устанавливаем из смежных ли чисел произведение равное 650. Извлекаем квадратный корень t0=650 =25,49, t1 =t0+1=25+1=26.
Находим произведение р= 2526= 650, редуцированный вычет принадлежит ТССС.
Вычисляем значение нечетного t в области ТССС t = 25 + 26 = 51.

Определяем для этого t номер строки хоц (t) = (N t) = (2501 51) = 1225.
Находим для хоц (t) квадратичный вычет (левый в СММ)
rл(хо) = хо (t)²(mod N) =1225²(mod2501) = 5².

Вычисляем делители с использованием НОД
dб = НОД(N, 5+1235) = 61; dm = НОД(N, 1235 5) = 41.

Проверка N = рq = 4161 = 2501. Такая схема также приводит к успешному решению.

Подробнее..

Категории: Информационная безопасность , Алгоритмы , Алгоритм , Математика , Криптография , Модель , Натуральный ряд чисел , Вычет , Кольцо

Факторизация и эллиптическая кривая. Часть III

23.10.2020 12:08:13 |

Автор: admin

Прочие статьи цикла

Факторизация чисел и методы решета. Часть I
Факторизация чисел и методы решета. Часть II
Факторизация и эллиптическая кривая. Часть III

Использование эллиптических кривых (ЭК) для решения разнообразных задач криптологии коснулось каким-то боком и факторизации чисел. Здесь будем рассматривать вопрос, касающийся ЭК и не только в связи с проблемой факторизации составного нечетного натурального числа (СННЧ), но несколько шире.

Если пройтись по Интернету и по статьям об ЭК на Хабре, то после этого возникает мысль, что существует определенный пробел всех без исключения публикаций, включая и объемные бумажные книги. Авторы почему-то считают само-собой разумеющимся понимание природы ЭК и ее аддитивной группы, ее появление. На самом деле ЭК и ее группа (мое мнение) это чудо!

Группа точек плоскости, множество которых замкнуто по операции сложения, оказалась каким-то образом встроена в ЭК и мы об этом до сего дня не знали бы, не располагая теорией групп, и даже при наличии теории групп, без гения Эйлера и Пуанкаре, которые нам эту группу открыли. В свое время Иоганн Кеплер открыл человеку законы движения Планет и качественно описал их траектории, но только гений Ньютона смог объяснить природу этих законов.

Правда для этого ему пришлось открыть свои законы движения/тяготения и изобрести дифференциальное и интегральное исчисления. Задача взятие двукратного интеграла от второго закона Ньютона, в котором ускорение вторая производная пути, решением имеет плоскую кривую второго (не третьего, не путать эллипсы траектории планет, спутников и эллиптические кривые в криптологии) порядка, что до И. Ньютона было открыто И.Кеплером.

Объект математики эллиптические кривые давно изучается геометрией(сама кривая, точки, касательные, ЭК, которая может быть изображена геометрическим рисунком, и др.) и алгеброй (уравнение ЭК, коэффициенты и корни уравнения, дискриминант, инварианты и др.). Но только в наш информационный век нашли важное практическое применение такому объекту.

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

Предварительные сведения из высшей алгебры

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

Вначале приведем кратко математические основы, без уяснения структур (группа, подгруппа, поле, подполе, кольцо, идеал, подкольцо) которых затруднено восприятие текста. Понятно, что задача не из простых (это передний край науки о числах) и требует от читателя определенной предварительной подготовки, но такова специфика Хабра наличие читателей разного уровня подготовки.

Дадим несколько необходимых определений высшей алгебры.

Определение. Алгебраической (конечной) группой называется множество элементов (чисел, многочленов, матриц и др.) над которыми задана одна операция. В зависимости от природы элементов (матрицы, подстановки, вычеты по модулю N) операции могут различаться, но названия их, как правило, всегда одинаковы: сложение либо умножение. В случае групп вычетов по модулю N множество элементов группы может быть целыми или даже натуральными пополненными нулем числами от 0 до N 1. Элементы группы отождествляются с номерами строк и столбцов таблицы Кели.

Эта единственная операция группы по назначению может быть сложением (+), и тогда группа называется аддитивной, или умножением (), и группа мультипликативная. Обеим операциям групп присущи близкие свойства (описываемые развернуто в учебной литературе): ассоциативность, замкнутость, наличие нейтрального и противоположного (обратного) элементов, а при сохранении результата операции в случае смены операндов местами коммутативность.

Пример G

Таблица Кели Аддитивная группа вычетов по модулю N=23 (23 порядка)

В клетках таблицы суммы номеров строки и столбца по модулю N, пересекающихся в ней.

Таблица Кели Мультипликативная группа вычетов по модулю N=23 (23 порядка)

В этой группе отсутствует нулевой элемент. Обратный мультипликативный элемент находят по этой таблице: вход номер строки и движемся по строке пока в некоторой позиции не встретим единицу; номер столбца клетки с единицей обратный элемент к номеру строки. Например, для элемента 19 (строка 19) перемещаемся по строке до 17-го столбца, т.е. до клетки с 1. Номер столбца 17 и есть обратный элемент для 19-го. Действительно, их произведение по mod23 дает 1917(mod 23) =323(mod23) =1 единицу.

Поясним также свойство замкнутости операции в группе. Множество элементов, образующих конечную группу, конечно и постоянно. Результатами операции всегда являются элементы из исходного множества. Среди элементов группы только один-нейтральный элемент (1) или (0), и каждый элемент имеет себе обратный (а^-1) (или противоположный (-а)). Операция над элементами не выводит результат за пределы исходного множества элементов группы.

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

Определение. Алгебраическим числовым конечным простым полем вычетов по простому модулю N называется и обозначается множество (k, GF(p), Fp) элементов (чисел от 0 до N 1), над которыми заданы две операции сложение (+) и умножение (). Модуль N, по которому формируются элементы поля, должен быть обязательно простым числом.

Среди элементов обязательно имеются противоположные (-а) к каждому элементу и один нейтральный (0) по сложению, обратные (а^-1) к каждому элементу и один нейтральный (1) по умножению. Поле образовано в соответствии с операциями допустимыми в нем (+) и () двумя соответствующими мультипликативной Fр* порядка р-1 и порядка р аддитивной группами.

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

Такие поля GF(pⁿ) появляются как результат расширения определенной степени n простых полей GF(p).

Определение. Расширенное поле К-поле GF(pⁿ), содержащее заданное поле GF(p) в качестве подполя, что записывают так К/k, где k = GF(p) простое поле, К=GF(pⁿ) -расширение поля k. Элементами поля расширения K являются все элементы (числа) простого поля k и все многочлены степени не превышающей n-1. Иллюстрацией групп поля и результатов обеих операций в группах для примера поля GF(7) сложения и умножения являются числовые таблицы 1 и 2 помещенные в примерах ниже.

Пример P. Пусть задано конечное поле вычетов по модулю два двоичное поле GF(2) = {0,1}. Построим поле расширения степени, например, n = 6, что обозначается так GF(2⁶ ). Это поле образуют числа 0, 1 и все возможные многочлены степени, не превышающей 5. Когда выполняются действия с многочленами в мультипликативной группе поля, то степень результата (произведения многочленов) degd(x) может превышать показатель степени n = 5.

При этом условие замкнутости множества элементов мультипликативной группы нарушается. Чтобы вернуть результат в поле сделать его элементом поля, результат произведения делят на специально выбираемый многочлен (например, f(х) = х⁶ + х + 1) степени равной степени расширения, т.е. n = 6. Окончательным результатом операции считается остаток от деления.

Такой многочлен в сущности формирует поле и не должен иметь корней в простом поле, он называется неприводимым многочленом, т. е. он не раскладывается на сомножители в поле. Действительно, при f(0) =0+0+10 и f(1) =1+1+1(mod2) =10, т.е. элементы 0 и 1 из GF(2) не являются корнями f(x). Говорят результаты операций расширенного поля приводятся по модулю неприводимого многочлена. Кроме того, все коэффициенты многочленов в этом поле принадлежат простому полю и приводятся по модулю простого поля (простого числа).

Таким образом, результаты операций в поле приводятся по двойному модулю, что иногда обозначается так d(х)(moddp,f(x)), где р простое число, формирующее простое поле, а f(x) неприводимый многочлен степени равной степени расширения простого поля.

Поле Галуа GF( $inline$ ). Неприводимый полином P(x) = x^6 + x +1 = 1000011, = 2

Первая колонка таблицы поля Галуа GF( $inline$ ) степени примитивного элемента =2, пробегающие все элементы поля, которые упорядочены по этим степеням. Вторая колонка многочлены поля. Третья векторное (двоичным числом ) представление элементов расширенного поля. Далее представление ( $a_{10}^i$ ) десятичным числом, порядок (е) элемента, обратный вектор, степень обратного, обратный в десятичном представлении, вес элемента. Располагая такой таблицей поля, таблицы Кели не нужны.

Определение. Алгебраическим числовым конечным кольцом вычетов по составному модулю N (обозначается Z_N) называется множество элементов (чисел от 0 до N 1), над которыми заданы две операции сложение (+) и умножение (). Модуль N, по которому формируются элементы кольца должен быть составным (не простым) числом.

Если модуль сделать простым числом ( неприводимым многочленом ), то кольцо преобразуется в простое поле (поле многочленов ). Среди элементов кольца обязательно имеются противоположные (-а) к каждому элементу и нейтральный (0) по сложению, но обратный элемент (а^-1) существует не для каждого элемента и нейтральный элемент (1) по умножению в кольце может отсутствовать.

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

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

Элементы теории эллиптической кривой

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

Одним из примеров использования известных свойств конечных аддитивных групп является разработка алгоритмов решения задачи факторизации больших чисел (ЗФБЧ), другими алгоритмы цифровой подписи и/или шифрования документов (сообщений), в которых привлекаются не совсем обычные группы. В алгоритмах используются точки алгебраической кривой, заданной над конечными структурами (поле, кольцо), редуцированной (вычисления приводятся по модулю N) и называемой эллиптическая кривая в форме Вейерштрасса (1815-1897).

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

Сама кривая плоская ее коэффициенты а и b; точки ЭК (х, у) описываются через две х и у переменные, значения которых принадлежат конечному простому полю Галуа GF(p) (но могут принадлежать и расширенному полю GF(pⁿ), как в некоторых стандартах электронной цифровой подписи (ЭЦП)), таким образом, в алгоритмах используется декартово произведение поля GF(p)GF(p).

Операция сложения точек ЭК это специальная операция (+), заключительный шаг которой взятие результата по модулю N простому или (для кольца) составному. При составном модуле ЭК задана не над полем, а над кольцом, что существенно изменяет свойства рассматриваемых объектов, сохраняя основные из них и существенные для целевой задачи.

Рассмотрим самые начальные сведения из теории и арифметики эллиптических кривых. Необходимо уяснить ряд моментов. Задание ЭК, смысловое значение параметров ЭК, множество целых точек и возможность их сложения между собой. Операция сложения точек. Эти сведения и их понимание необходимы для доступного изложения алгоритма факторизации натуральных (целых) чисел, который давно известен специалистам-криптологам по публикациям Х. Ленстра от 1987 г и более поздним усовершенствованиям Р. Монтгомери 1992 [2, 4, 5, 6, 7,10 ].

Для задания эллиптической кривой Е_a,b(F_р) над полем вначале задается поле характеристикой конечного поля простым числом N или p>3. Для задания коэффициентов а и b эллиптической кривой Е (а, b), определенной над конечным простым полем Fр, можно воспользоваться подходом из отечественного стандарта (см. ГОСТ).

Определение. Эллиптической кривой Е_a,b(F_р) называется множество {(х, у)} пар целых чисел, элементов поля х, уFр, удовлетворяющих соотношению
$inline$ , где а, b Fр.

После преобразований сравнения получается более простой вид $inline$ .

У Е_a,b(F_р) дискриминант многочлена правой части равен -4а³ + 27b² 0(modp) и не сравним с нулем по модулю р и многочлен не имеет кратных корней Правильнее сказать так называется группа точек ЭК, а не сама кривая.

Но такая замена понятий в чем-то упрощает изложение. Коэффициенты ЭК а, b определяются соотношениями а 3k(modp); b 2k(modp); где
k J(E)(1728 J(E))^-1(modp); J(E)17284а³(4а³+27b²)^-1(modp) инвариант ЭК; J(E) 01728.

Пары чисел (х, у), удовлетворяющие уравнению ЭК, называются ее точками, обозначаемыми Q(х, у), а х и у координатами точки. В группу точек ЭК в качестве нейтрального элемента включается специальная точка (О) точка, удаленная в бесконечность (), ее координаты обычно не вычисляются. Порядок группы #E(Fq). На множестве всех целых точек ЭК вводится операция сложения. Для двух произвольных точек Q₁(х₁, у₁) и Q₂(х₂, у₂) кривой Е(а,b) суммирование выполняется по различающимся формулам в зависимости от соотношения координат точек.

Построение группы точек ЭК

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

Уравнение ЭК $inline$ получает вид. Эта кривая задана над простым полем Fр с характеристикой р = 23 простое число. Кривая редуцирована, т.е. приведена по модулю р.

Решение. В заданном поле 23 элемента, но каждая точка кривой имеет две координаты, т.е. кривая задана над плоскостью, образуемой декартовым произведением множества элементов поля $F_pF_p = F_{23}F_{23}$ . Группа этой кривой циклическая с генерирующей точкой Р(0, 1). Покажу в деталях, как возникает аддитивная группа ЭК над полем для тех, кто не изучал теорию групп и для тех кто изучал, но возможно плохо ее помнит.

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

Построим таблицу для левой и отдельно для правой частей ЭК при пробегании переменными х и у по всем элементам поля $F_p= F_{23}$ . Точками группы ЭК будут те, для которых правая и левая части ЭК совпадают своими значениями (их отыскиваем в таблицах П1, П2). Например, первое совпадение получаем при у = 1 и х = 0, вычеты левой и правой части равны 1=1

Таблица П1Значения вычетов левых и правых частей ЭК $inline$

Таблица П2 упорядоченные вычеты правой части (по х)

Далее в этой таблице П1 будем находить одинаковые значения вычетов правой и левой частей ЭК по модулю 23 (выделены заливкой). Всем вычетам соответствуют значения х из 2-й строки таблицы П1. Так как в левой части выписан квадрат переменной у, следовательно, при равных значениях вычетов частей одному х будут соответствовать два значения у. Но отрицательные значения модулярная арифметика позволяет легко перевести в положительные, т.е. для ( у1) имеем р у1 = у2.

Значению элемента поля 0 соответствует в правой части 1 и у = 1, т.е. у1=1,
у2 = 23 1 = 22. Теперь выпишем в таблицу П3 группы точек ЭК координатные пары (х, у) и порядки точек: $inline$ (mod p), а = 1, b = 1, дополнительно в группу включается -удаленная точка (28-я по номеру, обозначена ).

Это очень важная точка О нейтральный элемент группы, она не имеет координат. Точке (27-й) с координатой х = 4 пары нет, она сама к себе противоположная. Удвоение этой точки ( $Р_{27} + Р_{27} = Р_{28}$ ) равно -удаленной точке.

В последней строке таблицы 3 вписан порядок (ord) точки.

Математик Кэли предложил характеризовать множество результатов таких операций таблицами, которые получили его имя (таблицы Кэли), таблицей сложения для аддитивной группы и таблицей умножения для мультипликативной. При построении таблицы П4 (таблицы Кели) группы точек и наличии таблицы П3 можно использовать не координаты точек, а их порядковые номера, что более удобно. Номера точек требуют меньше места для записи, чем координаты.

Таблица П4 Сумма пар точек группы эллиптической кривой $inline$ над простым полем GF(23).

В таблице группы ЭК (таблица П4) показаны заливкой разного цвета выявленные подгруппы разного порядка.

Суммирование точек ЭК групповая операция

Таблица П4 суммы точек группы ЭК получена путем сложения пар (Q1 =(x1, y1); Q2 =(x2, y2)) точек по специальным формулам, а результатом будет третья точка Q3 =(x3, y3).

При равенстве обеих координат у точек х₁= х₂, у₁= у₂ 0 имеем удвоение или сумму одной точки с собой. Результирующая точка Q₃(х₃, у₃) получает координаты, вычисляемые по формулам, где коэффициент или тангенс угла наклона прямой (касательной или секущей), соединяющей точки Q1, Q2:

(3х₁² + а)(2у₁)^-1(modp);
х₃²-2х₁(modp);
у₃ (х₁-х₃)-у₁(modp).

При х₁ х₂ суммой точек Q₁(х₁, у₁) и Q₂(х₂, у₂) является точка Q₃(х₃, у₃), которая получает координаты, вычисляемые по формулам:

(у₂-у₁)(х₂-х₁)^-1(modp);
х₃²-х₁-х₂(modp);
у₃ (х₁-х₃)-у₁(modp).

При х₁= х₂, у₂= -у₁(modp), точки лежат на вертикальной прямой, пересекающей в них ЭК. Эта прямая пересекает и третью точку (О) ЭК, которая удалена в бесконечности. Сумма двух точек Q₁(х₁, у₁) и Q₂(х₂, у₂) называется нейтральным элементом (нулевой точкой O) группы, координаты которой не определяются.

Суммирование с этой точкой любой другой точки не изменяет эту другую и дает результат Q + О = О + Q = Q +O = Q.

Точка Q имеет кратность k или называется просто кратной точкой Е(а, b), если для некоторой точки РЕ(а, b) выполнено равенство Q = Р + Р + ...+ Р = kP.

Порядок группы и элемента группы

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

Определение. Порядок (ord, период) элемента в группе это наименьшее положительное число (кратность k элемента) в операции, при котором результат операции обращается в нейтральный элемент.

а + а +...+ а = ka = 0 в аддитивной или
aaa...a = a^k = 1 в мультипликативной группе.
Период элемента кратен порядку группы, т.е. делит нацело порядок группы.

Подгруппы точек разных порядков: 27, 28; 2 порядка (она входит в п/группу 14 порядка),
15, 16, 27, 28; 4 порядка,
7, 8, 19, 20, 21, 22, 28; 7 порядка,
7,8,9,10, 11,12, 17,18,19,20,21, 22,27, 28; 14-го порядка,

Пример П1. Все 28 элементов образуют циклическую группу ЭК, но генератором может быть только элемент 28 порядка, например, Р (0, 1). Многократно суммируя этот элемент с собой сумма проходит через все элементы группы.

Порядок каждого из элементов (точек) группы находится многократным суммированием по таблице П4 пока сумма не станет нейтральным элементом. Например, $Р_{15} +Р_{15} +Р_{15} +Р_{15} =Р_{28}.$
Кратные элементов образуют подгруппы (циклические): $Р_{15}, Р_{15} +Р_{15} +Р_{27}, Р_{15} + Р_{27} = Р_{16}$ ,
$Р_{15} + Р_{16} = Р_{28}$ ; элементы $Р_{15}, Р_{16}, Р_{27}, Р_{28}$ образуют циклическую подгруппу 4-го порядка.
Это нормальная подгруппа и по ней можно разложить исходную группу в смежные классы. В свою очередь эти смежные классы рассматриваются как элементы факторгруппы, т.е. они образуют группу 7-го порядка по числу смежных классов.

Операция суммирования всех целых точек Е(а,b) вместе с нулевой точкой О (нейтральный элемент) порождает конечную (коммутативную) аддитивную (абелеву) группу порядка q, где q p. Для этого порядка справедливо установленное Хассе соотношение р + 1 2р < q < р + 1 + 2р. Если для точки Q выполнено Q + Q + ...+ Q = kQ = О, то k порядок точки Q.
Группа, как известно, имеет множество замечательных свойств. Так $Е(Fq)C_{n_1} C_{n_2};$
$inline$ циклическая группа порядка n. Одно из свойств односторонность зависимостей кратных базовой точке других точек группы нашло применение с учетом использования модулярной арифметики в двухключевой криптографии, а в ней для шифрования и цифровой подписи.

Пример П2. Вычисление порядка группы ЭК $inline$ над простым полем GF(23). Пусть генератор группы с порядком 28 Q =(0, 1).Тогда имеем полный список кратных генератору точек:

1Q =(0, 1); 2Q =( 6,-4); 3Q = (3,-10); 4Q =(-10,-7); 5Q =(-5, 3); 6Q =(7,11); 7Q =(11,3);
8Q =(5,-4); 9Q =(-4,-5); 10Q=(12,14); 11Q =( 1, -7); 12Q=(-6,-3); 13Q=(9,-7); 14Q =( 4,10);
15Q=(9,7); 16Q=(-6, 3); 17Q= ( 1, 7); 18Q =(12,-4); 19Q=(-4, 5); 20Q=(5, 4); 21Q=(11,-3);
22Q=(7,-11); 23Q=(-5,-3); 24Q= (10,7); 25Q = (3,10); 26Q=( 6, 4); 27Q=(0,-1); 28Q=();

Пример S. Суммирование кратных точек группы ЭК. При наличии полного списка кратных точек группы упрощается вычисление комбинаций таких кратных точек. Пусть требуется вычислить сумму 3Q =(3,-10) и 7Q =(11,3).

Решение. Очевидно должно быть 3Q +7Q =10Q. Убедимся в этом, будем считать, что суммируются две какие-то точки из группы: Q1 =3Q и Q2 =7Q их координаты заданы.

Обрабатывается результирующая точка Q₃(х₃, у₃), она получает координаты, вычисляемые по формулам:

(у2-у1)/(x2-x1)(mod23)=(3-(-10)/(11-3)(mod23)=13/8(mod23); Так как 8^-1 3(mod23), то 13/8 133(mod23)=16;
х₃²-2х₁(modp)= -x1 -x2(1616-3-11)(mod23)=12;
у₃ (х₁-х₃)-у₁(modp)(x1-x3)-y1(mod23)(16-12-(-10))(mod23)=14.
Ответ х3=12; у3 =14 или Q3 = (12, 14)=10Q.

Отсюда следует, что для понимания проблемы применимости ЭК в криптографии первой решаемой задачей должна быть задача установления и последующий анализ группы G точек конкретной ЭК. С этого важного положения мы и начнем рассмотрение и установление группы G точек ЭК над фиксированным конечным простым полем F(р), элементы которого оказываются координатами обнаруживаемых точек кривой. Здесь же определим порядок каждой найденной точки, порядок самой группы G, перечислим подгруппы, входящие в состав основной группы G.

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

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

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

В работе излагается один из известных подходов к решению задачи факторизации больших чисел (ЗФБЧ), использующий математику эллиптических кривых (ЭК). Об этой математике, а точнее о технике вычислений приведу цитату авторов из [ 1 ]

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

Метод факторизации числа, использующий эллиптическую кривую

Алгоритм факторизации числа

В этом вероятностном алгоритме отображены основные черты его изложения в работах [3, 7, 9].

1. Выбираются числа M и N и числа 1< a, x, y< N;

2. полагаем b = у² х³ ах(modN). После чего для ЭК у² х³ + ах + b(moN), где а, b, х, у Fр выбираем точку Р = (х, у);

3. Находим d = НОД(N, 4а³ + 27b² ), если 1< d< N, то d | N и задача решена, если d = 1, то переход к следующему шагу;

4. Выбираем число k = НОК(2, 3,..., М), М -натуральное число;

5. Вычисляем кратные точки kР на ЭК, k = 2,3,..;

6. Вычисляем d = НОД(N, х_k х_k-1),
если 1< d< N, то d | N задача решена, делитель N найден,
если d = 1, то либо переходим к шагу 4 и увеличиваем k, либо возвращаемся к шагу 1 и выбираем параметры новой кривой,
если d = 1, то переход к шагу 4 и уменьшаем k.

Для факторизации задается составное нечетное число N. Выбирается целое число k равное произведению степеней небольших простых чисел с ограниченными показателями степени:k = 2^d23^d35^d5...r^dr. Здесь 2, 3, 5, ..., r несколько первых простых чисел, а d2, d3, d5,...dr -малые положительные числа. После этого вычисляется а^k-1 по модулю N и затем (N, а^k-1), что требует для вычисления 2og₂ (2kN) операций. При этом даже если k и N имеют в записи по тысяче знаков время расчетов оказывается вполне приемлемым.

Если (N, а^k-1) N, то получаем нетривиальный делитель числа N. При этом N раскладывается на два множителя и, если они составные, то к каждому из них применяется эта же процедура. При (N, а^k-1) = N, переходим к новому выбору параметра а. Если же (N, а^k-1) = 1, то переход к новому значению k большему предыдущего. В работе [3] приводится средняя оценка сложности:

е ^{((2 + о(1))ogpogogp)^1/2}og²N для этого алгоритма, здесь р минимальный простой делитель N.

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

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

При этом возможно, что решение задачи факторизации появляется раньше, чем будет найден порядок точки в процессе вычисления кратных точек. Нахождение суммы двух точек требует вычисления коэффициента , для чего привлекается расширенный алгоритм НОД(N, х₂-х₁) Евклида.

Если значение d = НОД >1, и d N, то делитель N найден и факторизация выполнена. В примере все вычисления проводятся в конечном числовом кольце вычетов с модулем
N = 455839 = 599761. Выбрана ЭК Е: у² х³+ 5х-5(modN), где
а = b = 5 ZN и дискриминант Е(а, b) равный -4а³ + 27b² 0(modN) не сравним с нулем по модулю N. Задана также рациональная точка Р=(1,1) на ЭК. Будем многократно суммировать эту точку с собой. Рано или поздно такое суммирование приведет к результату-нейтральному элементу-точке (0), так как каждый элемент алгебраической структуры имеет период.

Конечно, это суммирование очень длительный процесс, но алгоритм, оказывается, может приводить к решению часто и на промежуточном шаге вычислений. Поэтому при больших числах сначала будем находить небольшую сумму точек, например,
10! Р = 2⁸ 3⁴ 5²7Р = 3628800Р и при их недостатке увеличивать число.

Начнем с удвоенной точки Р₂ = P + P=2! Р =12Р.
Обрабатывается точка Р₂ = 2Р. Находим для Р₂ значение коэффициента и затем координаты точки Р₂
(3х₁² + а)(2у₁)^-1(modN) = (31² + 5)/(21)4(modN);
х₂²-2х₁(modN)= 4²-21(modN) =14;
у₂ (х₁-х₂)-у₁(modN)=4(1-14)-1(modN)=-53(modN)=>-53(modN)=455839-53=455786.

При фиксированном х₂, х₂ 0, на ЭК имеется две точки с разными координатами у₂, дополняющими друг друга до модуля. Легко убедиться подстановкой координат в уравнение ЭК, что полученная точка Р₂ = ( х₂, у₂) = (14, -53) лежит на ЭК.
у₂² = (-53)² = 2809 = 14³ + 514-5 = 2744+70-5 = 2809(modN), Р₂ Е. Левая часть уравнения равна правой.

Вычисление в формуле содержит деление на 2у, но в операции деления в алгебраических структурах нет. Деление заменяется умножением на обратный элемент, получаемый через НОД.
Далее вычисляем точку 2Р₂ = 4Р и к ней приплюсуем точку Р₂ = 2Р.

Обрабатывается точка 2Р₂ = 4Р. Находим для 2Р₂ значение коэффициента и координаты 2Р₂
(3х₂²+а)(2у₂)^-1(modN) =(3196 + 5)/(2(-53))=-593/106 = 322522(mod455839);
х₂²-2х₁(modN) =322522²-214(modN)=104020440484-28(455839) =259851;
у₂(х₁-х₂)-у₁(modN)=116255(mod455839).

Проверка принадлежности точки Р= (259851, 116255) эллиптической кривой:
Е: у² х³+ 5х-5(modN); 116255²(mod455839)=54514;
259851³ + 5259851 -5 =17545800113472051+1299255-5(mod455839) = 54514.

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

Получение мультипликативного обратного элемента в кольце вычетов

Пример ОБ.Определение обратного элемента возможно, если элемент обратим (в конечном кольце вычетов не все элементы имеют обратные). Для выражения =-593/106(mod455839) имеем как раз такой случай, т.е. для элемента 106 необходимо определить обратный к нему элемент в конечном кольце по модулю N.

Покажем как это делается в нашем примере; привлекается расширенный алгоритм Евклида поиска наибольшего общего делителя двух чисел: модуля 455839 и знаменателя числа 106:

455839 = 4300106 + 39;
106 = 239 + 28;
39 = 128 + 11;
28 = 211 + 6;
11 = 16 + 5;
6 = 15 + 1.

Получили, что НОД(455839, 106) = 1. После этого обратным ходом находим обратный элемент для числа 106;

1= 6-5 = 26-11 = 228-511 = 728-539 = 81707106-19455839 => 81707106-19455839 1(mod455839) =>81707106 1(mod455839) и, окончательно, 1/106 81707(mod455839).

Тогда =-593/106(mod455839) => =-59381707(mod455839) = 322522.
Для получения точки Р₃ надо суммировать две разные ранее найденные точки 2Р и 4Р. Вычисляется коэффициент (по другим формулам) для этого случая и координаты точки.

Далее вычисляем точку Р₃ = 3! Р = 123Р = 6Р = 2Р + 4Р. Нашли уже ранее значение 2Р₂ = 4Р, которое получали суммированием точки 2Р с собой. Для 2P + 2P = 2Р₂ определяем значение коэффициента. Используем те же формулы.

Обрабатывается точка 3Р₂ =3! Р= 6Р. Находим для 3Р₂ значение коэффициента и ее координаты
(у₂-у₁)(х₂-х₁)^-1(mod455839);
х₃²-х₁-х₂(modN) = 195045(mod455839);
у₃ (х₁-х₃)-у₂(modN) = 123227(mod455839).

Продолжая вычисления тем же порядком для точек Р₄ = 4! Р, Р₅ = 5! Р Р₈ = 8! Р, для которой знаменатель в формуле для получает значение равное 599, в процессе вычисления
d= НОД(455839, 599) получаем d = 599, т.е. это делитель N, что и завершает задачу факторизации. Другой делитель получаем делением на первый N/599 = 761. Оба делителя простые числа.

Еще одно применение ЭК в криптологии это построение криптографической системы (КГС).

Простая криптографическая система на эллиптических кривых

В сети обмена данными для всех абонентов задается общая редуцированная эллиптическая кривая Е_a,b(F_р) над полем F_р и порождающая точка
Р = (х, у) на ней.

Каждый абонент, используя точки аддитивной группы этой ЭК формирует свои открытый и закрытый ключи. Ниже в примере 2 рассматривается простой вариант криптографической системы (КГС) с возможностью шифрования/расшифрования сообщений элементами группы точек ЭК. Понимание основ теории эллиптических кривых и смежных вопросов открывает возможности использование богатого арсенала их средств в целях повышения уровня безопасности информационных систем и предотвращения возможных нападений на них.

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

Шифрование: Пусть отправитель В посылает получателю А сообщение в виде исходного текста (ИТ) одного трехбуквенного слова ДОМ
Эти символы необходимо преобразовать в цифровую (двоичную) форму, например, ASCII кодом.
ИТ = {ИТ1 = Д = Е4 = 1110 1000, ИТ2= О=ЕЕ = 1110 1110, ИТ3 = М = ЕС = 1110 1100}

Для посимвольного шифрования сообщения абоненту В требуется открытый ключ абонента А. Этот ключ абонент А формирует и публикует как общедоступный в сети связи.
Открытый ключ А: точка генератор группы ЭК Q=P5=(3,3). Выбор этой точки достаточно произволен.

Далее А вырабатывает случайное число а = 3 которое для абонента А является личным (иногда называют секретным ключом) ключом. Точка Q умножается на личный ключ. Получается точка N =аQ =3Q =3P5 = P11 =(6,3). окончательно открытый ключ имеет вид: Q,N.

Отправитель В вырабатывает свое случайное число b=2 и умножает обе точки ЭК открытого ключа Q и N на b=2: получает точки R=bQ =P4 = (2,5); S =bN = baQ = P8 = (4, 5).

Далее координаты точки S = (4, 5) преобразуются к двоичному представлению S = P8 = (4, 5) = (0000 0100, 0000 0101). Символы сообщения и координата хs преобразуются после этого в шифрованный текст (ШТ). Простейший вариант преобразования текста сообщения операцией ЕХОR
ШТ ={шт1 = 1110 1100; ШТ2 = 1110 1010; ШТ3 =1110 1000}.

Отправитель В посылает получателю А точку ЭК R и шифрованное сообщение ШТ.
Расшифрование: выполняет сторона А получатель сообщения. Точка R кривой умножается на личный (секретный) ключ (а) абонента А: аR =аbQ = S = 3P4 = P8 = (4,5), что также дает точку S = P8 = (4,5). После этого абонент А выполняет расшифрование, получая исходный текст ИТ.

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

Пример 2.

k число слагаемых равных точке Рi соответствующей строки. В ячейках таблиц 4 и 5 помещены номера i точек Pi из таблицы 3, где представлены все 13 точек конечной аддитивной группы эллиптической кривой у² х³ + 3(mod7)

Заключение

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

Список использованных источников

[1] Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел.-М.: Мир, 1987. -416с.
[2] Болотов А.А. и др. Элементарное введение в эллиптическую криптографию.Алгебр. и алгоритмические основы.-М.: КомКнига,2006.-328 с.
[3] Василенко О.Н. Теоретико-числовые алгоритмы в криптографии.- М.: МЦНМО, 2003.-328 с.
[4] Жданов О.Н., Чалкин В.А. Эллиптические кривые. Основы теории и криптографические приложения.-М.: Кн. домЛИБРОКОМ, 2012.-200с.
[5] Ишмухаметов Ш.Т. Методы факторизации натуральных чисел.- Казань: Казан.ун-т,2001.-190 с.(http://personeltest.ru/away/www.ksu.ru/f9/bibl/Monograph_ishm,pdf)
[6] Кнэпп Э. Эллиптические кривые.- М.: Факториал-пресс, 2004.-488 с.
[7] Koblitz N.A. Course in namber theory and cryptography.-Springer -Verlag, 1987.
[8] Lenstra H.W. (1987) Factoring integer with elliptic curves. Ann.of Math.126(2),649-673.(http://personeltest.ru/away/www.ams.org/mathscinet-getitem?mr=89g:11125).
[9] Соловьев Ю.П. и др. Эллиптические кривые и современные алгоритмы теории чисел.-Москва-Ижевск: Ин-т компьют-х исслед.,2003.-192с.
[10] Степанов С.А. Арифметика алгебраических кривых

Подробнее..

Категории: Информационная безопасность , Научно-популярное , Алгоритмы , Математика , Криптография , Модель , Число , Эллиптическая кривая , Делитель

Перевод Что такое machine learning?

29.04.2021 12:05:53 |

Автор: admin

Данный пост содержит выдержки из одноименной статьи Дэниела Фагеллы, руководителя отдела исследований в компании Emerj от 26.02.2020. Дэниел является всемирно востребованным экспертом по последствиям ИИ по направлению конкурентных стратегий для лидеров бизнеса и государств; его услугами пользуются ООН, Всемирный банк, Интерпол и ведущие компании.

Слегка укороченный перевод данной статьи служит доказательством концепции, изложенной мной в предыдущем посте от 24.04.2021 Комментарий переводчика, или никто никого не обучает.

Главный тезис указанного поста звучал так:

Мы имеем феномен, который называется усвоением знаний человеком и животными. Этот феномен объясняется теориями усвоения знаний (в частности павловской теорией условных-безусловных рефлексов). В 60-х годах XX-го века компьютерные ученые задались вопросом о том, как создать самообучающуюся машину, и дали классическое определение такой машины (определение дано выше в посте), как способной автоматически усваивать знания из данных, не будучи для этого программируемой. То есть признавалось, что вычислительную машину, в отличие от людей и животных, которые наделены такой способностью по природе, надо еще наделить способностью усваивать знания. Это делается путем строительства специальных моделей машинного усвоения знаний, в основе которых лежит алгоритм машинного усвоения. Строительство таких моделей и алгоритмов и является предметом подобласти ИИ под названием машинное усвоение (МУ).

Приведенный ниже перевод сделан с учетом именно такого понимания термина machine learning. Если вы настроены к такому пониманию , как говорится по-аглицки, upfront враждебно то прошу не тратить своего времени на мои призывы подумать о присоединении к принятому во всем мире пониманию machine learning как машинному (автоматическому) усвоению знаний.

Итак, вот перевод. Прошу отнестись с пониманием (с) ;-). Все очепятки мои

Набрав что такое machine learning? в поисковой строке Google, можно открыть ящик Пандоры форумов, научных исследований и ложной информации и цель этой статьи состоит в том, чтобы упростить определение и понимание термина машинное усвоение благодаря прямой помощи со стороны группы экспертов-исследователей.

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

Эта статья будет разбита на следующие ниже разделы:

Что такое машинное усвоение?

Как мы пришли к нашему определению (посредством разных точек зрения экспертов-исследователей)

Базовые концепции машинного усвоения

Визуальные представления моделей машинного усвоения

Как мы обеспечиваем машины способностью усваивать знания

Обзор трудностей и пределов машинного усвоения

Краткое введение в глубокое усвоение знаний

Цитируемые работы

Интервью по данной теме

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

Что такое машинное усвоение?

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

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

Как мы пришли к нашему определению

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

1. Машинное усвоение в своей основе - это практика использования алгоритмов для разбора данных, усвоения из них знаний, а затем принятия решения или генерирования предсказания о чем-то, что присутствует в окружающем мире Nvidia

2. Машинное усвоение - это наука о том, как обеспечивать компьютеры способностью действовать без явного на то программирования Стэнфорд

3. Машинное усвоение основывается на алгоритмах, которые могут усваивать знания из данных, не опираясь в этом на программирование на основе правил -McKinsey & Co.

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

5. Область машинного усвоения стремится ответить на вопрос о том, как строить компьютерные системы, которые совершенствуются автоматически вместе с опытом, и каковы фундаментальные законы, которые управляют всеми процессами усвоения знаний? Университет Карнеги Мелона

Мы разослали эти определения экспертам, которых мы опросили и/или включили в один из прошлых исследовательских консенсусных опросов, и попросили их ответить своим определением либо предоставить свое собственное. Наше вводное определение отражает разнообразные ответы. Ниже приведено несколько ответов:

Д-р Иошуа Бенжио, Монреальский университет:

Термин не должен определяться использованием отрицаний (отсюда, пункты 2 и 3 исключаются). Вот мое определение:

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

Д-р Данко Николич, CSC и Институт Макса Планка:

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

Д-р Роман Ямпольский, Университет Луисвилла:

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

Доктор Эмили Фокс, Вашингтонский университет:

Мое любимое определение - пункт 5.

Базовые концепции машинного усвоения

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

Представление (набор классификаторов или понятный компьютеру язык)

Оценивание (aka целевая функция/функция оценивания)

Оптимизация (метод поиска; нередко, например, классификатор с наивысшей оценкой; используются как готовые, так и конкретно-прикладные методы оптимизации)

Автор таблицы: д-р Педро Доминго, Вашингтонский университет

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

Визуализации моделей машинного усвоения знаний

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

Модель на основе дерева решений:

Дерево решений

Модель на основе гауссовой смеси:

Гауссова смесь

Нейронная сеть с отсевом

Как мы обеспечиваем машины способностью усваивать знания

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

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

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

Иногда это также происходит непреднамеренно. В качестве одного примера можно взять модельные ансамбли, или комбинации многочисленных алгоритмов усвоения знаний, служащих для повышения точности. Коллективы разработчиков, участвовавшие в конкурсе Приз Netflix 2009 года, обнаружили, что они получили свои наилучшие результаты после того, как совместили своих учеников с учениками других коллективов, что привело к быстрому рекомендательному алгоритму (подробнее о том, почему они не использовали этот ансамбль, читайте в блоге Netflix).

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

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

Обзор трудностей и пределов машинного усвоения

Машинное усвоение знаний не может получать что-то из ничего но оно умеет получать больше из меньшего Доктор Педро Доминго, Вашингтонский университет

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

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

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

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

Глубокое усвоение и новейшие разработки в нейронных сетях

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

Международная конференция по машинному усвоению (International Conference on Machine Learning, аббр. ICML) широко считается одной из самых важных в мире. В 2019 году она проводилась в Нью-Йорке и собрала исследователей со всего мира, которые работают над решением текущих проблем в области глубокого усвоения знаний:

Неконтролируемое усвоение в малых наборах данных
Усвоение на основе симуляций и переносимость в реальный мир

За последнее десятилетие системы глубокого усвоения добились больших успехов в таких областях, как обнаружение и распознавание объектов, преобразование текста в речь, информационный поиск и другие. В настоящее время исследования сосредоточены на разработке эффективного машинного усвоения знаний, т. е. систем глубокого усвоения, которые могут усваивать знания еще эффективнее, с той же результативностью за меньшее время и с меньшим объемом данных, в таких передовых областях, как персонализированное здравоохранение, стимулированное усвоение знаний роботом (robot reinforcement learning), анализ настроений и другие.

Ключевые тезисы по применению машинного усвоения знаний

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

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

Цитируемые работы

1 http://homes.cs.washington.edu/~pedrod/papers/cacm12.pd

2 http://videolectures.net/deeplearning2016_precup_machine_learning/

3 http://www.aaai.org/ojs/index.php/aimagazine/article/view/2367/2272

4 https://research.facebook.com/blog/facebook-researchers-focus-on-the-most-challenging-machine-learning-questions-at-icml-2016/

5 https://sites.google.com/site/dataefficientml/

6 http://www.cl.uni-heidelberg.de/courses/ws14/deepl/BengioETAL12.pdf

Интервью в Emerj по темам, связанным с машинным усвоением знаний

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

Наука машинного усвоения знаний с д-ром Иошуа Бенжио(один из ведущих мировых экспертов в области МУ)

Д-р Лайл Унгар из UPENN oб использовании машинного усвоения знаний для выявления шаблонов и смысла в социальных медиа

Консультант по ИИ Лорьен Пратт из Кремниевой долины о деловых вариантах использования технологии машинного усвоения знаний

Выводы

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

Подробнее..

Категории: It-стандарты , Искусственный интеллект , Машинное обучение , Machine learning , Учебный процесс в it , Модель , Терминология it , Ии

Маленькими шагами к красивым решениям

16.05.2021 12:20:18 |

Автор: admin

Архитектура ПО это Вселенная. Все очень сложно, но если все правильно, то все невероятно просто. Шаг за шагом познаю что и как. Ищу лучшие практики и шаблоны. В конечном счете, в очередной раз делаю одно и то же заключение:

Изученные правильные практики и шаблоны проектирования лишь вектор, который вдохновляет на красивые и уникальные решения.

Здесь нет примеров хорошей архитектуры, советов как должно быть и как правильно. Я просто хочу зафиксировать мысли, которые надо не забывать воспроизводить при решении очередной задачи.

Снаружи для пользователя, внутри для команды разработки

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

Вдохновляет простое. К простым и красивым решениям не всегда возможно прийти с первого раза. Ошибка тоже результат.

Если система проста и удобна внутри, то она так же проста и удобна снаружи. У пользователей меньше проблем, а значит и у разработчиков тоже.

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

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

Модель

Объектная модель должна быть понятна не только разработчикам, но и пользователям.

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

При реализации объектной модели клиентам рекомендуется ориентироваться на модель сервер-приложения.

Логика

Упрощайте алгоритмы. Делите сложные части на простые. Не переусердствуйте.

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

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

Алгоритм должен легко читаться: в тексте, в любой нотации моделирования, в коде.

Не прячьте за методами в коде неявную логику. Неявные связи в реализации логики ведут к усложнению решения.

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

Нейминг решает

Если назвать бокал стаканом, то назначение "пить" вроде бы не меняется, но что-то все-таки не то.

Имя объекта должно характеризовать его достаточно емко, не вызывать двусмысленности.

Метод должен реализовывать ровно то, о чем говорит его название. Название должно быть таким, чтобы другому разработчику не нужно было залезать внутрь и раскапывать, что еще здесь можно неожиданно встретить в реализации. Лучше, когда название метода описывает результат его работы, но не его реализацию.

Имена объектов и методов в конечном счете становится языком команды разработки, заказчика ПО и даже пользователей.

MVP и прототипы

MVP это быстро и просто, это способ сдвинуться с мертвой точки и начать показывать результат.

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

Рефакторинг

Это придется делать. Это нормально и это важно. Даже для задач, выпущенных в продакшн совсем недавно.

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

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

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

Документация

Документация к системе должна дополнять программный код и хранить знания о причинах принятых архитектурных решений.

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

Выводы

Не усложнять.

Ничего не прятать.

Называть все своими именами.

Не стоять на месте.

Не поддаваться отчаянию, если не получилось.

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

Подробнее..

Категории: Алгоритмы , Анализ и проектирование систем , Проектирование и рефакторинг , Архитектура по , Моделирование , Прототипирование , Архитектура , Модель , Проектирование систем , Mvp , Рефакторинг , Системный анализ , Простота в коде

Краеугольный камень анализа. Часть 1

16.06.2021 02:22:40 |

Автор: admin

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

Я придерживаюсь убеждения, что задача анализа в IT это борьба с неопределённостью, с целью прийти к пониманию, которое выражается в виде модели. Неважно как представлена модель: в виде диаграммы, текста, таблиц, всё равно это модель. Модели бываю разные: модель проблемы, решения, предметной области, модель бизнеса, модель системы, разные модели. И статья целиком состоит из моделей, где будет использоваться простой вымышленный случай, когда потребовалось создание системы. Клиент: Пекарня ООО Три яблока, которая специализируются на производстве выпечки с начинкой из яблок. Заказ: Информационная система поддержки нового продукта пекарни на всех этапах жизненного цикла продукта. Итак, допустим бизнес-аналитики собрали все бизнес-требования, описали все бизнес-процессы. Системные аналитики описали модель данных и процессы на системном уровне. А разработчики реализовали систему по этим описаниям. Тестировщики тоже отработали, критических багов нет. А клиент говорит: Это не то, что нужно! Давай разбираться, где что-то в анализе могло пойти не так. Нас интересует только проблемы анализа.

Нам потребуется следующая иерархия уровней абстракций:

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

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

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

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

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

Еще один способ движение точек зрения навстречу друг другу:
сверху вниз вовлечение пользователей в процесс разработки;
снизу вверх вовлечение разработчиков в обсуждение задач и проблем бизнеса.

А если эти два способа совместить, получим приближение к Agile. В нем эти способы закреплены следующими 2-мя принципами:
1. Частая поставка работающего программного обеспечения;
2. Общение представителей бизнеса с разработчиками должно быть ежедневным на протяжении всего проекта.

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

Чаще ли стали достигать цели работы?
В простых случаях Да, в сложных и больших проектах Agile требует дополнительной организационной работы и методологий, которые уже тяжелы.
Стал ли лучше процесс и результат анализа?
По своей сути Agile это непрерывная корректировка текущего результата с желаемым. Время на комплексный анализ и проработку вариантов ограничено. Основной способ проверки гипотез практика, а не рассуждения.

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

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

Задача анализа это борьба с неопределённостью, с целью прийти к пониманию, которое выражается в виде модели.

А что есть модель? Что описывают модели? Если убрать из рассмотрения парадигмы, то в сухом остатке (исходные, базовые, основные) модели описывают, как субъект выполняет действие над объектом, или субъект взаимодействует с другим субъектом. Дополнительными моделями и элементами моделей могут выступать события, интерфейсы и состояния.

Но основой, вокруг которой всё строится это: субъект, действие, объект. При этом без разницы в каком виде построена модель: BPMN, Use case или UML Диаграмма последовательности. Всё равно, это модель как субъект выполняет действие над объектом, или субъект взаимодействует с другим субъектом.

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

Напомню проблемы, которые нужно решить:

Модели не согласованы внутри себя.
Модели не согласованы между собой.

Для этого нужно выставить первое требование к моделям: Модели на всех уровнях абстракции должны представить собой систему.

Есть еще одна проблема, которую я указал в начале доклада:

Реализация по моделям не соответствует тому, что требуется пользователям и бизнесу.

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

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

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

Если подходить напрямую, то вероятнее всего вы попробуете построить верхеуровневую модель бизнеса. Поискав различные представления, скорее всего найдете Business Model Canvas Александра Остервальдера. И в этом табличном представление обнаружите элементы, которые могут оказать непривычными, если до это вы описывали только операционную деятельность организации. Вы можете попробовать использовать Архитектурные фреймворки, BIZBOK или TOGAF. Но без конкретных примеров они представляют собой теоретические абстракции. По моему мнению, сложность в том, что они созданы не для того, чтобы кого-то научить, они нужны для тех, кто уже знает и понимает, и хочет систематизировать знания.

Ячейка Почему отвечает за назначение остальных ячеек в этой строке, но ее уровень абстракции выше. Это хорошо видно на матрице Захмана первой версии.

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

И с этим выводом формируется Краеугольный камень анализа:
1) Модели на всех уровнях абстракции должны представить собой систему.
2) Назначение элементов системы определяет система.
3) Назначение самой системы находится на вышестоящем уровне абстракций. То есть его определяет вышестоящая система (экосистемы).

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

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

Есть еще технические приемы. Как много вы думали над тем, почему часть User Story после слова чтобы очень тяжело написать? И почему критерии INVEST именно такие?

Шаблон User Story:

Как <субъект>, я хочу/могу <выполнить деятельность или получить объект>, чтобы <зачем или почему>.

INVEST критерии хорошей User Story:

Independent независимая от других историй;
Negotiable обсуждаемая, отражает суть, а не детали;
Valuable ценная для клиентов, бизнеса и стейкхолдеров;
Estimable оцениваемая по сложности и трудозатратам;
Small компактная, может быть сделана командой за одну итерацию;
Testable тестируемая, имеет критерии приемки.

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

В 2020 в руководство по Scrum добавлен понятие Цель продукта, а рамках планирования особое внимание уделяется вопросу Почему для цели спринта. Agile сосредоточен на верхней части пирамиды абстракций. Авторы не глупые люди, они понимают, что это залог успеха.

Для проработки вопроса назначения и ограничений вместе с Agile подходом можно использовать дополнительные методики: Дизайн мышление, Impact mapping и JTBD. Все они хорошие, рекомендую попробовать практиковать. Но тут есть большое НО это не будет работать, если у вас команда неопытных аналитиков. Несмотря на кажущуюся легкость и заявленную опору на простой здравый смысл использовать Agile могут только квалифицированных специалисты с достаточным опытом. Потому что Agile игнорирует уровни абстракций. А в Scrum, по идее, вообще нет аналитиков, есть кроссфункциональная команда, которая работает, не обращая внимание на уровни абстракции.

Примечание

Даже с профессионалами, это возможно только для одной команды из 7-9 человек, как только у вас появляется большой проект и 3-4 команды, то требуется архитектура, модели, проектирование.

Итак, Agile это подход, который делает упор на организационные способы решения задач с опытными профессионалами. Используя различные приемы, указанные ранее, можно получить некоторое представление о назначении и ограничениях, в виде набора стикеров, job stories и mind map.

А есть ли более строгий, аналитический способ понять назначение и ограничения?

Этому будут посвящена вторая часть статьи.

Подробнее..

Категории: Анализ и проектирование систем , Agile , Модель , Метамодель

Краеугольный камень анализа. Часть 2

18.06.2021 00:22:38 |

Автор: admin

Потребуется достроить пирамиду абстракций. За основу я использовал метамодели OMG Business Motivation Model и Open Group ArchiMate.

Нас интересует два слоя: Модель стратегии - она находится над моделью бизнеса и Модель мотивации, которую я разместил на другой грани пирамиды абстракций, она соседствует с Моделью управления. Мотивация и управление это связанные вещи, но управление я рассматривать не буду. Может быть сделаю отдельную статью. Нам не нужно проводить стратегический анализ, это отдельная сложная область, но нас интересуют базовые предметы и результаты этого анализа.

Итак, давайте вспомним про наш условный пример. У нас есть клиент: Пекарня ООО Три яблока, которая специализируются на производстве выпечки с начинкой из яблок. И есть заказ: Информационная система поддержки нового продукта пекарни на всех этапах жизненного цикла продукта. Но чтобы это хорошо сделать, нам нужно понять мотивацию нашего клиента.
Зачем он назвал пекарню Три яблока?

Оказывается, движущей идеей было создание пекарни с самыми вкусными яблочными пирогами. Это его vision. Логично, что у такой пекарни должен быть свой фирменный, самый вкусный яблочный пирог. Уметь делать его - является целью. А какой пирог является самым вкусным? Только свежий. Значит, нужно обеспечить длительное сохранение свежести это задача. Клиент рассчитывает, что реализация этой цели принесет ему ценность в виде дохода, а покупателям качественный товар.

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

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

Далее переходим подходим к воплощению миссии и стратегий. Сама миссия должна реализовываться бизнес-моделью, которую изначально заложил владелец пекарни. Стратегию с самым вкусным пирогом должен будет обеспечить продукт Шарлотка. Операционная деятельность для данного продукта нам разъяснит клиент, особое внимание нужно уделить этапу заморозки и разморозки пирогов. Нам потребуется проанализировать все активы пекарни, которые будут использоваться в данном продукте, то есть персонал, процессы, технологии.

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

Общий вид модели мотивации и стратегии, а также связь с моделью бизнеса. Пробежимся еще раз: Третья колонка слева это: Vision, Цели, Задачи. Элементы слева это ценности, которые представляются по достижению целей. Далее колонка в центре это способы: Миссия для достижения Vision, детализуется в Стратегии для достижения целей, далее стратегии детализируется в тактики для решения задач. Вторая колонка справа это средства реализующие способы. Это Бизнес-модель в интерпретации Остервальдера для выполнения миссии, Продукты, реализующие стратегии и операционная деятельность, реализующая соответствующие тактики. Последняя колонка это нижележащий уровень абстракций с бизнес-процессами, привычными для бизнес-аналитиков.

Метамодель

Теперь посмотрим поближе связь между уровнями абстракций. Важно отметить, что в данном случае результатом процесса является не продукт, а товар. Продукт это совокупность процессов и конфигурация активов для выпуска вида товара. Пример, Биг Мак это продукт сети Макдональдс, а не конкретный бургер.

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

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

Детализируем операционную деятельность на процессы маркетинга, производства и продажи.

Добавим в таком представлении элементы стратегии и мотивации, который мы получили ранее.

Свернем их в один элемент, получим краеугольный камень анализа.

И вот ключевой вопрос:
Можно ли хорошо построить модель операционной деятельности без понимания стратегии и мотивации?

Допустим, вы расписали до винтика весь бизнес только на привычном уровне абстракции в виде процессов на BPMN, а это только желтые элементы на диаграмме.

Допустим, даже вы раньше автоматизировали другую пекарню.
Будет ли это то, что нужно клиенту, если у вас нет понимания стратегии и мотивации?

Примечание

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

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

А еще, наверно, можно развернуть мысль: Если у вас команда профессионалов, то неважно по какой методологии они работают.

Подробнее..

Категории: Анализ и проектирование систем , Модель , Мотивация , Стратегия , Метамодель

Event2Mind для русского языка. Как мы обучили модель читать между строк и понимать намерения собеседника

18.06.2020 18:21:58 |

Автор: admin

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

Уже было предпринято несколько попыток решить данную задачу в той или иной форме. Например, на NLP-progress публикуются последние достижения в области commonsense reasoning. Слабость большинства существующих моделей заключается в том, что в их основе лежит supervised подход, то есть им требуются большие размеченные датасеты для обучения. А в силу специфичности задачи разметка часто бывает весьма нестандартной и достаточно сложной.

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

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

На самом деле, правильнее было бы рассматривать это как целое направление задач, направленных на распознавание намерений и эмоций действующего лица. Единой формулировки у нее нет, и в данном посте мы возьмем за основу вот такой ее вариант, предложенный авторами event2mind: по короткому тексту в свободной форме, содержащему некоторое действие или событие (например, PersonX eats breakfast in the morning), определить намерения субъекта (X wants to satisfy hunger), его эмоции/реакции (X feels satiated, full) и возможные эмоции/реакции других участников события, если таковые присутствуют. Рисунок 1 это наглядно иллюстрирует.

Рисунок 1. Задача Commonsense Reasoning по короткому тексту-событию определить намерения, эмоции/реакции субъекта и эмоции/реакции окружающих

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

Данные, данные и еще раз данные

Итак, нашей задачей было собрать корпус размеченных текстов в свободной форме в формате, пригодном для обучения event2mind. Для простоты дальше мы будем называть такие короткие тексты просто событиями. При этом мы старались максимально расширить common sense reasoning кругозор модели, собрав события на самые разные темы из повседневной жизни.

Часть первая. Crowdsourced corpus

На первом этапе нам предстояло собрать достаточное количество сырых событий для последующей разметки. За основу мы взяли три источника данных:

Короткие посерийные описания сериалов и мыльных опер. Мы вручную отобрали 50 сериалов с сюжетами из повседневной жизни, такие как Друзья, Секс в большом городе, Санта-Барбара, Универ, Кухня и другие. При этом мы старались выбирать сериалы о повседневной жизни с сюжетами на общие темы. Фантастика или профессиональные сериалы нам не подходили, так как они содержат очень много специальной лексики, и события там из своей специфичной области. Вы представляете, что может выучить модель, обученная на Докторе Хаусе или Звездном пути? Еще начнет подозревать у всех волчанку и сыпать рассказами о сражениях с инопланетянами.
Краткие содержания книг. Суммарно нам удалось набрать краткие содержания 1512 книг.
Тексты из SynTagRus, который является частью Русского Национального корпуса и содержит художественные тексты вместе с новостями.

На следующем шаге мы извлекли события из собранных текстов. События для тренировки event2mind можно определить как комбинацию глагольного предиката с входящими в составляющую глагола аргументами. Для поиска подобных паттернов был использован синтаксический парсер UdPipe, с помощью которого мы выделяли в текстах паттерны вида глагол + зависимые слова в синтаксическом дереве, как например на рисунке 2, которые удовлетворяли одному из следующих правил:

nsubj + root + obj
nsubj + root + iobj
nsubj + advmod + root
nsubj + root + case + obl
etc.

Рисунок 2. Синтаксические паттерны, использованные для извлечения событий из текстов

Отобранные события обезличиваются. По аналогии с оригинальным event2mind все действующие лица и именованные сущности были заменены на единообразные PersonX, а также PersonY и PersonZ, если в предложении упоминается более одного действующего лица. Для распознавания именованных сущностей (Named Entity Recognition) и дальнейшей замены мы вновь воспользовались UdPipe: в событиях, которые отвечают паттернам выше мы деперсонилизировали токены, помеченные тегами PROPN или PRONOUN. В завершении мы исключили события, которые не содержат одушевленных субъектов. Например, по этому критерию было отсеяно предложение Идет дождь. В итоге в корпус вошли только события с одушевленными именованными сущностями (person named entities).

После деперсонализации и фильтрации мы воспользовались частотным анализом и расстоянием Левенштейна для отобора наиболее распространенных событий и фильтрации нестандартных примеров, которые встретились лишь единожды. Во-первых, мы взяли все события, которые встретились в первоначальной выборке больше одного раза. Для оставшейся части данных мы посчитали попарные расстояния Левенштейна $inline$ , ), отобрали пары, для которых оно не превосходило 5 и из каждой пары взяли более короткое предложение. При таком методе мы руководствовались следующим соображением: если для пары событий их расстояние Левенштейна мало (в данном случае порог 5), то эти предложения отличаются весьма незначительно, например, в роде глагола или прилагательного. Фактически это вариации одного и того же события. А более короткое предложения из пары мы выбирали потому, что оно скорее будет содержать начальные формы слов (они чаще короче, хотя и не всегда).

После сбора данных события предстояло разметить, выделив в них намерения PersonX, его эмоции/реакции, а также эмоции/реакции PersonY и PersonZ, если таковые присутствуют. Для этого мы создали задание в Яндекс.Толоке. Пример из него вы можете видеть на рисунке 3. Для каждого события мы спрашивали разметчиков:

содержит ли оно осмысленное событие;
можно ли по тексту события понять намерения действующего лица;
можно ли по событию понять эмоции/реакцию действующего лица;
может ли это событие вызвать реакцию окружающий.

Рисунок 3. Пример задания из Яндекс.Толоки

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

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

В итоге нам удалось собрать 6756 событий на различные повседневные темы.

Часть 2. Translated English corpus

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

Дело в том, что разметка подобного датасета трудоемкое дело, требующее большого количества ресурсов, денег и средств. У нас просто не было возможности разметить корпус, по размерам сопоставимый с английским, который состоит из 46 тысяч примеров. Поскольку собранный на русском датасет оказался меньшего размера, мы решили оценить, хватит ли такого объема данных для обучения. Для этого мы обучили английскую модель на частях оригинального корпуса и измерили, как меняется качество в зависимости от размера обучающего датасета. Результаты приведены в таблице. Качество для намерений (intent) и эмоций/реакций (react) оценивалось, по аналогии с оригинальной статьей, по метрике recall@10 на валидации. recall@10 отражает долю случаев, когда истинный ответ golden standard попадает в топ-10 предсказаний модели. Метрика меняется от 0 до 1, чем больше, тем лучше.

Таблица 1. Зависимость качества английской модели от размера корпуса для обучения

Сразу можно сказать, что 5000 примеров недостаточно для полноценного обучения модели. Однако уже при 30000 примеров, loss и recall практически не отличаются от результатов на полном объеме данных. Получается, что размеченных нами 7000 примеров не хватает для обучения модели и необходимо каким-то способом увеличить размер обучающей выборки.

Для этого мы подготовили дополнительный корпус, полученный из английского с помощью автоматического перевода Google Переводчиком. Как уже отмечалось выше, при автоматическом переводе всего корпуса некоторые переводы оказывались некорректными или полностью теряли смысл. Поэтому мы отобрали ту часть английских данных, которая переводилась наиболее адекватно. Изначально английский корпус собран из нескольких источников: ROC Story training set, the GoogleSyntactic N-grams, the Spinn3r corpus и idioms. При этом предложения из некоторых источников оказались проще для перевода, чем из других. Например, адекватный перевод идиом без ручной правки оказался не под силу компьютеру. Поэтому мы взяли только примеры из ROC-story. По результатам оригинальной статьи (см. таблицу 2), у этого источника коэффициент согласованности аннотаторов (Cohen's kappa coefficient), равный 0.57. А это, скорее всего, свидетельствует о том, что события оттуда проще для понимания и разметки, а значит меньше подвержены ошибкам при переводе.

Таблица 2 Данные и Cohen's kappa coefficient для разных источников в английском корпусе

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

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

В итоге нам удалось набрать 23409 переведенных событий, а объем объединенного корпуса с учетом размеченной русской части составил 30165. Этого, как мы выяснили во время экспериментов, должно было хватить для обучения русской модели.

А теперь к экспериментам!

Итак, данные собраны, пора переходить к обучению модели и экспериментам. Модель event2mind представляет собой нейросетевую архитектуру вида encoder-decoder с одним энкодером и тремя декодарами для каждого вида предсказаний (см. рисунок 4): намерение субъекта, его эмоции/реакции и эмоции/реакции других участников события, если таковые имеются (subjects intent, subjectss reaction и others events participants reactions). Исходные предложения изначально векторизуются с помощью одного из методов векторных представлений слов (например, word2vec или fasttext) и кодируются с помощью энкодера в вектор $h^E\in \mathbb{R}^H$ . А затем с помощью трех RNN декодеров генерируются предсказания. Благодаря этому модель может генерировать ответы даже для намерений и реакций, которые она до этого не видела.

Рисунок 4. Архитектура модели event2mind

Для экспериментов мы использовали объединенный корпус для русского языка, размеченную и переведенную части. А чтобы сделать распределение русских и переведенных примеров более равномерным, мы дополнительно перемешали данные. Отметим, что мы также попробовали обучить модель только на размеченных данных, но из-за маленького объема датасета, она показала очень плохие результаты. Мы протестировали различные слои в энкодере LSTM и GRU, а также попробовали различные векторные представления fasttext и word2vec с RusVectores. Результаты приведены в таблице 3, результаты по intentам и reactам, как и ранее считались по метрике recall@10.

Таблица 3. результаты моделей для русского языка, intent и react оценивались по recall@10

Итак, какие выводы можно сделать из результатов экспериментов? Во-первых, word2vec embeddings оказались немного лучше, чем fasttext. При этом fasttext embeddings, обученные на ruscorpora показали себя лучше обученных на araneum. Во-вторых, можно отметить, что при использовании word2vec, GRU в энкодере оказывается лучше LSTM. И наконец, лучшая модель (areneum word2vec + GRU) практически повторяет результаты для английского языка.

И напоследок посмотрим на реальные примеры!

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

Вместо заключения

Итак, мы создали русскоязычный корпус для обучения модели event2mind. Помимо этого, мы провели эксперименты, которые показали, что архитектура event2mind работает для русского языка, который по своей природе грамматически сложнее английского. Несмотря на сложность русского языка, удалось достичь сравнимого с английским качества. Лучшая модель и данные выложены в репозитории.

Такой большой проект стал возможен, только благодаря совместным усилиям нашей команды. В адаптации event2mind для русского языка также принимали участие alenusch и onetwotrickster.

Подробнее..

	Русский
	English

Модель

Модель натурального числа. Часть I

Теоремы существования и теоремы перечисления. Модели

Предварительные результаты, необходимые для разработки модели числа

Модель отдельного нечетного числа

Обоснование выбора списковой многострочной модели (СММ) числа

Алгоритм решения ЗФБЧ с учетом области ТКВК

Алгоритм

Факторизация и эллиптическая кривая. Часть III

Предварительные сведения из высшей алгебры

Элементы теории эллиптической кривой

Построение группы точек ЭК

Суммирование точек ЭК групповая операция

Порядок группы и элемента группы

Метод факторизации числа, использующий эллиптическую кривую

Получение мультипликативного обратного элемента в кольце вычетов

Простая криптографическая система на эллиптических кривых

Заключение

Список использованных источников

Перевод Что такое machine learning?

Что такое машинное усвоение?

Как мы пришли к нашему определению

Базовые концепции машинного усвоения

Визуализации моделей машинного усвоения знаний

Как мы обеспечиваем машины способностью усваивать знания

Обзор трудностей и пределов машинного усвоения

Глубокое усвоение и новейшие разработки в нейронных сетях

Ключевые тезисы по применению машинного усвоения знаний

Цитируемые работы

Интервью в Emerj по темам, связанным с машинным усвоением знаний

Выводы

Маленькими шагами к красивым решениям

Снаружи для пользователя, внутри для команды разработки

Модель

Логика

Нейминг решает

MVP и прототипы

Рефакторинг

Документация

Выводы

Краеугольный камень анализа. Часть 1

Краеугольный камень анализа. Часть 2

Event2Mind для русского языка. Как мы обучили модель читать между строк и понимать намерения собеседника

Данные, данные и еще раз данные

Часть первая. Crowdsourced corpus

Часть 2. Translated English corpus

А теперь к экспериментам!

И напоследок посмотрим на реальные примеры!

Вместо заключения

Категории

Последние комментарии