Arithmetics.HTM
Выше     ДП Фурье в конечных полях

Арифметики в конечных числовых полях

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≤restM1. Остаток rest называют ВЫЧЕТом по модулю M.

Например, при M=3   и   при   M=5
a = M·div + rest
a = M·div + rest
0 = 3·0 + 0
1 = 3·0 + 1
2 = 3·0 + 2
3 = 3·1 + 0
4 = 3·1 + 1
5 = 3·1 + 2
6 = 3·2 + 0
7 = 3·2 + 1 и т.д.
0 = 5·0 + 0
1 = 5·0 + 1
2 = 5·0 + 2
3 = 5·0 + 3
4 = 5·0 + 4
5 = 5·1 + 0
6 = 5·1 + 1
7 = 5·1 + 2 и т.д.

Если 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, и называются взаимно простыми (или неделимыми относительно друг друга).

Например,
(5,2)=1
(5,4)=1
 
 
(17, 2)=1
(17, 4)=1
(17, 8)=1
(17,16)=1
2 | 4
 
 
 
2 | 16
 
 
 
4 | 16
 
 
 
8 | 16
 
 
 

Любое составное число  a  можно представить в виде произведения степеней простых чисел   p1, p2, ...

a = p1(n1)·p2(n2) ... = pk(nk) ,   k=1,2,..
Основная теорема арифметики, доказанная Гауссом, утверждает, что это представление единственно.

Например,
    16=24
  256=28
65536=216


 
Что остаётся от сказки потом,
после того, как её рассказали?
                               Владимир Высоцкий
          "Песня Кэрролла" из музыкальной сказки
       "Алиса в стране чудес" по Льюису Кэрроллу.

Сравнения и ВЫЧЕТы.

Каждому ВЫЧЕТу rest=0..M1 соответствует много целых чисел a,b,... Говорят, что числа с одинаковым ВЫЧЕТом сравнимы по модулю M и обозначают так:

      ab mod M или
      ab (mod M) или (ab) modulo M (введено Гауссом) или
      ab ( M ), т.е. без mod (введено в ) или
    ((ab)) M или ((ab))M или
      a( b ) M (это современные варианты без mod) или
    ab M или
    a M = b M, т.е. без   mod   и   знак   равно (сравнимо)   вместо   знака тождества (введено Рейдером в )

Например, при M=3
и rest=0 сравнимы по модулю 3 числа .., −9, −6, −3, 0, 3, 6,   9,..
и rest=1 сравнимы по модулю 3 числа .., −8, −5, −2, 1, 4, 7, 10,..
и rest=2 сравнимы по модулю 3 числа .., −7, −3, −1, 2, 5, 8, 11,..
              а при M=5
и rest=0 сравнимы по модулю 5 числа .., −15, −10, −5, 0, 5, 10, 15,..
и rest=1 сравнимы по модулю 5 числа .., −14,   −9, −4, 1, 6, 11, 16,..
и rest=2 сравнимы по модулю 5 числа .., −13,   −8, −3, 2, 7, 12, 17,..
и rest=3 сравнимы по модулю 5 числа .., −12,   −7, −2, 3, 8, 13, 18,..
и rest=4 сравнимы по модулю 5 числа .., −11,   −6, −1, 4, 9, 14, 19,..

Числа a, которые сравнимы по модулю M, образуют класс своего ВЫЧЕТа rest и определяются как a=rest+div·M. Числа a тоже называют ВЫЧЕТами по модулю M. Неотрицательные ВЫЧЕТы a=rest (при div=0), принимающие значения из интервала [0..M1], образуют

      ПСНВ+ mod MПолная Система Наименьших Вычетов
  по модулю M.

ВЫЧЕТы   a , принимающие значения из интервала

[ div·M+0...(div·M + M1)], где div=1,2,..
образуют
      ПСВ mod MПолная Система Вычетов (но не наименьших)
  по модулю M.

ВЫЧЕТы   a , принимающие значения из интервала

[−(M1)/2) ... (M1)/2] , при нечётном M
или из интервала
        [-M/2 ... M/2-1] , при чётном M ,
образуют
      ПСАНВ± mod MПолная Система Абсолютно Наименьших Вычетов
  по модулю M.

Например, при M=5 классы наименьших ВЫЧЕТов по модулю 5 образуют ВЫЧЕТы:
rest =   0,   1, 2, 3, 4ПСНВ+ mod 5,
    a =2, −1, 0, 1, 2ПСАНВ± mod 5,

а классы НЕ наименьших ВЫЧЕТов по модулю 5 образуют ВЫЧЕТы:

b1 = rest + 1·5 =   5,  6,   7,   8,   9ПСВ mod 5
b2 = rest + 2·5 = 10, 11, 12, 13, 14ПСВ mod 5 и т.д.

Класс ВЫЧЕТов, элементы которого взаимно просты с модулем M называют приведеным. Функция Эйлера φ(M) определяет сколько ВЫЧЕТов из ПСНВ+ по модулю M взаимно просты с M. При простом M=p имеем

φ(p) = p1 .


 
А для низкой жизни были числа,
Как домашний, подъяремный скот,
Потому что все оттенки смысла
Умное число передаёт.
                        Николай Гумилёв

Группы, кольца, поля чисел.

      ПСНВ+ mod M   при простом   M=p   образует конечное поле порядка M или простое поле Галуа   GF(p)   в отличии от расширенного поля Галуа   GF(pr)   при M=pr,   а при составном Mкоммутативное или абелево кольцо ZM (или Z/(M) ). Числовое поле формально определяется системой аксиом. Упрощенно говоря, абелевой группой является множество, в котором можно "складывать" и "вычитать", в кольце можно ещё и "умножать", а в поле, кроме этого, можно ещё и "делить".

Например, абелевыми будут:
Z — кольцо обычных целых чисел (тип integer);
Z[j] — кольцо целых комплексных чисел γ=u+jv ,
    где u и v — целые числа;
Zμ[j] - кольцо целых комплексных чисел Гаусса γ mod μ или γ μ ,
    где μ=p+jq ,   а   p и q — взаимно простые числа, т.е. НбОД (p,q)=1;
ZM (или Z/(M) ) - кольцо ВЫЧЕТов по модулю целого составного числа M;
ZM[j] - кольцо целых комплексных чисел λ = a M + j b M ,
    где a, b и M — целые числа;
GF(M) — простое поле Галуа (конечная алгебра) порядка M ,
    где M — простое целое;
GF(pr) — расширенное поле Галуа (конечная алгебра) порядка pr ,
    где характеристика p — простое (неделимое) число,
    а размерность поля r — натуральное число;
Q(0) — поле рациональных чисел (характеристики 0);
R(0) — поле вещественных чисел (характеристики 0);
C(0) — поле комплексных чисел (характеристики 0);
< (·),R+ > - мультипликативная группа положительных вещественных чисел;
< (+),R > - аддитивная группа всех вещественных чисел.



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

                      Козьма Прутков
               "Мысли и афоризмы",66.

Изоморфизм.

Две похожие по структуре и свойствам группы H и G называют изоморфными, обозначается H~G, если найдется отображение ψ:HG такое, что

ψ(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 , ... — составные.

ПСНВ+ поля
GF(F0) — это 2-битовые числа из интервала [0..21= 2 ] ,
GF(F1) — это 3-битовые числа из интервала [0..22= 4 ] ,
GF(F2) — это 5-битовые числа из интервала [0..24= 16 ] ,
GF(F3) — это 9-битовые числа из интервала [0..28=256 ] ,
GF(F4) — это 17-битовые числа из интервала [0..216=65536 ] ,

ПСНВ+ кольца
Z/(F5) — это 33-битовые числа из интервала [0..232=4294967296 ] ,
Z/(F6) — это 65-битовые числа из интервала [0..264 ] ,
Z/(F7) — это 129-битовые числа из интервала [0..2128 ] .

Составные числа Ферма имеют вид (Лукас)

Fn = U1·U2·... ,
где сомножители Uk — простые (?) и имеют вид
Uk = Ck·2(n+2)+1.
Например,
F5 = 4'294'967'297 = 641 · 6'700'417 =
( 5 · 2(5+2)+1) ·
· (52347 · 2(5+2)+1)  
F6 = 274177 · 67'280'421'310'721 =
(1'071 · 2(6+2)+1) ·
· (262'814'145'745 · 2(6+2)+1)  
F7 = 59'649'589'127'497'217 · 5'704'689'200'685'129'054'721 =
(116'503'103'764'643 · 2(7+2)+1) ·
· (11'141'971'095'088'142'685 · 2(7+2)+1)  
Посчитано при помощи спецкалькулятора Яна Хованского по имени Algebry

Перейти к: Числа Ферма из энциклопедии "Википедия" (ru.wikipedia.org)


 
Смотри в корень
                 Козьма Прутков
           "Мысли и афоризмы",5.

Первообразные КОРНИ.

Пусть rootКОРЕНЬ T-й степени из 1 по модулю Fn , т.е. формально это корень (решение)

root T1 mod Fn
уравнения
rootT Fn = 1 .
Тогда ВЫЧЕТы по модулю Fn   k-ых степеней root , т.е.
rootk Fn , при k=0,1,...,T1
образуют циклическую группу порядка T (т.е. группу из T элементов).

В случае простого Fn по теореме Эйлера имеем

φ(Fn) = Fn1 = Tmax = O(Fn) .
При   T=Tmax=(Fn1)   КОРЕНЬ   root называется   примитивным (primitive) или первообразным (порождающим, образующим) КОРНЕМ по модулю Fn , а при T<Tmax=(Fn1) КОРЕНЬ root называется просто КОРНЕМ порядка T (или степени T) по модулю Fn или иначе формально
rootT Fn = 1 ,
где T0 и T принадлежит ПСНВ+ mod Fn , и все степени
rootk Fn 0 ,
при k=0,1,...,T1 (TFn1) принимают неповторяющиеся значения из интервала [1,...,(Fn1)] , причём T должно делить Tmax = (Fn1) = 2b , т.е.
T | (Fn1) .

Например, для   n=1   имеем   b=2n=21=2   и простое число Ферма

F1 = 2b+1 = 22+1 = 5
имеет такие КОРНИ:
  34 5 =1, где 3 — примитивный КОРЕНЬ порядка 2b=F11=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, т.е. rootN1 mod Fn , то другие КОРНИ rootm=rootp будут иметь порядок N/p, если p|N. Нас интересует случай КОРНЯ root=2, порядок которого по модулю чисел Ферма равен N=T2=2b=2n+1. Тогда порядок КОРНЯ rootm должен иметь вид

Trootm = 2k ,
потому, что
Trootm=2k | 2b = (Fn1)=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=F21=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=F31=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=F41=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 существуют ещё 2b1 других примитивных КОРНЕЙ, которые также имеют максимальный порядок

Tmax = 2b = Fn1 = O(Fn)
и могут быть образованы возведением root=3 в нечётную степень.

      Для составных чисел Ферма Fn при   n=5,6,7,...   примитивных (primitive) или первообразных КОРНЕЙ по модулю Fn просто не может быть, а максимальный объём преобразования O(Fn) или максимальный порядок КОРНЯ root равен
Tmax = 2n+2 = 4b = O(Fn) .
У прочих не примитивных КОРНЕЙ root порядки   TTmax   должны также делить 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..171,
образующих циклические группы ВЫЧЕТов порядка T ,
т.е. порядка КОРНЕЙ root mod F2=17 .


  root=4, T=4
root=4117=13, T=4
root=2, T=8
root=2117=9, T=8
root=217=6, T=16
root=(2)1=6117=3, T=16
k 4k 17 4-k 17 2k 17 2-k 17 6k 17 6-k 17 = 3k 17
  ПСНВ+ ПСАНВ± ПСНВ+ ПСАНВ± ПСНВ+ ПСАНВ±
   0
   1
   2
   3
   4
   5
   6
   7
   8
   9
 10
 11
 12
 13
 14
 15
 16
  1 +1
  4 +4
16 -1
13 -4
  1
  4
16
13
  1
  4
16
13
  1
  4
16
13
  1
  1 +1
13 -4
16 -1
  4 +4
  1
13
16
  4
  1
13
16
  4
  1
13
16
  4
  1
  1 +1
  2 +2
  4 +4
  8 +8
16 -1
15 -2
13 -4
  9 -8
  1
  2
  4
  8
16
15
13
  9
  1
  1 +1
  9 -8
13 -4
15 -2
16 -1
  8 +8
  4 +4
  2 +2
  1
  9
13
15
16
  8
  4
  2
  1
  1 +1
  6 +6
  2 +2
12 -5
  4 +4
  7 +7
  8 +8
14 -3
16 -1
11 -6
15 -2
  5 +5
13 -4
10 -7
  9 -8
  3 +3
  1
  1 +1
  3 +3
  9 -8
10 -7
13 -4
  5 +5
15 -2
11 -6
16 -1
14 -3
  8 +8
  7 +7
  4 +4
12 -5
  2 +2
  6 +6
  1


 
Где начало того конца, которым
оканчивается начало?
                     Козьма Прутков
              "Мысли и афоризмы",78.

(A-1)-арифметика ВЫЧЕТов по модулю чисел Ферма

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

Рассмотрим таблицу соответствия между естественной формой представления чисел в обычной A-арифметике и формой представления чисел в (A-1)-арифметике, у которых совпадает битовое представление для случая b=2n=22=4, т.е. в арифметике операций по модулю числа Ферма F2=17.

Число в обычной
A-арифметике
Двоичное (битовое)
представление
Число с уменьшенным на 1 битовым образом в (A-1)-арифметике
ПСНВ+ ПСАНВ± 5-й и 4 младших

ПСНВ+ ПСАНВ±
  0   0
  1 +1
  2 +2
  3 +3
  4 +4
  5 +5
  6 +6
  7 +7

        отриц. в
    дополн.коде

  8 -8
  9 -7
10 -6
11 -5
12 -4
13 -3
14 -2
15 -1
16  ??




















0 ' 0000
0 ' 0001
0 ' 0010
0 ' 0011
0 ' 0100
0 ' 0101
0 ' 0110
0 ' 0111




0 ' 1000
0 ' 1001
0 ' 1010
0 ' 1011
0 ' 1100
0 ' 1101
0 ' 1110
0 ' 1111
1 ' 0000




















  1 +1
  2 +2
  3 +3
  4 +4
  5 +5
  6 +6
  7 +7
  8 +8


        инверсия 4-х младших битов

  9 -8
10 -7
11 -6
12 -5
13 -4
14 -3
15 -2
16 -1
  0   0

Числа с одинаковым битовым представлением в (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=2p1 , (которую называют комплементарной до 1 или арифметикой в дополнительном коде, в котором отрицательные целые образуются из положительных инверсией битов и прибавлением 1, а при преобразовании, например из 8 бит в 16 бит, дополняются единицами в старших битах) и может быть реализована на стандартных компьютерах с длиной регистров b=2n бит.

NB. В современных персональных компьютерах (с процессорами Intel PENTIUM) имеются 8-, 16-, 32-, 64-битные регистры и команды для операций с целыми числами на этих регистрах. Поэтому арифметические операции по модулю чисел Ферма над целыми в (A-1)-арифметике можно реализовать программно на ассемблере или на языке программирования высокого уровня, например, Pascal, C/C++, Modula-2 или Оберон.

(*
  Примеры операций в (А-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 = < F2 — 1 >F2 =       
         1а-й метод                    = < F2 — 1 >F2        
  Умножение < g*h >F2 в (A-1)-арифметике равно                     
                           < g*h-1 >F2 = < g*(h-1)+(g-1)>F2 =           
         2-й метод                     = < g*h1   + g1  >F2       

  Умножение < g*h >F2 в (A-1)-арифметике равно             
                         < g*h-1 >F2 = < g*(h-1)+(g-1) >F2 =
         2-й метод ->                = < g*h1   + g1   >F2
    или                  < g*h-1 >F2 = <(g-1)*h +(h-1) >F2 =
         2-й метод ->                = < g1*h   + h1   >F2

......................................... умножение на 0 .....................
  По  определению:
 A-1:   1'0000 = 0      0'0111 = 8
      * 0'0100 = 5    * 1'0000 = 0
     ---------       ---------
             ?               ?
     ---------       ---------
        1'0000 = 0      1'0000 = 0

............................................. 1-й метод ......................
  Умножение < g*h >F2 в (A-1)-арифметике равно                    
                         < g*h-1 >F2 = <(g-1)*(h-1)+<(g-1)+(h-1)>F2 >F2 =
                                     = < g1  * h1  +< g1  + h1  >F2 >F2 
  По  определению:
 A-1:   1'0000 = 0      0'0111 = 8          0'1110 = 15(14)           0'1110 = 15 (14)
      * 0'0100 = 5    * 1'0000 = 0        * 0'1001 = 10 (9)         + 0'1001 = 10 ( 9)
     ---------       ---------           ---------                  --------
             ?               ?       +      0'1110 = + (14)=(14)*1  + 1'0111
                                         0111'0    =  (112)=(14)*8    L--> 0 = inv(1) <- Приведение вычета <>17
                                     -------------                  -------- 
                                     +   0111'1110 =<126>17=14        0'0111 =<15+10>17=8
                                            0'0111 =  8 <-------------------------------<
                                     -------------
                                     +   1000'0101
                                         L--> 0111 = inv(1000) <- Приведение вычета <>17
                                          --------
                                          + 0'1100
                                            L->  1 = inv(0)
     ---------       ---------            --------
        1'0000 = 0      1'0000 = 0          0'1101 = 14 = <15*10>17

............................................. 1a-й метод ......................
  Умножение < g*h >F2 в (A-1)-арифметике равно            
                         < g*h-1 >F2 = < < g*h >F2 — 1 >F2 =
                                     = < < g*h >F2 — 1 >F2
  По  определению:
 A-1:   1'0000 = 0      0'0111 = 8          0'1110 = 15(14)
      * 0'0100 = 5    * 1'0000 = 0          L--> 1 = inv(0)
     ---------       ---------           ---------
             ?               ?              0'1111-------------->    0'1111
                                                            ---->  * 0'1010
                                                            ¦       -------
                                            0'1001 = 10( 9) ¦   +   01'1110
                                            L--> 1 = inv(0) ¦     0111'1   
                                         ---------          ¦        ---------
                                            0'1010-----------   + 1001'0110
                                                                  L--> 0110 = inv(1001) <- Приведение вычета <>17 
                                                                  ---------
                                                                     0'1100
                                                                     L--> 1 = inv(0)
     ---------       ---------                                    ---------
        1'0000 = 0      1'0000 = 0                                   0'1101 = 14=<15*10>17
------------------------------------------------------------------------------
*)
 

Три дела, однажды начавши, трудно кончить:
1) вкушать хорошую пищу;
2) беседовать с другом, возвратившимся из похода
 и
3) чесать, где чешется.
                                  Козьма Прутков
                           "Мысли и афоризмы",45.

В начало текущей     ДП Фурье в конечных полях






Последнее обновление 16.09.2013

c 2005 г., Александр Тимофеев, г.Харьков, Украина, eMail: atimopheyev@yahoo.com