Как стать автором
Обновить

Комментарии 29

Все очень понятно, и написано доступным языком. Спасибо.
С таким-то ником может и понятно. А остальным как быть? =(
Пожалуйста! Рад, что вам понравилась статья. Видимо не зря старался :)
НЛО прилетело и опубликовало эту надпись здесь
Благодарю, замечательный и отлично структурированный материал. Осталось только его понять. Когда-нибудь.
Что такое порядок группы для кривой? (из фразы) «Две кривые над одним конечным полем изогенны тогда и только тогда, когда порядки их групп равны.».
Порядок группы — это число ее элементов. Порядок группы точек кривой — число элементов группы точек кривой.
Но можно сказать еще проще: это число всех точек на конкретной кривой + одна точка на бесконечности. Вы можете посмотреть мою предыдущую статью
Что такое «группа точек кривой» и чем она отличается от «все точки кривой»? Если «группа точек» — это все точки, то можем ли мы говорить, что группа точек на синусоиде и на параболе сравнимая — и там и там бесконечность?

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

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


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


Без ноля те же самые множества образуют группу по умножению.


Более подробно об этом можно почитать в Википедии

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

Теперь мы говорим про порядок группы. У нас есть две непрерывные гладкие функции определённые на всём множестве вещественных чисел. Будет ли порядок группы точек первой кривой отличаться от порядка группы второй кривой?

А если одна кривая определена на отрезке вещественных чисел? Например, равны ли порядки для групп точек кривой x2+y2=1 и кривой y=sin(x)?

Нет, только умножение. Если операций две — то это уже поле (или кольцо, если вторая операция необратима).


Обратите внимание также на формулировку теоремы Tate:


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

Кривая над конечным полем никак не может содержать бесконечное количество точек :-)

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

Ага, всё сложнее. У нас рядом с «группой» появляется слово «поле». Группа — это когда определена операция умножения, поле — когда определены умножение и сложение.

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

Пытаюсь развернуть определение «теоремы Tate»: Кривая — конечное множество точек на поле, описываемое какой-то функцией. Для поля определены операции умножения и сложения. Для точек кривой как минимум определено умножение и деление.

Мы говорим, что две такие кривые изогенны, тогда и только тогда, когда содержат одинаковое количество точек, так?

Раскрывая определение изогенности:

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

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

Переводя на компьютерный язык:

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

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

Допустим, у меня есть поле [1,2,3,4,5,6]. На этом поле у меня определены операции сложения (для некоторых элементов), умножения (аналогично), деления (аналогично).

1) Является ли 1-6 полем? Мне кажется, что нет. Если таки да, то:
Допустим, у меня есть кривая [1,2,3] и и [4,5,6]. Есть ли такое отображение, которое будет давать изогенное отображение? Как оно выглядит?

Если я где-то сделал фатальную ошибку, объясните мне её, пожалуйста. И если это возможно, проиллюстрируйте на конечном множестве чисел как оно должно быть. Спасибо.
Я его не забыл, я про него не знал. Видимо, поле должно обладать какими-то специальными свойствами.

Интересно, если у меня есть беззнаковая арифметика по модулю 256, то это будет полем?

Мне как айтишнику будет очень легко смотреть на математические операции над байтом.
Нет, не будет. По модулю 257 будет.

Беззнаковая арифметика по модулю 256 — это не поле, а кольцо. Разница — в обратимости умножения. Например, нельзя разделить 1 на 2 нацело.


Тем не менее, с 256 элементами поле построить можно — это будет поле двоичных полиномов, порожденное полиномом 8й степени. Именно в таком поле производит вычисления, к примеру, алгоритм CRC-8 (вообще, все семейство алгоритмов CRC основано на полях двоичных полиномов, порожденных полиномами соответствующих степеней). Роль сложения в таких полях играет операция XOR (побитовое исключающее "или").

Если вам интересны конечные поля и вам нужны примеры, чтобы разобраться, то рекомендую установить open-source пакет SAGE — он много чего умеет. А кроме того, я бы почитал классику: «Конечные поля» Лиддла и Нидеррайтера или еще лучше «Алгебра» Глухова
Допустим, что у вас есть конечное поле из p^n элементов.(все конечные поля имеют такой порядок)
Вы не можете взять и поделить его на две одинаковые части, поскольку каждая из них по отдельности не будет полем.
А можно увидеть пример двух кривых, которые построены на базе какого-то поля, причём так, чтобы размерность кривой (число точек) было меньше, чем число элементов поля?
Да, конечно :)

Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 2 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 3 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 11 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 14 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + x + 2 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + x + 5 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + x + 6 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + x + 7 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + x + 10 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + x + 11 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 2*x + 6 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 2*x + 8 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 2*x + 10 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 2*x + 12 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 2*x + 14 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 2*x + 15 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 2*x + 17 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 2*x + 18 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 3*x + 6 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 3*x + 8 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 3*x + 10 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 3*x + 12 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 3*x + 14 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 3*x + 15 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 3*x + 17 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 3*x + 18 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 4*x + 1 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 4*x + 3 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 4*x + 7 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 4*x + 9 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 4*x + 15 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 4*x + 17 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 5*x + 1 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 5*x + 4 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 5*x + 11 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 5*x + 13 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 5*x + 14 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 5*x + 16 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 6*x + 1 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 6*x + 3 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 6*x + 7 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 6*x + 9 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 6*x + 15 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 6*x + 17 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 7*x + 2 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 7*x + 5 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 7*x + 6 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 7*x + 7 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 7*x + 10 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 7*x + 11 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 8*x + 2 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 8*x + 8 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 8*x + 9 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 8*x + 12 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 8*x + 13 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 8*x + 15 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 8*x + 16 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 8*x + 18 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 9*x + 1 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 9*x + 3 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 9*x + 7 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 9*x + 9 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 9*x + 15 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 9*x + 17 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 10*x + 3 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 10*x + 4 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 10*x + 5 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 10*x + 8 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 10*x + 10 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 10*x + 12 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 10*x + 13 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 10*x + 18 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 11*x + 2 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 11*x + 5 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 11*x + 6 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 11*x + 7 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 11*x + 10 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 11*x + 11 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 12*x + 2 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 12*x + 8 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 12*x + 9 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 12*x + 12 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 12*x + 13 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 12*x + 15 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 12*x + 16 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 12*x + 18 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 13*x + 3 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 13*x + 4 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 13*x + 5 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 13*x + 8 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 13*x + 10 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 13*x + 12 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 13*x + 13 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 13*x + 18 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 14*x + 6 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 14*x + 8 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 14*x + 10 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 14*x + 12 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 14*x + 14 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 14*x + 15 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 14*x + 17 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 14*x + 18 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 15*x + 3 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 15*x + 4 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 15*x + 5 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 15*x + 8 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 15*x + 10 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 15*x + 12 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 15*x + 13 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 15*x + 18 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 16*x + 1 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 16*x + 4 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 16*x + 11 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 16*x + 13 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 16*x + 14 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 16*x + 16 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 17*x + 1 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 17*x + 4 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 17*x + 11 over Finite Field of size 19
has order
18
Elliptic Curve defined by y^2 = x^3 + 17*x + 13 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 17*x + 14 over Finite Field of size 19
has order
12
Elliptic Curve defined by y^2 = x^3 + 17*x + 16 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 18*x + 2 over Finite Field of size 19
has order
14
Elliptic Curve defined by y^2 = x^3 + 18*x + 8 over Finite Field of size 19
has order
13
Elliptic Curve defined by y^2 = x^3 + 18*x + 9 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 18*x + 12 over Finite Field of size 19
has order
15
Elliptic Curve defined by y^2 = x^3 + 18*x + 13 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 18*x + 15 over Finite Field of size 19
has order
17
Elliptic Curve defined by y^2 = x^3 + 18*x + 16 over Finite Field of size 19
has order
16
Elliptic Curve defined by y^2 = x^3 + 18*x + 18 over Finite Field of size 19
has order
18
где p — это простое число. Но даже если p = 2 и число элементов получится 2^n, то все равно вам придется взять в одну из двух частей 0 или 1 и они уже не будут полями.

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

«Все точки кривой» — это множество всех точек кривой. Понятие «группа точек кривой» предполагает наличие операции между любыми двумя точками, результат которой — точка той же самой кривой. Эта операция должна удовлетворять определенным правилам, которые одинаковы для всех групп (мультипликативная группа, которая используется в классическом Диффи-Хеллмане также этим правилам удовлетворяет (иначе она называлась бы не группа)). Вот эти правила: 1. ассоциативность (a*b)*c = a*(b*c) 2. в группе всегда есть нейтральный элемент e такой, что a*e = e*a = a (для любого a). 3. для любого элемента x в группе существует обратный элемент y: x*y = y*x = e
При написании статьи всегда возникает вопрос: насколько далеко стоит уходить в описание элементарных понятий. Ведь можно сделать статью либо недоступной к пониманию, либо просто скучной. Ее главная цель — вызвать интерес к предмету, даже если что-то не совсем понятно. В любом случае большое спасибо за сигнал — я добавлю определений в первую статью.
Я не могу говорить за всех, но мне бы хотелось иметь возможность понять написанное с скудным багажом из матанализа и хорошим представлением об обычных типах данных.

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