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

12.2.1 áÌÇÏÒÉÔÍ ûÅÒÍÁÎÁ -- ìÅÍÁÎÁ

üÔÏÔ ÁÌÇÏÒÉÔÍ ÉÍÅÅÔ ÏÃÅÎËÕ ÓÌÏÖÎÏÓÔÉ $ O(n^{1/3})$ É ÚÁËÌÀÞÁÅÔÓÑ × ÓÌÅÄÕÀÝÅÍ.     1. óÞÉÔÁÑ, ÞÔÏ $ n>8$, ÐÏÓÌÅÄÏ×ÁÔÅÌØÎÏ ÐÒÏ×ÅÒÑÅÍ ÄÅÌÉÍÏÓÔØ ÉÓÈÏÄÎÏÇÏ ÞÉÓÌÁ $ n$ ÎÁ $ i=2,3,\ldots,\left[n^{1/3}\right]$.

    2. åÓÌÉ ÎÁ ÜÔÁÐÅ 1 ÄÅÌÉÔÅÌØ ÎÅ ÎÁÊÄÅÎ É $ n$ ÓÏÓÔÁ×ÎÏÅ, ÔÏ $ n=pq$, ÇÄÅ $ p$ É $ q$ -- ÐÒÏÓÔÙÅ ÞÉÓÌÁ, ÐÒÉÞÅÍ $ n^{1/3}<p\leqslant q<n^{2/3}$. ôÏÇÄÁ ÄÌÑ ËÁÖÄÙÈ $ k=1,2,\ldots,\left[n^{1/3}\right]$ É $ d=0,1,\ldots,\left[n^{1/6}\left/\left(4\sqrt k\right)\right.\right]+1$ ÐÏÌÁÇÁÅÍ $ a=\left[\sqrt{4kn}\right]+d$ É ÐÒÏ×ÅÒÑÅÍ, Ñ×ÌÑÅÔÓÑ ÌÉ ÞÉÓÌÏ $ a^2-4kn$ Ë×ÁÄÒÁÔÏÍ ÎÁÔÕÒÁÌØÎÏÇÏ ÞÉÓÌÁ. åÓÌÉ ÄÁ, ÔÏ $ a^2\equiv b^2\mkern5mu({\rm mod}\,\,n)$, ÇÄÅ $ b=\sqrt{a^2-4kn}$, ÐÏÜÔÏÍÕ ÅÓÌÉ $ 1<(a-\varepsilon b,n)<n$ ÄÌÑ ÎÅËÏÔÏÒÏÇÏ $ \varepsilon\in\{-1,1\}$, ÔÏ $ (a-\varepsilon b,n)$ -- ÉÓËÏÍÙÊ ÎÅÔÒÉ×ÉÁÌØÎÙÊ ÄÅÌÉÔÅÌØ $ n$.

ôÅÏÒÅÍÁ 2.  åÓÌÉ ÁÌÇÏÒÉÔÍ ûÅÒÍÁÎÁ -- ìÅÍÁÎÁ ÚÁËÏÎÞÉÌ ÒÁÂÏÔÕ É ÎÅ ÎÁÛÅÌ ÄÅÌÉÔÅÌÑ $ n$, ÔÏ $ n$ -- ÐÒÏÓÔÏÅ ÞÉÓÌÏ.

ïÔÍÅÔÉÍ, ÞÔÏ × ÁÌÇÏÒÉÔÍÅ ûÅÒÍÁÎÁ -- ìÅÍÁÎÁ ×ÏÚÍÏÖÎÙ ÐÁÒÁÌÌÅÌØÎÙÅ ×ÙÞÉÓÌÅÎÉÑ.

÷ÐÅÒÅÄ ÷×ÅÒÈ îÁÚÁÄ óÏÄÅÒÖÁÎÉÅ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ
÷ÐÅÒÅÄ: 12.2.2 íÅÔÏÄ ðÏÌÌÁÒÄÁ ÷×ÅÒÈ: 12.2 æÁËÔÏÒÉÚÁÃÉÑ ÞÉÓÅÌ Ó ÜËÓÐÏÎÅÎÃÉÁÌØÎÏÊ ÓÌÏÖÎÏÓÔØÀ îÁÚÁÄ: 12.2 æÁËÔÏÒÉÚÁÃÉÑ ÞÉÓÅÌ Ó ÜËÓÐÏÎÅÎÃÉÁÌØÎÏÊ ÓÌÏÖÎÏÓÔØÀ   óÏÄÅÒÖÁÎÉÅ   ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ

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