÷ÓÅ Ï ÇÅÏÌÏÇÉÉ :: ÎÁ ÇÌÁ×ÎÕÀ ÓÔÒÁÎÉÃÕ! çÅÏ×ÉËÉÐÅÄÉÑ 
wiki.web.ru 
ðÏÉÓË  
   Rambler's Top100 Service
 çÌÁ×ÎÁÑ ÓÔÒÁÎÉÃÁ  ëÏÎÆÅÒÅÎÃÉÉ: ëÁÌÅÎÄÁÒØ / íÁÔÅÒÉÁÌÙ  ëÁÔÁÌÏÇ ÓÓÙÌÏË    óÌÏ×ÁÒØ       æÏÒÕÍÙ        ÷ ÐÏÍÏÝØ ÓÔÕÄÅÎÔÕ     ðÏÓÌÅÄÎÉÅ ÐÏÓÔÕÐÌÅÎÉÑ
   çÅÏÌÏÇÉÑ | ëÕÒÓÙ ÌÅËÃÉÊ
 ïÂÓÕÄÉÔØ × ÆÏÒÕÍÅ  äÏÂÁ×ÉÔØ ÎÏ×ÏÅ ÓÏÏÂÝÅÎÉÅ
÷ÐÅÒÅÄ ÷×ÅÒÈ îÁÚÁÄ óÏÄÅÒÖÁÎÉÅ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ
÷ÐÅÒÅÄ: 11.3.5 áÌÇÏÒÉÔÍ ëÏÐÐÅÒÓÍÉÔÁ ÷×ÅÒÈ: 11.3 ìÏÇÁÒÉÆÍÉÒÏ×ÁÎÉÅ × GF(q)* îÁÚÁÄ: 11.3.3 ìÏÇÁÒÉÆÍÉÒÏ×ÁÎÉÅ × ÐÏÌÑÈ ÐÒÏÓÔÏÇÏ ÐÏÒÑÄËÁ   óÏÄÅÒÖÁÎÉÅ   ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ

11.3.4 áÌÇÏÒÉÔÍ èÅÌÌÍÁÎÁ -- òÅÊÎÅÒÉ

òÁÓÓÍÏÔÒÉÍ ÔÅÐÅÒØ ÓÌÕÞÁÊ, ËÏÇÄÁ $ p$ ÎÅ×ÅÌÉËÏ. ôÏÇÄÁ ÄÌÑ ÄÉÓËÒÅÔÎÏÇÏ ÌÏÇÁÒÉÆÍÉÒÏ×ÁÎÉÑ × $ GF(q)*$ ÐÒÉÍÅÎÉÍ ÓÌÅÄÕÀÝÉÊ ÁÌÇÏÒÉÔÍ (ÓÍ. [HR], [Kob, ÇÌ. 4, $ \mathsection$ 3]).

    1. ðÏÌÅ $ GF(q)$ ÐÒÅÄÓÔÁ×ÉÍ × ×ÉÄÅ ÆÁËÔÏÒËÏÌØÃÁ $ GF(p)[y]/(f(y))$, ÇÄÅ $ f(y)=f$ -- ÎÅÐÒÉ×ÏÄÉÍÙÊ ÍÎÏÇÏÞÌÅÎ ÓÔÅÐÅÎÉ $ n$. ðÏÜÔÏÍÕ ÍÏÖÎÏ ÓÞÉÔÁÔØ, ÞÔÏ ÜÌÅÍÅÎÔÙ $ GF(q)$ ÅÓÔØ ÍÎÏÇÏÞÌÅÎÙ ÉÚ $ GF(p)[y]$ ÓÔÅÐÅÎÉ ÎÅ ×ÙÛÅ $ n-1$. üÌÅÍÅÎÔ $ a_1=a^{(q-1)/(p-1)}\bmod f$ ÉÍÅÅÔ ÐÏÒÑÄÏË $ p-1$, ÓÌÅÄÏ×ÁÔÅÌØÎÏ, ÏÎ Ñ×ÌÑÅÔÓÑ ÐÏÒÏÖÄÁÀÝÉÍ $ GF(p)*$. úÎÁÑ ÅÇÏ, ÓÏÓÔÁ×ÌÑÅÍ ÔÁÂÌÉÃÕ ÌÏÇÁÒÉÆÍÏ× "ËÏÎÓÔÁÎÔ" -- ÜÌÅÍÅÎÔÏ× $ GF(p)*$ (ÌÏÇÁÒÉÆÍÙ ÐÏ ÏÓÎÏ×ÁÎÉÀ $ a$). ôÁË ËÁË $ p$ ÎÅ×ÅÌÉËÏ, ÔÏ ÜÔÏ ÍÏÖÎÏ ÓÄÅÌÁÔØ ÜÆÆÅËÔÉ×ÎÏ.

    2. ðÕÓÔØ $ B$ -- ÍÎÏÖÅÓÔ×Ï ×ÓÅÈ ÎÅÐÒÉ×ÏÄÉÍÙÈ ÍÎÏÇÏÞÌÅÎÏ× ÉÚ $ GF(p)[y]$ ÓÔÅÐÅÎÉ ÎÅ ×ÙÛÅ $ m$, ÇÄÅ $ m$ -- ÎÅËÏÔÏÒÏÅ ÎÁÔÕÒÁÌØÎÏÅ ÞÉÓÌÏ, ÍÅÎØÛÅÅ $ n$.

    3. óÌÕÞÁÊÎÏ ÐÅÒÅÂÉÒÁÑ $ t$, $ 1\leqslant t\leqslant q-2$, ÎÁÈÏÄÉÍ ÔÅ ÉÚ ÎÉÈ, ÄÌÑ ËÏÔÏÒÙÈ

$\displaystyle a^t\bmod f=c_0\prod_{g\in B}g^{\alpha_g(t)}, $

ÇÄÅ $ c_0\in GF(p)$ É $ \alpha_g(t)\geqslant0$. (òÁÚÌÏÖÅÎÉÅ $ a^t\bmod f$ ÎÁ ÍÎÏÖÉÔÅÌÉ ÍÏÖÎÏ ÎÁÈÏÄÉÔØ, ÎÁÐÒÉÍÅÒ, Ó ÐÏÍÏÝØÀ ÁÌÇÏÒÉÔÍÁ âÅÒÌÅËÜÍÐÁ (ÓÍ. [áËÒ, ÒÁÚÄ. 6.2.4]), ÜÆÆÅËÔÉ×ÎÏÇÏ ÐÒÉ ÍÁÌÙÈ $ p$). éÍ ÓÏÏÔ×ÅÔÓÔ×ÕÀÔ ÕÒÁ×ÎÅÎÉÑ

$\displaystyle t\equiv\log c_0+\sum_{g\in B}\alpha_g(t)\log g\mkern5mu({\rm mod}\,\,q-1) $

ÏÔÎÏÓÉÔÅÌØÎÏ ÎÅÉÚ×ÅÓÔÎÙÈ $ \log g$.

    4. ðÏÌÕÞÉ× ÎÁ ÐÒÅÄÙÄÕÝÅÍ ÜÔÁÐÅ ÄÏÓÔÁÔÏÞÎÏ ÍÎÏÇÏ ÕÒÁ×ÎÅÎÉÊ ÏÔÎÏÓÉÔÅÌØÎÏ $ \log g$, $ g\in B$, ÒÅÛÁÅÍ ÓÉÓÔÅÍÕ ÕÒÁ×ÎÅÎÉÊ É ÎÁÈÏÄÉÍ $ \log g$, $ g\in B$.

    5. îÁÈÏÄÉÍ $ t$, ÔÁËÏÅ, ÞÔÏ

$\displaystyle ba^t\bmod f=c_1\prod_{g\in B}g^{\beta_g}, $

ÇÄÅ $ c_1\in GF(p)$ É $ \beta_g\geqslant0$. ôÏÇÄÁ ÉÓËÏÍÙÊ ÄÉÓËÒÅÔÎÙÊ ÌÏÇÁÒÉÆÍ ÒÁ×ÅÎ

$\displaystyle \log b=\left(-t+\log c_1+\sum_{g\in B}\beta_g\log g\right)\bmod(q-1). $

üÔÏÔ ÁÌÇÏÒÉÔÍ ÉÍÅÅÔ ÓÕÂÜËÓÐÏÎÅÎÃÉÁÌØÎÕÀ ÓÌÏÖÎÏÓÔØ.

îÅÓËÏÌØËÏ ÉÎÕÀ ÓÈÅÍÕ ÌÏÇÁÒÉÆÍÉÒÏ×ÁÎÉÑ × $ GF(q)*$ ÐÒÅÄÌÏÖÉÌ üÌØ çÁÍÁÌØ [ElG84], [ElG85], [ElG86]. ïÃÅÎËÁ ÓÌÏÖÎÏÓÔÉ ÁÌÇÏÒÉÔÍÏ× üÌØ çÁÍÁÌÑ ÓÕÂÜËÓÐÏÎÅÎÃÉÁÌØÎÁÑ (ÐÒÉ ÎÅËÏÔÏÒÙÈ Ü×ÒÉÓÔÉÞÅÓËÉÈ ÄÏÐÕÝÅÎÉÑÈ).

÷ÐÅÒÅÄ ÷×ÅÒÈ îÁÚÁÄ óÏÄÅÒÖÁÎÉÅ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ
÷ÐÅÒÅÄ: 11.3.5 áÌÇÏÒÉÔÍ ëÏÐÐÅÒÓÍÉÔÁ ÷×ÅÒÈ: 11.3 ìÏÇÁÒÉÆÍÉÒÏ×ÁÎÉÅ × GF(q)* îÁÚÁÄ: 11.3.3 ìÏÇÁÒÉÆÍÉÒÏ×ÁÎÉÅ × ÐÏÌÑÈ ÐÒÏÓÔÏÇÏ ÐÏÒÑÄËÁ   óÏÄÅÒÖÁÎÉÅ   ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ

ðÒÏÅËÔ ÏÓÕÝÅÓÔ×ÌÑÅÔÓÑ ÐÒÉ ÐÏÄÄÅÒÖËÅ:
 çÅÏÌÏÇÉÞÅÓËÏÇÏ ÆÁËÕÌØÔÅÔÁ íçõ,
òææé
    
TopList Rambler's Top100