Первісні корені та індекси. Загальні теореми

Страницы работы

10 страниц (Word-файл)

Содержание работы

Первісні корені та індекси

1.  Загальні теореми

a.  При (a,m)=1 існує додатнє γ з умовою αγ≡1(modm), наприклад (теорема Ейлера), γ=φ(m). Найменше з них зветься: показник, якомуaналежить по модулю m.

b.  Якщо a по модулю m належить показнику δ, то числа 1=a0,a1, …, aδ-1 по модулю m непорівнянні.

Дійсно, з al≡ ak(modm), 0≤k<l<δ, слідує al-k≡1(mod m); 0<1-k<δ, що протирічить означенню δ.

c.  Якщо a по модулю m належить показнику δ, то aγ≡aγ(mod m)тоді і тільки тоді, коли γ≡γ’(mod δ); зокрема (при γ’=0), aγ≡1(mod m) тоді і тільки тоді, коли γ ділиться на δ.

Дійсно, нехай r і r1 найменші додатні лишки чисел γ і γ' по модулю δ; тоді деяких q та q1маємо γ=δq+r, γ'=δq1+r1. Звідси та з aδ≡1(modm) слідує

aγ=(aδ)qar≡ar(mod m)

a γ=(aδ)q(mod m)

Отже, aγ≡aγ(mod m) тоді і тільки тоді, коли ar(mod m), тобто (b), коли r=r1.

d.  Нехай a по модулю m належить показнику δ. Тоді з с (γ'=0) та з aφ(m)≡1(mod m) слідує, що φ(m) ділиться на δ. Таким чином, показники, яким числам належать по модулю m, є дільниками φ(m). Найбільших з цих дільників є сама φ(m). Числа, які належать показнику φ(m) (якщо такі існують), називаються первісними коренями по модулю m.

2.  Первісні корені по модулям pαта 2pα

a.  Нехай p – просте непарне число та α≥1. Доведемо існування первісних коренів по модулям pα та 2pα.

b.  Якщо x(mod m) належить показнику ab, то xa належить показнику b.

Дійсно, нехай xa належить показнику δ. Тоді (xa)δ≡1(mod m), звідки xaδ ≡ 1(mod m); отже (1,c), a δ ділиться на ab, тобто δ ділиться на b. З іншої сторони, xab ≡ 1(mod m), звідси (xa)b≡ 1(mod m); отже (1,c), b ділиться на δ. Значить δ=b.

c.  Якщо x по модулю mналежить показнику a, а y – показнику b, причому (a,b)=1, то xy належить показнику ab.

Дійсно, нехай xy належить показнику δ. Тоді (xy)δ≡1(modm). Звідси xbδybδ≡1(modm)(c, 1)xbδ≡1(modm). Отже, (c, 1)bδділиться на a. І так як (b,a)=1, то δ ділиться на a. Так само знаходимо, що δ ділиться і на ab. З іншої сторони, з (xy)ab≡1(modm)маємо (c, 1), що abділиться на δ. Отже δ=ab.

d.  Існують первісні корені по модулю p.

Дійсно, нехай

δ1, δ2, …, δr                        (1)

-всі різні показники, котрим по модулю p належать числа 1, 2, …, (p-1). Нехай τ – найменше спільне кратне цих показників та

- його канонічний розклад. Кожен множник  цього розкладу ділить хоча б одне число δj ряда (1), котре може бути представлено у вигляді: . Нехай ξj – однеізчисел ряду 1, 2, …, (p-1), які належать показнику δj. Згідно з b число належить показнику , згідно з c добуток g=ξ1ξ2…ξkналежить показнику . Отже (d, 1) τ – дільник p-1.

Але оскільки числа (1) ділять τ, всі 1, 2, …, (p-1) є розв’язками (c, 1) конгруенції xτ≡1(mod p); отже будемо мати p-1≤τ. Звідси, τ=p-1, та g–первісний корінь.

e.  Нехай g – первісний корінь по модулю p. Можемо вказати t з умовою, яка визначена рівністю (g+pt)p-1=1+pu, не ділиться на p. Відповідні g+pt буде первісним коренем по модулю pα при будь яких α>1.

Дійсно, маємо

gp-1=1+pT0                            (2)

(g+pt)p-1=1+p(T0-gp-2t+pT)=1+pu

де, одночасно з t, u пробігає повну систему лишків по модулю p. Тому можна вказати t з умовою, що u не ділиться на p. При такому t з (2) виводимо

(g+pt)p(p-1)=(1+pu)p=1+p2u2

………………………………………………………….                         (3)

де всі u2, u3, …, uα також не діляться на p. Нехай g+pt належить показнику δ по модулю pα. Тоді маємо (g+pt)δ≡1(modpα), звідси знаходимо g δ≡1(modp). Тому (1,c) δ ділиться на p-1 та, будучи (1,d) дільником числа φ(pα)=pα-1(p-1), повинно мати вигляд δ=pr-1(p-1), де r – одне з чисел 1, …, α. Так як рівності (2) та (3) показують, що конгруенція

вірно при r=α та невірно при r<α, то (d, 1)δ=pα-1(p-1)=φ(pα) та g+pt – первісний корінь по pα.

f.  Нехай α≥1 та g – первісний корінь по модулю pα. Непарне g0 зчисел g та g+pα ,буде первісним коренем по модулю 2pα.

Дійсно, φ(pα) та φ(2pα) рівні між собою (маємо φ(2pα)=φ(2)φ(pα)=φ(pα)); їх спільне значення позначають буквою c. Далі легко впевнитися що конгруенції  та  можуть виконуватися лише одночасно (  ділиться на 2). А так як g0 – первісний корінь по модулю pα і перша конгруенція вірна при r=c і невірна при r<c, тим самим і друга конгруенція вірна при r=c і невірна при r<c та g0–первісний корінь по модулю 2pα.

3.  Пошук первісних коренів по модулям pαта 2pα

a.  Первісні корені по модулям pαта 2pα, де p–просте непарне число і α≥1, можна знайти, користуючись наступною загальною теоремою:

Нехай c=φ(m) та q1, q2, …, qk – різні прості дільники числа c. Для того, щоб число g взаємно просте з m, було первісним коренем по модулю m, необхідно та достатньо, щоб це g не задовольняло ні одну з конгруенцій.

Похожие материалы

Информация о работе

Предмет:
Криптография
Тип:
Конспекты лекций
Размер файла:
324 Kb
Скачали:
0