÷ÓÅ Ï ÇÅÏÌÏÇÉÉ :: ÎÁ ÇÌÁ×ÎÕÀ ÓÔÒÁÎÉÃÕ! çÅÏ×ÉËÉÐÅÄÉÑ 
wiki.web.ru 
ðÏÉÓË  
   Rambler's Top100 Service
 çÌÁ×ÎÁÑ ÓÔÒÁÎÉÃÁ  ëÏÎÆÅÒÅÎÃÉÉ: ëÁÌÅÎÄÁÒØ / íÁÔÅÒÉÁÌÙ  ëÁÔÁÌÏÇ ÓÓÙÌÏË    óÌÏ×ÁÒØ       æÏÒÕÍÙ        ÷ ÐÏÍÏÝØ ÓÔÕÄÅÎÔÕ     ðÏÓÌÅÄÎÉÅ ÐÏÓÔÕÐÌÅÎÉÑ
   çÅÏÌÏÇÉÑ | ëÕÒÓÙ ÌÅËÃÉÊ
 ïÂÓÕÄÉÔØ × ÆÏÒÕÍÅ  äÏÂÁ×ÉÔØ ÎÏ×ÏÅ ÓÏÏÂÝÅÎÉÅ
÷ÐÅÒÅÄ ÷×ÅÒÈ îÁÚÁÄ óÏÄÅÒÖÁÎÉÅ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ
÷ÐÅÒÅÄ: 13.5 ðÏÓÔÒÏÅÎÉÅ ÂÏÌØÛÉÈ ÐÒÏÓÔÙÈ ÞÉÓÅÌ n Ó ÉÓÐÏÌØÚÏ×ÁÎÉÅÍ ÞÁÓÔÉÞÎÏÇÏ ÒÁÚÌÏÖÅÎÉÑ n-1 ÎÁ ÍÎÏÖÉÔÅÌÉ ÷×ÅÒÈ: 13. íÅÔÏÄÙ ÐÏÓÔÒÏÅÎÉÑ ÂÏÌØÛÉÈ ÐÒÏÓÔÙÈ ÞÉÓÅÌ îÁÚÁÄ: 13.3 ðÒÏÓÔÙÅ ÞÉÓÌÁ ÓÐÅÃÉÁÌØÎÏÇÏ ×ÉÄÁ   óÏÄÅÒÖÁÎÉÅ   ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ


13.4 ðÏÓÔÒÏÅÎÉÅ ÂÏÌØÛÉÈ ÐÒÏÓÔÙÈ ÞÉÓÅÌ Ó ÉÓÐÏÌØÚÏ×ÁÎÉÅÍ ÐÏÌÎÏÇÏ ÒÁÚÌÏÖÅÎÉÑ ÎÁ ÐÒÏÓÔÙÅ ÍÎÏÖÉÔÅÌÉ

èÏÒÏÛÏ ÉÚ×ÅÓÔÅÎ ÓÌÅÄÕÀÝÉÊ ÒÅÚÕÌØÔÁÔ (ÓÍ., ÎÁÐÒÉÍÅÒ, ÏÂÚÏÒ [÷ÁÓ1]).

ôÅÏÒÅÍÁ 5.  ðÕÓÔØ $ n$ -- ÎÅÞÅÔÎÏÅ ÎÁÔÕÒÁÌØÎÏÅ ÞÉÓÌÏ, $ n>1$, É $ n-1=\prod\limits_{j=1}^mp_j^{e_j}$ -- ÉÚ×ÅÓÔÎÏÅ ÒÁÚÌÏÖÅÎÉÅ $ n-1$ ÎÁ ÐÒÏÓÔÙÅ ÍÎÏÖÉÔÅÌÉ $ p_j$. åÓÌÉ ÄÌÑ ËÁÖÄÏÇÏ $ j=1,\ldots,m$ ÓÕÝÅÓÔ×ÕÅÔ ÎÁÔÕÒÁÌØÎÏÅ ÞÉÓÌÏ $ a_j$ ÔÁËÏÅ, ÞÔÏ

$\displaystyle a_j^{n-1}\equiv1\mkern5mu({\rm mod}\,\,n)$   É$\displaystyle \quad a_j^{(n-1)/p_j}\not\equiv1\mkern5mu({\rm mod}\,\,n), $

ÔÏ $ n$ -- ÐÒÏÓÔÏÅ ÞÉÓÌÏ.

îÁ ÜÔÏÊ ÔÅÏÒÅÍÅ ÏÓÎÏ×ÁÎ ÓÌÅÄÕÀÝÉÊ ÍÅÔÏÄ íÉÌÌÅÒÁ ÐÏÓÔÒÏÅÎÉÑ ÂÏÌØÛÉÈ ÐÒÏÓÔÙÈ ÞÉÓÅÌ. äÌÑ ÎÅËÏÔÏÒÏÇÏ ÎÁÂÏÒÁ ÉÚ×ÅÓÔÎÙÈ ÐÒÏÓÔÙÈ ÞÉÓÅÌ $ p_1=2,p_2,\ldots,p_m$ É ÐÏËÁÚÁÔÅÌÅÊ $ e_1,\ldots,e_m$ ×ÙÞÉÓÌÑÅÍ $ n=p_1^{e_1}\ldots p_m^{e_m}+1$. ó ÐÏÍÏÝØÀ ÎÅËÏÔÏÒÏÇÏ ×ÅÒÏÑÔÎÏÓÔÎÏÇÏ ÔÅÓÔÁ (ÓÍ. ÒÁÚÄÅÌ 13.2) ÐÒÏ×ÅÒÑÅÍ, ÎÅ Ñ×ÌÑÅÔÓÑ ÌÉ $ n$ ÓÏÓÔÁ×ÎÙÍ. åÓÌÉ ÎÅÔ, Ô. Å. $ n$ ×ÅÒÏÑÔÎÏ ÐÒÏÓÔÏÅ, ÔÏ ÇÅÎÅÒÉÒÕÅÍ ÓÌÕÞÁÊÎÕÀ ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏÓÔØ $ a_1,a_2,\ldots$ ÎÁÔÕÒÁÌØÎÙÈ ÞÉÓÅÌ ÉÚ ÉÎÔÅÒ×ÁÌÁ $ (1,n)$. äÌÑ ËÁÖÄÏÇÏ $ i$ ×ÙÞÉÓÌÑÅÍ $ a_i^{n-1}\bmod n$ É $ a_i^{(n-1)/p_j}\bmod n$ ÄÌÑ ×ÓÅÈ $ j$ ÔÁËÉÈ, ÞÔÏ $ a_l^{(n-1)/p_j}\equiv1\mkern5mu({\rm mod}\,\,n)$ ÐÒÉ ×ÓÅÈ $ l<j$ . åÓÌÉ ÄÌÑ ÎÅËÏÔÏÒÏÇÏ $ i\quad a_i^{n-1}\not\equiv1\mkern5mu({\rm mod}\,\,n)$, ÔÏ $ n$ ÓÏÓÔÁ×ÎÏÅ. ÷ ÐÒÏÔÉ×ÎÏÍ ÓÌÕÞÁÅ ÍÙ ÄÏËÁÖÅÍ, ÞÔÏ $ n$ ÐÒÏÓÔÏÅ, ËÏÇÄÁ ÄÌÑ ×ÓÅÈ $ j=1,\ldots,m$ ÎÁÊÄÅÍ $ i=i(j)$ ÔÁËÏÅ, ÞÔÏ $ a_{i(j)}^{(n-1)/p_j}\not\equiv1\mkern5mu({\rm mod}\,\,n)$.

÷ ÒÁÂÏÔÅ ðÌÅÊÓÔÅÄÁ [Pl] ÕËÁÚÁÎ ÓÐÏÓÏ ÐÒÁ×ÉÌØÎÏÊ ÏÒÇÁÎÉÚÁÃÉÉ ×ÙÞÉÓÌÅÎÉÊ ÄÌÑ ÐÒÏ×ÅÒËÉ ÓÒÁ×ÎÅÎÉÊ ÕËÁÚÁÎÎÏÇÏ ÍÅÔÏÄÁ. á ÉÍÅÎÎÏ, ÓÌÅÄÕÅÔ ÐÏÌÏÖÉÔØ $ d=p_1\ldots p_m$, $ d_1 =p_1\ldots p_{[m/2]}$, $ d_2=p_{[m/2]+1}\ldots p_m$, $ q=(n-1)/d$. óÎÁÞÁÌÁ ÓÌÅÄÕÅÔ ×ÙÞÉÓÌÉÔØ $ a^q\bmod n$, ÚÁÔÅÍ $ (a^q)^{d_i}\bmod n$, $ i=1,2$. îÁËÏÎÅÃ, ÎÕÖÎÏ ×ÙÞÉÓÌÉÔØ

$\displaystyle \left(\left(a^q\right)^{d_1}\right)^{d_2/p_j}\bmod n\quad$ ÄÌÑ$\displaystyle \quad p_j\mid d_1$    

É


$\displaystyle \left(\left(a^q\right)^{d_2}\right)^{d_1/p_j}\bmod n\quad$ ÄÌÑ$\displaystyle \quad p_j\mid d_2,$    

ÄÅÌÁÑ ÜÔÏ ÒÅËÕÒÓÉ×ÎÏ ÔÅÍ ÖÅ ÍÅÔÏÄÏÍ. íÙ ÔÁËÖÅ ÐÒÉ ÜÔÏÍ ÎÁÊÄÅÍ $ a^{n-1}\bmod n$, ×ÏÚ×ÅÄÑ × Ë×ÁÄÒÁÔ $ \left(\left(a^q\right)^{d_2}\right)^{d_1/p_1}\bmod n$, ÔÁË ËÁË $ p_1=2$. ðÒÉ ×ÙÞÉÓÌÅÎÉÑÈ ÜÔÉÍ ÓÐÏÓÏÂÏÍ ÔÒÅÂÕÅÔÓÑ $ O(\log n\,\log\log n)$ ÕÍÎÏÖÅÎÉÊ ÐÏ ÍÏÄÕÌÀ $ n$.

úÁÄÁÄÉÍÓÑ ÔÅÐÅÒØ ×ÏÐÒÏÓÏÍ: ËÁËÏÊ ÉÚ ×ÅÒÏÑÔÎÏÓÔÎÙÈ ÔÅÓÔÏ× É ÓËÏÌØËÏ ÒÁÚ ÐÒÉÍÅÎÑÔØ? òÅËÏÍÅÎÄÕÅÔÓÑ ÔÅÓÔ íÉÌÌÅÒÁ -- òÁÂÉÎÁ (ÓÍ. ÒÁÚÄÅÌ 13.2). ðÏÓËÏÌØËÕ ÎÁ ÏÔÒÅÚËÅ $ [1,n]$ ÄÏÌÑ ÐÒÏÓÔÙÈ ÞÉÓÅÌ ÓÏÓÔÁ×ÌÑÅÔ ÐÒÉÍÅÒÎÏ $ 1/\log n$, ÔÏ ÎÁÄÏ ÐÒÉÍÅÎÉÔØ ÔÅÓÔ $ k$ ÒÁÚ, ÇÄÅ $ k$ ÏÐÒÅÄÅÌÑÅÔÓÑ ÉÚ ÎÅÒÁ×ÅÎÓÔ×Á $ 4^{-k}<1/\log n$. ôÏÇÄÁ ×ÅÒÏÑÔÎÏÓÔØ ÔÏÇÏ, ÞÔÏ $ n$ ÓÏÓÔÁ×ÎÏÅ, ÂÕÄÅÔ ÍÅÎØÛÅ ×ÅÒÏÑÔÎÏÓÔÉ ÔÏÇÏ, ÞÔÏ $ n$ ÐÒÏÓÔÏÅ (ÜÔÏ Ü×ÒÉÓÔÉÞÅÓËÏÅ ÒÁÓÓÕÖÄÅÎÉÅ).

ðÏÄÙÔÏÖÉ×ÁÑ ÓËÁÚÁÎÎÏÅ, ÐÒÏÓÔÏÔÕ $ n$ ÔÁËÏÇÏ, ÞÔÏ $ n-1=\prod\limits_{j=1}^mp_j^{e_j}$, ÐÒÏ×ÅÒÑÅÍ Ó ÐÏÍÏÝØÀ ÓÌÅÄÕÀÝÅÇÏ ÁÌÇÏÒÉÔÍÁ.     1. ôÅÓÔÉÒÕÅÍ $ n$ ÎÁ ÐÒÏÓÔÏÔÕ ÍÅÔÏÄÏÍ íÉÌÌÅÒÁ -- òÁÂÉÎÁ $ k$ ÒÁÚ, ÇÄÅ $ k$ ÏÐÒÅÄÅÌÑÅÔÓÑ ÉÚ ÎÅÒÁ×ÅÎÓÔ×Á $ 4^{-k}<1/\log n$.

    2. åÓÌÉ ÎÅ ÏËÁÚÁÌÏÓØ, ÞÔÏ $ n$ ÓÏÓÔÁ×ÎÏÅ, ÔÏ ÐÅÒÅÂÉÒÁÅÍ ÎÅÓËÏÌØËÏ ÚÎÁÞÅÎÉÊ $ a_i$ É ÄÌÑ ÎÉÈ ÐÒÏ×ÅÒÑÅÍ ÕÓÌÏ×ÉÑ ÍÅÔÏÄÁ íÉÌÌÅÒÁ. ïÂÙÞÎÏ ÐÅÒÅÂÉÒÁÀÔ 4-6 ÚÎÁÞÅÎÉÊ $ a_i$.

    3. åÓÌÉ ÄÏ ÓÉÈ ÐÏÒ ÎÅ ÏÂÎÁÒÕÖÅÎÏ, ÞÔÏ $ n$ ÓÏÓÔÁ×ÎÏÅ É ÎÅ ÄÏËÁÚÁÎÏ, ÞÔÏ $ n$ ÐÒÏÓÔÏÅ, ÔÏ ÄÁÌÅÅ ÞÅÒÅÄÕÀÔ: ÄÌÑ ÏÄÎÏÇÏ $ a$ ÔÅÓÔ íÉÌÌÅÒÁ -- òÁÂÉÎÁ, ÄÌÑ ÔÒÅÈ ÍÅÔÏÄ íÉÌÌÅÒÁ É Ô. Ä. ÄÏ ÔÅÈ ÐÏÒ, ÐÏËÁ ÎÅ ÄÏËÁÖÕÔ, ÞÔÏ $ n$ ÐÒÏÓÔÏÅ ÉÌÉ ÓÏÓÔÁ×ÎÏÅ.

ü×ÒÉÓÔÉÞÅÓËÁÑ ÏÃÅÎËÁ ÓÌÏÖÎÏÓÔÉ ÐÒÏ×ÅÒËÉ ÐÒÏÓÔÏÔÙ ÞÉÓÅÌ $ n$, ÎÅ ÐÒÅ×ÏÓÈÏÄÑÝÉÈ ÎÅËÏÔÏÒÏÊ ÇÒÁÎÉÃÙ $ N$, Ó ÐÏÍÏÝØÀ ÜÔÏÇÏ ÍÅÔÏÄÁ ÓÏÓÔÁ×ÌÑÅÔ $ O\left(\log^2N\right)$ ÁÒÉÆÍÅÔÉÞÅÓËÉÈ ÏÐÅÒÁÃÉÊ ÐÏ ÍÏÄÕÌÀ ÞÉÓÅÌ, ÎÅ ÐÒÅ×ÏÓÈÏÄÑÝÉÈ $ N$.

ôÁËÉÍ ÏÂÒÁÚÏÍ, ÄÌÑ ÐÏÓÔÒÏÅÎÉÑ ÂÏÌØÛÉÈ ÐÒÏÓÔÙÈ ÞÉÓÅÌ ÎÁÍ ÏÓÔÁÅÔÓÑ ÌÉÛØ ÏÐÒÅÄÅÌÉÔØ, ËÁË ×ÙÂÉÒÁÔØ ÎÁÂÏÒ $ (p_1,e_1),\ldots,(p_m,e_m)$, Ô. Å. ËÁËÏÅ ×ÚÑÔØ $ n$. äÌÑ ÜÔÏÇÏ × [Pl] ÐÒÅÄÌÏÖÅÎ ÒÑÄ ÓÔÒÁÔÅÇÉÊ.

÷ÐÅÒÅÄ ÷×ÅÒÈ îÁÚÁÄ óÏÄÅÒÖÁÎÉÅ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ
÷ÐÅÒÅÄ: 13.5 ðÏÓÔÒÏÅÎÉÅ ÂÏÌØÛÉÈ ÐÒÏÓÔÙÈ ÞÉÓÅÌ n Ó ÉÓÐÏÌØÚÏ×ÁÎÉÅÍ ÞÁÓÔÉÞÎÏÇÏ ÒÁÚÌÏÖÅÎÉÑ n-1 ÎÁ ÍÎÏÖÉÔÅÌÉ ÷×ÅÒÈ: 13. íÅÔÏÄÙ ÐÏÓÔÒÏÅÎÉÑ ÂÏÌØÛÉÈ ÐÒÏÓÔÙÈ ÞÉÓÅÌ îÁÚÁÄ: 13.3 ðÒÏÓÔÙÅ ÞÉÓÌÁ ÓÐÅÃÉÁÌØÎÏÇÏ ×ÉÄÁ   óÏÄÅÒÖÁÎÉÅ   ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ

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