|
▲ Выше
ДП Фурье в конечных полях ►
|
|
Арифметики в конечных числовых полях |
|
∀
an, p, (a,p)=1
n=1,2,...
∃ λ , p | aλ-1 ⇒ λ | p-1 |
Понятие простого числа является основным в теории чисел. |
|
a=3, p=13,
λ=3,
aλ=33=27
13 | 33-1 ⇒ 3 | 13-1 |
Сперва вы объясняете то, что собираетесь сказать, потом говорите, потом объясняете то, что вы сказали
Б.Саймон
Стюардесса: "Наш самолёт приземляется в порту Баден-Баден."Голос из салона: "Ну, ты чо, блин, два раза повторять? Тут же не лохи сидят."
Анекдот, XXI Р.Х.
|
|
a=3, p=17,
λ=16,
aλ=316=43046721
17 | 316-1 ⇒ 16 | 17-1 |
Чрезмерная формализация — стиль, вдохновлённый несомненно дьяволом.
Дж.Литлвуд
|
|
a=2, p=17,
λ=8,
aλ=28=256
17 | 28-1 ⇒ 8 | 17-1 |
Математика — царица наук, а арифметика — царица математики.
К.Ф.Гаусс
|
 Делимость целых чисел
Сравнения и ВЫЧЕТы
Группы, кольца, поля чисел
Изоморфизм
Числа Ферма
Первообразные КОРНИ
(A−1)-арифметика ВЫЧЕТов по модулю чисел Ферма
|
Я всматриваюсь в вас, о, числа,
и вы мне видитесь одетыми в звери — в их шкурах —
рукой опирающимися на вырванные дубы.
Вы даруете единство между змееобразным
движением
хребта вселенной и пляской коромысла,
вы позволяете понимать века, как быстрого
хохота зубы.
Мои сейчас вещеобразно разверзлися зеницы
узнать, что будет Я, когда делимое его — единица.
Велемир Хлебников
"Числа", 1912.
|
Делимость целых чисел.
При делении целых чисел a и M получаются частное div и остаток rest такие, что a=M·div+rest и 0≤rest≤M−1. Остаток rest называют ВЫЧЕТом по модулю M.
Например, при M=3
и при M=5
Если rest=0, то говорят, что M делит a нацело (или M кратно a) и пишут
M | a ,
а числа div и M называют делителями a.
Очевидно, что 1|a и a|a.
Если a не имеет других делителей, кроме 1 и a,
то a — простое число (или неделимое), иначе a называют
составным числом. Самый большой положительный делитель
d двух чисел a и M называется
Наибольшим Общим Делителем
(НбОД) и обозначается
d=(a,M).
Если НбОД (a,M)=1, то a и M не имеют общих делителей, кроме 1, и называются взаимно простыми (или неделимыми относительно друг друга).
Например,
Любое составное число a можно представить в виде произведения степеней простых чисел p1, p2, ...
a
=
p1(n1)·p2(n2) ...
=
∏
pk(nk) ,
k=1,2,..
Основная теорема арифметики, доказанная Гауссом, утверждает, что это
представление единственно.
Например,
|
Что остаётся от сказки потом,
после того, как её рассказали?
Владимир Высоцкий
"Песня Кэрролла" из музыкальной сказки
"Алиса в стране чудес" по Льюису Кэрроллу.
|
|
Сравнения и ВЫЧЕТы.
Каждому ВЫЧЕТу rest=0..M−1 соответствует много целых чисел a,b,... Говорят, что числа с одинаковым ВЫЧЕТом сравнимы по модулю M и обозначают так:
a≡b mod M или
a≡b (mod M) или (a≡b) modulo M (введено Гауссом) или a≡b ( M ), т.е. без mod (введено в
) или ((a≡b)) M или ((a≡b))M или a≡( b ) M (это современные варианты без mod) или 〈 a≡b 〉M или 〈 a 〉M = 〈 b 〉M, т.е. без mod и знак равно (сравнимо) вместо знака тождества (введено Рейдером в
)
Например, при M=3
а при M=5
Числа a, которые сравнимы по модулю M, образуют класс своего ВЫЧЕТа rest и определяются как a=rest+div·M. Числа a тоже называют ВЫЧЕТами по модулю M. Неотрицательные ВЫЧЕТы a=rest (при div=0), принимающие значения из интервала [0..M−1], образуют
ВЫЧЕТы a , принимающие значения из интервала
[ div·M+0...(div·M + M−1)], где div=1,2,..
образуют
ВЫЧЕТы a , принимающие значения из интервала
[−(M−1)/2) ... (M−1)/2] , при нечётном M
или из интервала
[-M/2 ... M/2-1] , при чётном M ,
образуют
Например, при M=5 классы наименьших ВЫЧЕТов по модулю
5 образуют ВЫЧЕТы:
а классы НЕ наименьших ВЫЧЕТов по модулю 5 образуют ВЫЧЕТы:
Класс ВЫЧЕТов, элементы которого взаимно просты с модулем M называют приведеным. Функция Эйлера φ(M) определяет сколько ВЫЧЕТов из ПСНВ+ по модулю M взаимно просты с M. При простом M=p имеем
φ(p)
= p−1 .
|
А для низкой жизни были числа,
Как домашний, подъяремный скот,
Потому что все оттенки смысла
Умное число передаёт.
Николай Гумилёв
|
|
Группы, кольца, поля чисел.
ПСНВ+ mod M при простом M=p образует
конечное поле порядка M или
простое поле Галуа
GF(p)
в отличии от
расширенного поля Галуа
GF(pr)
при
M=pr,
а при составном M — коммутативное
или
абелево кольцо
ZM
(или
Z/(M)
).
Числовое поле формально определяется системой аксиом.
Упрощенно говоря,
абелевой группой
является множество, в котором можно "складывать" и "вычитать", в
кольце
можно ещё и "умножать", а в
поле, кроме этого, можно ещё и "делить".
Например, абелевыми будут:
|
Многие вещи нам не понятны не потому,
что наши понятия слабы;
но потому, что сии вещи
не входят в круг наших понятий.
Козьма Прутков
"Мысли и афоризмы",66.
|
|
Изоморфизм.
Две похожие по структуре и свойствам группы H и G называют изоморфными, обозначается H~G, если найдется отображение ψ:H→G такое, что
ψ(h1
op(H)
h2)
=
g1
op(G)
g2,
или иначе (формально) H~G, если
∃
ψ
такое, что
ψ(h1
op(H)
h2)
=
ψ(h1)
op(G)
ψ(h2)
=
g1
op(G)
g2,
т.е.
ψ(h1)=g1
и
ψ(h2)=g2.
Например, логарифм переводит умножение положительных вещественных чисел в сложение всех вещественных чисел, т.е. мультипликативную группу
< (·),R+ >
положительных вещественных чисел
R+
переводит в аддитивную группу
< (+),R >
поля R всех вещественных чисел:
log: < (·),R+ >
→
< (+),R >
log(h1·h2) = log(h1) + log(h2). Точно также, в поле C комплексных чисел ДПФ (Дискретное Преобразования Фурье) результата циклической свёртка двух числовых последовательностей
y[n]=x[n]*h[n]
равно произведению спектров ДПФ этих последовательностей
ДПФ( y[n] )
=
ДПФ( x[n]*h[n] )
=
ДПФ( x[n] ) · ДПФ( h[n] )
или формально
ДПФ: < (*),C >
→
< (·),C > .
|
Когда мерцает в дыме сёл
сверкнувший синим коромысел,
проходит Та, как новый вымысел,
и бросит ум на берег чисел.
Воскликнул жрец: "О, дети, дети!"-
на речь афинского посла.
И ум, и мир, как плащ, одеты
на плечах строгого числа.
И если смертный морщит лоб
над вино-пенным уравнением,
узнайте: делает он, чтоб
стать роста на небо растением.
Прочь застенок! Глаз не хмуря,
огляните чисел лом.
Ведь уже трепещет буря,
полупоймана числом.
Напишу в чернилах: верь!
Близок день, что всех возвысил!
И грядёт бесшумно зверь
с парой белых нежных чисел!
Но, услышав нежный гомон
этих уст и этих дней,
он падёт, как будто сломан,
на утёсы меж камней.
Велемир Хлебников
"Зверь + число", 1915
|
|
Числа Ферма.
Пусть порядок M поля Галуа GF(M) равен числу Ферма, т.е.
M = Fn ,
Fn = 2b+1, где b=2n и n = 0,1,2,3,4,5,6,7, ... Числа Ферма F0=3 , F1=5 , F2=17 , F3=257 , F4=65537 — простые, а числа Ферма F5 , F6 , F7 , ... — составные.
ПСНВ+ поля
ПСНВ+ кольца
Составные числа Ферма имеют вид (Лукас)
Fn
=
U1·U2·... ,
где сомножители Uk — простые (?) и имеют вид
Uk
=
Ck·2(n+2)+1.
Например,
|
Смотри в корень
Козьма Прутков
"Мысли и афоризмы",5.
|
|
Первообразные КОРНИ.
Пусть root — КОРЕНЬ T-й степени из 1 по модулю Fn , т.е. формально это корень (решение)
root ≡ T√1 mod Fn
уравнения
〈
rootT
〉Fn
=
1 .
Тогда ВЫЧЕТы по модулю
Fn
k-ых степеней root , т.е.
〈
rootk
〉Fn ,
при k=0,1,...,T−1
образуют циклическую группу порядка T
(т.е. группу из T элементов).
В случае простого Fn по теореме Эйлера имеем
φ(Fn)
=
Fn−1
=
Tmax
=
O(Fn)
.
При T=Tmax=(Fn−1)
КОРЕНЬ root называется
примитивным (primitive) или
первообразным (порождающим, образующим) КОРНЕМ по модулю
Fn , а при
T<Tmax=(Fn−1) КОРЕНЬ root называется просто КОРНЕМ
порядка T
(или
степени
T) по модулю Fn
или иначе формально
〈
rootT
〉Fn
= 1 ,
где T≠0 и T принадлежит ПСНВ+ mod
Fn ,
и все степени
〈
rootk
〉Fn
≠
0 ,
при k=0,1,...,T−1
(T≤Fn−1)
принимают неповторяющиеся значения из интервала [1,...,(Fn−1)] ,
причём T должно делить
Tmax
=
(Fn−1)
=
2b
, т.е.
T | (Fn−1) .
Например, для n=1 имеем b=2n=21=2 и простое число Ферма
F1 = 2b+1 = 22+1 = 5
имеет такие КОРНИ:
〈
34
〉5
=1, где 3 — примитивный КОРЕНЬ порядка 2b=F1−1=4=Tmax= O(F1),
〈 24 〉5 =1, где 2 — КОРЕНЬ порядка 2b=2n+1 = 4 = Tmax (примитивный) , 〈 42 〉5 =1, где 4 - КОРЕНЬ порядка 2 < Tmax . При n > 1 , т.е. для чисел Ферма F2=17 , F3=257 , F4=65537 и т.д., не примитивные КОРНИ rootm вида 2p, где p=2m, m=1,2,...,n имеют такой порядок
Trootm
=
T2 /p
=
2b/2m
=
2n+1-m ,
т.к.
p
должно делить порядок
T2=2b
КОРНЯ из 1
root=2
.
Это следует из того, что если root имеет порядок N, т.е. rootN≡1 mod Fn , то другие КОРНИ rootm=rootp будут иметь порядок N/p, если p|N. Нас интересует случай КОРНЯ root=2, порядок которого по модулю чисел Ферма равен N=T2=2b=2n+1. Тогда порядок КОРНЯ rootm должен иметь вид
Trootm
=
2k
,
потому, что
Trootm=2k
|
2b
=
(Fn−1)=Tmax=O(Fn)
.
Это возможно при
p=2m
и поэтому КОРЕНЬ
rootm
порядка
N/p
найдётся как
rootm
=
2p
=
22m ,
m=1,2,...,n ,
а
Trootm
=
2k
=
T2 /p
=
2b/2m
=
2n+1-m ,
m=1,2,...,n .
Например, для n=2 имеем b=2n=22=4 и простое число Ферма
F2 = 2b+1 = 24+1 = 17
имеет такие КОРНИ:
〈
316
〉17
=1, где 3 — примитивный КОРЕНЬ порядка 2b=F2−1=16=Tmax ,
〈 √216 〉17 =1, где √2 — КОРЕНЬ порядка 4b=2n+2=16=Tmax (примитивный), 〈 28 〉17 =1, где 2 — КОРЕНЬ порядка 2b=2n+1 = 8 = Troot0 = T2 ( m=0 ), 〈 44 〉17 =1, где 4 — КОРЕНЬ порядка 4 = Troot1 = T4 ( m=1 ) , 〈 162 〉17 =1, где 16 — КОРЕНЬ порядка 2 = Troot2 = T16 ( m=2 ) . Для n=3 имеем b=2n=23=8 и простое число Ферма
F3 = 2b+1 = 28+1 = 257
имеет такие КОРНИ:
〈
3256
〉257
=1, где 3 — примитивный КОРЕНЬ порядка 2b=F3−1=256=Tmax ,
〈 √232 〉257 =1, где √2 — КОРЕНЬ порядка 4b=2n+2=32 < Tmax , 〈 216 〉257 =1, где 2 — КОРЕНЬ порядка 2b=2n+1=16 = Troot0= T2 ( m=0 ), 〈 48 〉257 =1, где 4 — КОРЕНЬ порядка 8 = Troot1 = T4 ( m=1 ), 〈 164 〉257 =1, где 16 — КОРЕНЬ порядка 4 = Troot2 = T16 ( m=2 ), 〈 2562 〉257 =1, где 256 — КОРЕНЬ порядка 2 = Troot3 = T256 ( m=3 ) . Для n=4 имеем b=2n=24=16 и простое число Ферма
F4 = 2b+1 = 216+1 = 65536+1 = 65537
имеет такие КОРНИ:
〈
365536
〉65537
=1, где 3 — примитивный КОРЕНЬ порядка 2b=F4−1=Tmax ,
〈 √264 〉65537 =1, где √2 — КОРЕНЬ порядка 4b=2n+2=64 < Tmax , 〈 232 〉65537 =1, где 2 — КОРЕНЬ порядка 2b=2n+1=32=Troot0=T2 (m=0), 〈 416 〉65537 =1, где 4 — КОРЕНЬ порядка 16 = Troot1 = T4 (m=1), 〈 168 〉65537 =1, где 16 — КОРЕНЬ порядка 8 = Troot2 = T16 (m=2), 〈 2564 〉65537 =1, где 256 — КОРЕНЬ порядка 4 = Troot3 = T256 (m=3), 〈 655362 〉65537 =1, где 65536 — КОРЕНЬ порядка 2 = Troot4= T65536 (m=4). Заметим, что для простых чисел Ферма F3 и F4 (т.е. n > 2) кроме целого 3 существуют ещё 2b−1 других примитивных КОРНЕЙ, которые также имеют максимальный порядок
Tmax
=
2b
=
Fn−1
=
O(Fn)
и могут быть образованы возведением root=3 в нечётную степень.
Для составных чисел Ферма
Fn
при
n=5,6,7,...
примитивных (primitive)
или
первообразных
КОРНЕЙ по модулю
Fn
просто не может быть, а
максимальный объём преобразования O(Fn)
или
максимальный порядок КОРНЯ root равен
Tmax
=
2n+2
=
4b
=
O(Fn)
.
У прочих не примитивных КОРНЕЙ root
порядки
T≤Tmax
должны также делить
Tmax , т.е.
T | Tmax .
Например, для n=5 имеем b=2n=25=32 и составное число Ферма
F5 = 2b+1 = 232+1
имеет такие КОРНИ (примитивных у составного F5 нет ):
〈
√2128
〉F5
=1, где √2 — КОРЕНЬ порядка 4b=2n+2=128=
Tmax ,
〈 264 〉F5 =1, где 2 — КОРЕНЬ порядка 2b=2n+1= 64= Troot0= T2 (m=0) . Для n=6 имеем b=2n=26=64 и составное число Ферма
F6 = 2b+1 = 264+1
имеет такие КОРНИ (примитивных у составного F6 нет ):
〈
√2256
〉F6
=1, где √2 — КОРЕНЬ порядка 4b=2n+2=256=
Tmax ,
〈 2128 〉F6 =1, где 2 — КОРЕНЬ порядка 2b=2n+1=128= Troot0= T2 (m=0) . Для n=7 имеем b=2n=27=128 и составное число Ферма
F7 = 2b+1 = 2128+1
имеет такие КОРНИ (примитивных у составного F7 нет ):
〈
√2512
〉F7
=1, где √2 — КОРЕНЬ порядка 4b=2n+2=512=
Tmax ,
〈 2256 〉F7 =1, где 2 — КОРЕНЬ порядка 2b=2n+1=256= Troot0= T2 (m=0) .
Таблица степеней КОРНЕЙ 〈 rootk 〉17 , k=0..17−1, образующих циклические группы ВЫЧЕТов порядка T , т.е. порядка КОРНЕЙ root mod F2=17 .
|
||||||||||||||||||||||||||||
Где начало того конца, которым
оканчивается начало?
Козьма Прутков
"Мысли и афоризмы",78.
|
|
(A-1)-арифметика ВЫЧЕТов по модулю чисел Ферма
Для вычислений по модулю чисел Ферма была предложена схема предварительного
кодирования чисел из обычной A-арифметики
в (A-1)- арифметику, т.е. с уменьшением битового образа обычного числа на 1.
Рассмотрим таблицу соответствия между естественной формой представления
чисел в обычной A-арифметике и формой представления чисел в (A-1)-арифметике,
у которых совпадает
битовое представление для случая b=2n=22=4, т.е.
в арифметике операций по модулю числа Ферма F2=17.
Числа с одинаковым битовым представлением в (A-1)-арифметике на 1 больше, чем числа в обычной A-арифметике (т.е. с таким же точно битовым представлением), кроме 0, которому соответствует максимальное число в обычной A-арифметике.
Например, сравним соответствующие числа в двух арифметиках:
A и (A-1) по модулю чисел Ферма
F1
и
F2 ,
у которых битовое представление одинаково:
mod F1:
0,1, 2, 3, 4 — в A-арифметике
1,2, 3, 4, 0 — в (A-1)-арифметике ( ПСНВ+ ) 1,2,-2,-1, 0 — в (A-1)-арифметике ( ПСАНВ± ) mod F2 :
0,1,2,3, 4, 5, 6, 7, 8 — в A-арифметике
1,2,3,4, 5, 6, 7, 8, 0 — в (A-1)-арифметике ( ПСНВ+ ) 1,2,3,4,-4,-3,-2,-1, 0 — в (A-1)-арифметике ( ПСАНВ± ) В отличии от обычной A-арифметики ВЫЧЕТов по модулю Fn (т.е. только для положительных целых!), в (A-1)-арифметике ВЫЧЕТов по модулю Fn вторую (старшую) половину чисел можно рассматривать как отрицательные целые в ПСАНВ±, потому что их битовое представление является уже НЕ дополнительным кодом (как в обычной A-арифметике), а просто инверсией (без +1) значащих (здесь 4-х младших) битов в соответствующих им целых в ПСНВ+ (т.е. равных им по абсолютной величине). При этом положительные целые в (A-1)-арифметике увеличены на 1 по сравнению с обычной A-арифметикой. Таким образом, (A-1)-арифметика ВЫЧЕТов по модулю чисел Ферма Fn не сложнее обычной арифметики, например ВЫЧЕТов по модулю чисел Мерсена Mp=2p−1 , (которую называют комплементарной до 1 или арифметикой в дополнительном коде, в котором отрицательные целые образуются из положительных инверсией битов и прибавлением 1, а при преобразовании, например из 8 бит в 16 бит, дополняются единицами в старших битах) и может быть реализована на стандартных компьютерах с длиной регистров b=2n бит.
|
(*
Примеры операций в (А-1)-арифметике по модулю числа Fermat2 = 17
------------------------------------------------------------------------------
СЛОЖЕНИЕ
< x+y >F2 5-ти битовых ВЫЧЕТов mod Fermat2
Сумма < g+h >F2 в (A-1)-арифметике равна
< g+h-1 >F2 =< <(g-1) + (h-1)>F2 + 1 >F2
обозначим через g1=g-1, h1=h-1, тогда в (A-1)-арифметике
< g+h-1 >F2 =< < g1 + h1 >F2 + 1 >F2
По определению:
A-1: 1'0000 = 0 0'0111 = 8 0'0100 = 5 0'1111 = 16(-1)
+ 0'0100 = 5 + 0'1101 = 14 + 0'1011 = 12 + 0'0001 = 2
--------- --------- -------- --------
? + 1'0100 =<22>17=5 + 0'1111 =<17>17=0 1'0000 =<18>17=1
L--> 0 =+1-1=inv(1) L--> 1 =+1-0=inv(0) L--> 0 =+1-1=inv(1)
--------- --------- -------- --------
0'0100 = 5 0'0100 = 5 1'0000 = 0 0'0000 = 1
------------------------------------------------------------------------------
ОТРИЦАНИЕ
< -x >F2 5-ти битового ВЫЧЕТа mod Fermat2
Знак минус < -x >F2 = < F2-x >F2 = <17-x>17 или (17 XOR x) — инверсия битов для x<>0
По определению:
A-1: — 1'0000 = 0 -(+8) -(+5) -(-1)=16
--------- XOR 0'1111 XOR 0'1111 XOR 0'1111 = F2-1 = 17-1 = 16
? 0'0111 = 8 0'0100 = 5 0'1111 =-1
--------- -------- -------- --------
1'0000 = 0 0'1000 =-8=<17-8>17=9 0'1011 =-5=<17-5>17=12 0'0000 =+1=<17-(-1)>17=<18>17=1
(1+16-8=9) (1+16-5=12) (1+16-16=1)
------------------------------------------------------------------------------
УМНОЖЕНИЕ на 2
< 2*g >F2 на 2 в (A-1)-арифметике равно < < 2*(g-1) > +1 >F2
или < < 2*(g1) > +1 >F2
По определению: По определению:
A-1: 1'0000 = 0 0'1010 = 11 0'0100 = 5
* 0'0111 = 8 * 0'0111 = 2^3=8 * 0'0000 = 1
--------- --------- --------
? + 101'0000 <- сдвиг на 3 бита ?
L--> 010 = inv(101) <- Приведение вычета <88>17
--------- --------- --------
1'0000 = 0 0'0010 = 3=<88>17 0'0100 = 5
------------------------------------------------------------------------------
УМНОЖЕНИЕ любых чисел
< g*h >F2 в (A-1)-арифметике равно
< g*h-1 >F2 = <(g-1)*(h-1)+<(g-1)+(h-1)> >F2 =
1-й метод = < g1 * h1 +< g1 + h1 > >F2
Умножение < g*h >F2 в (A-1)-арифметике равно
< g*h-1 >F2 = <
|
Три дела, однажды начавши, трудно кончить:
1) вкушать хорошую пищу;
2) беседовать с другом, возвратившимся из похода
и
3) чесать, где чешется.
Козьма Прутков
"Мысли и афоризмы",45.
|
|
▲ В начало текущей ДП Фурье в конечных полях ► |
|
Последнее обновление 16.09.2013
c 2005 г., Александр Тимофеев, г.Харьков, Украина, eMail: atimopheyev@yahoo.com |