${\displaystyle x^{2}-y^{2}=4kn}$

${\displaystyle k<n^{1/3}}$

${\displaystyle 0\leqslant x-\lfloor {\sqrt {4kn}}\rfloor <{\frac {n^{1/6}}{4{\sqrt {k}}}}+1}$

?????

????? ????????? ??????? ???????. ????? ???????? ??????????? ????? ${\displaystyle r,\;s}$ ????? ??? ${\displaystyle rs<n^{1/3}}$ ? ${\displaystyle \mid pr-qs\mid <n^{1/3}}$ .

?????????????? ???????

????? ${\displaystyle p}$ ? ${\displaystyle q}$ ???????? ???????? ????? ${\displaystyle n}$ . ????? ${\displaystyle x=pr+qs}$ ? ${\displaystyle y=pr-qs}$ , ??? ${\displaystyle r}$ ? ${\displaystyle s}$ ????????????? ??????????? ?????, ????? ????????? ?????????
${\displaystyle x^{2}-y^{2}=(pr+qs)^{2}-(pr-qs)^{2}=4rspq=4kn}$ ,
??? ${\displaystyle k=rs}$ . ? ???? ?????, ????? ????? ${\displaystyle k}$ ????????????? ??????????? ${\displaystyle k<n^{1/3}}$ . ????????????? ????????? ?????? ??????????? ???????.

??? ?????????????? ??????? ??????????? ??????? ${\displaystyle z=x-\lfloor {\sqrt {4bn}}\rfloor =pr+qs-\lfloor {\sqrt {4bn}}\rfloor }$ , ??? ??? ${\displaystyle x^{2}=4kn+y^{2}}$ , ?? ${\displaystyle x\geqslant {\sqrt {4kn}}}$ ? ${\displaystyle z\geqslant 0}$ . ????????? ?????? ?????? ??? ${\displaystyle y}$ , ????????
${\displaystyle n^{2/3}>y^{2}=x^{2}-4kn=(pr+qs+{\sqrt {4kn}})(pr+qs-{\sqrt {4kn}})\geqslant 2{\sqrt {4kn}}(pr+qs-{\sqrt {4kn}})\geqslant 2{\sqrt {4kn}}(z-1)}$ .
?????? ???????, ??? ${\displaystyle z<{\frac {n^{2/3}}{2{\sqrt {4kn}}}}+1={\frac {n^{1/6}}{4{\sqrt {k}}}}+1}$ . ??????? ????????.

???????? (????????????????)

????? ${\displaystyle n}$ ??????? ? ${\displaystyle n>8}$ .

??? 1. ??? ${\displaystyle a=2,\;3,\;\ldots ,\;\lfloor n^{1/3}\rfloor }$ ????????? ??????? ${\displaystyle a\mid n}$ . ???? ?? ???? ???? ?? ??????? ????????? ${\displaystyle n}$ ?? ?????????, ?? ????????? ? ???? 2.

??? 2. ???? ?? ???? 1 ???????? ?? ?????? ? ${\displaystyle n}$ — ????????? , ?? ${\displaystyle n=pq}$ , ??? ${\displaystyle p,\;q}$ — ??????? ????? , ? ${\displaystyle n^{1/3}<p\leqslant q<n^{2/3}}$ . ????? ??? ???? ${\displaystyle k=1,\;2,\;\ldots ,\;\lfloor n^{1/3}\rfloor }$ ? ???? ${\displaystyle d=0,\;\ldots ,\;\left\lfloor {\frac {n^{1/6}}{4{\sqrt {k}}}}\right\rfloor +1}$ ?????????, ???????? ?? ????? ${\displaystyle \left(\left\lfloor {\sqrt {4kn}}\right\rfloor +d\right)^{2}-4kn}$ ????????? ???????????? ?????. ???? ????????, ?? ??? ${\displaystyle A=\left\lfloor {\sqrt {4kn}}\right\rfloor +d}$ ? ${\displaystyle B={\sqrt {A^{2}-4kn}}}$ ????????? ????????? :

${\displaystyle A^{2}\equiv B^{2}{\pmod {n}}}$ ??? ${\displaystyle (A-B)(A+B)\equiv 0{\pmod {n}}}$ .

? ???? ?????? ??? ${\displaystyle d^{*}=\gcd(A-B,\;n)}$ ??????????? ??????????? ${\displaystyle 1<d^{*}<n}$ . ???? ??? ?????????, ?? ${\displaystyle n=d^{*}\cdot (n/d^{*})}$ — ?????????? ${\displaystyle n}$ ?? ??? ?????????.

???? ???????? ?? ????? ?????????? ${\displaystyle n}$ ?? ??? ?????????, ?? ${\displaystyle n}$ — ??????? ?????.

?????? ???????? ? ?????? ????????? ????? ?? ${\displaystyle n}$ ??????? ???????? ?? ????????????? ${\displaystyle \lfloor n^{1/3}\rfloor }$ , ? ????? ?????????? ??????? ???????? ${\displaystyle k}$ ? ${\displaystyle d}$ ??? ???????? ???????????? ????????? ???? ???????. ? ??????, ???? ??????? ???????? ${\displaystyle x}$ ? ${\displaystyle y}$ , ?? ???????, ?? ?? ???????? ??? ????? ${\displaystyle n}$ ???????. ????? ??????? ?? ????? ????????????? ?????? ???????? ??? ???? ????? ${\displaystyle n}$ ?? ????????

????????????

?????????? ??????????? ?? ???????? ?????????????? ?????

?? ?????? ???? ????? ?????????? ${\displaystyle \lceil n^{1/3}\rceil }$ ???????? ??????? ??? ?????? ????????? ????????? ????? ${\displaystyle n}$ .

???????????? ??????? ???? ??????????? ? ????????? ???????????? ????? ${\displaystyle \left(\left\lfloor {\sqrt {4kn}}\right\rfloor +d\right)^{2}-4kn}$ , ?? ??, ???????? ?? ??? ?????? ?????????. ???????????? ??????? ????? ??????????? ?????? ?????????

${\displaystyle {\frac {n^{1/6}}{4}}\sum _{k=1}^{\lfloor n^{1/6}\rfloor }{{\frac {1}{\sqrt {k}}}+2(\lceil n^{1/3}\rceil -\lfloor n^{1/6}\rfloor )}<3\lceil n^{1/3}\rceil }$ .
????? ??????? ???????????? ????? ???? ???????? ${\displaystyle O(n^{1/3})}$ .

??????????? ?? ??????????? ?????????????? ?????

? ??????????? ??????? ????? ?????? ???? ?????? ??????????? ??????? ?????????? ?? ??????????? ???????????? ?????. ???? ?????????????? ??????????? ??? ???????? ???????? ???????????????? ??????????? ??????? ?????????? ?????? ?????? ?? ??????????? ?????????????? ?????.

${\displaystyle n\simeq 2^{l}}$ , ??? ${\displaystyle l}$ — ???????????.

${\displaystyle O(n^{1/3})=O(2^{l/3})=O(e^{l/3})}$

????????? ??????? ??????

??? ?????????????????? ?????? ????? ????? ?????? ????? ??????????? ??????? ?? ?????????? ????? ??????????? ?????, ????? ??? ?????????? ??????? ??????? ?? ?????????. ?????? ???? ?????????? ????? ??????????? ???? ????? ?????? ??????????? ??????????? ?????? ????? .

??? ????? ? ????????? ??????? ????????? ???????? ???????? — ????? ?????? ????????? ???????????????? ???????? ?? ???? ???? ?????????? ?????? ??????? ??????? ?????????.

?????????

for ${\displaystyle a\gets 2}$ to ${\displaystyle \lfloor n^{1/3}\rfloor }$ do

if ${\displaystyle a\vdots n}$ then

return ${\displaystyle a}$

end if

end for for ${\displaystyle k\gets 1}$ to ${\displaystyle \lfloor n^{1/3}\rfloor }$ do

for ${\displaystyle d\gets 0}$ to ${\displaystyle \left\lfloor {\frac {n^{1/6}}{4{\sqrt {k}}}}\right\rfloor +1}$ do

if ${\displaystyle isSquare((\lfloor {\sqrt {4kn}}\rfloor +d)^{2}-4kn)=true}$ then

${\displaystyle A\gets \lfloor {\sqrt {4kn}}\rfloor +d}$

${\displaystyle B\gets {\sqrt {A^{2}-4kn}}}$

if ${\displaystyle 1<gcd(A+B,n)<n}$ then

return ${\displaystyle gcd(A+B,n)}$

else if ${\displaystyle 1<gcd(A-B,n)<n}$ then

return ${\displaystyle gcd(A-B,n)}$

end if

end if

end for

end for

?????????:

${\displaystyle a\vdots n}$ ????????, ??? ${\displaystyle n}$ ???????????? ??????? ?? ${\displaystyle a}$ .

??????? ${\displaystyle isSquare(a)}$ ?????????? ${\displaystyle true}$ , ???? ${\displaystyle a}$ ???????? ?????? ????????? ? ${\displaystyle false}$ ? ????????? ??????.

??????? ${\displaystyle gcd(a,b)}$ ?????????? ?????????? ????? ???????? ????? ${\displaystyle a}$ ? ${\displaystyle b}$ .

??????????? ???????????? ?????????? ??????

????? ????

???????????? ?????????? ???????? ?? ????????? ???????:

??? 1:
??????? ??????????????? ????????, ???????????? ? ????????????, ???????? ???? ????? ????????????? ????????? ?? ????????? ${\displaystyle \{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \}}$ . ?????????????? ??????? ?????????? ????????? ${\displaystyle n}$ ?? ????????? ?? ???????? ?????? ?????? ?????????. ????? ????????? ?????????? ??????? ??????? ???????-??????????? «??????????» ?????????????? ???????? ?? ??????? ????????? ????????. ? ??????, ????? ?????????? ????????? ${\displaystyle n}$ ?? ????????, ???????-???????????, ??????? ?????????? ? ?????????? ????????, ???????? ????????? ????????? ?????? ?? ?????????? ??????. ???? ?? ???????? ?? ??????, ??? ?????????? ???? ????? ??? ????????, ????? ????????? ????????????.

??? 2:
??????? ??????????????? ???????? ?????????? ? ????? 1 ???????? ???? ????? ????? ${\displaystyle k}$ ?? ????????? ${\displaystyle \{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \}}$ . ?????????????? ??????? ?????????? ????????? ??? ???????, ????????? ? ?????????, ?????????, ?????? ?? ????????????? ?????????. ?????????? ? ????? 1 ???????-??????????? ???????????? ?????????? ???????? ?? ?????? ?????????? ???????? ? ????????? ??????? ? ?????????? ??? ?? ?????????? ??????????.

?????????? ??????? ??????? ????????? ???????? ???????? ????????? ??? ?????????? ?????????? ????????? ?? ?????? ? ?????????????? ???????.

?????????? ? ??????????? ?????????? GPGPU

??? ???????? ?????????? ????????? ? ??????????? ?????????? GPGPU ????? ?????? ??? ????????:
1. ??? ?????? ???????? ????????? ??????, ????? ?? ????????? ?? ?? CPU ??? ?? GPU .
2. ?????????? ????? ???????????? ???? GPU .

????????? ???? ?????? ????? ???????????? ??? ????????? ??????.

??? 1:
??? ???????? ????? ???? ??????? ????????? ?? GPU .

????? ${\displaystyle ker}$ — ????? ????????? ???? GPU , ${\displaystyle la}$ — ????? ????????? ????????? ${\displaystyle \{2,\;3,\;4,\;\ldots \lfloor n^{1/3}\rfloor \}}$ . ?????????? ??? ??????:
1. ${\displaystyle la\leqslant ker}$ : ?????????? ${\displaystyle la}$ ???? GPU .
2. ${\displaystyle la>ker}$ : ?????????? ${\displaystyle \left\lceil {\frac {la}{ker}}\right\rceil }$ ???????? . ?? ?????? ???????? ????????? ????????? ${\displaystyle ker}$ ??????? ?? ${\displaystyle ker}$ ?????. ? ????? ?????? ???????? ??????????, ????????? ??? ?????????? ??????????.

??? 2:

???????????? ${\displaystyle k}$ ????? ?????? GPU ?????????? ???? 1. ?? ?????? ???? GPU ????????? ?????? 1—3:
1. ?????????, ???????? ?? ????? ${\displaystyle \left(\left\lfloor {\sqrt {4kn}}\right\rfloor +d\right)^{2}-4kn}$ ????????? ???????????? ?????.
2. ? ?????? ????????? ?????????????? ?????????? ? ?????????? ??????, ????????? ${\displaystyle A=\left\lfloor {\sqrt {4kn}}\right\rfloor +d}$ ? ${\displaystyle B={\sqrt {A^{2}-4kn}}}$ .
3. ??? ???????? ${\displaystyle A}$ ? ${\displaystyle B}$ ????????? ??????? ${\displaystyle A^{2}\equiv B^{2}{\pmod {n}}}$ .
4. ??? ???????? ${\displaystyle A}$ ? ${\displaystyle B}$ , ????????? ????????? ????????, ????????? ?????????? ???????? ??????? ${\displaystyle 0<\gcd(A\pm B,\;n)<n}$ .

????????? ????? ????????????? ????????? ?? CPU , ??? ??? ??????????? ?????????? ?????? ???????? ????, ? ???????? ????????? ?? GPU ??????????? ?????????? ????????.

??????

???????? ?????? ? ${\displaystyle n=1387}$ , ????? ??? ${\displaystyle a=1,\;2,\;3,\;\ldots ,\;\lfloor n^{1/3}\rfloor }$ , ??? ${\displaystyle \lfloor n^{1/3}\rfloor =11}$ , ????????? ???????? ?? ????? ${\displaystyle a}$ ????????? ????? ${\displaystyle n}$ . ???????? ?????????, ??? ????? ???, ????? ????????? ? ?????????? ??????.

??? ???? ${\displaystyle k=1,\;2,\;3,\;\ldots ,\;11}$ ? ???? ${\displaystyle d=0,\;1,\;\ldots ,\;4}$ ?????????, ???????? ?? ????? ${\displaystyle \left(\left\lfloor {\sqrt {4kn}}\right\rfloor +d\right)^{2}-4kn}$ ????????? ???????????? ?????. ? ????? ?????? ?????????? ????? ${\displaystyle k=3}$ ? ${\displaystyle d=1}$ , ??? ????????? ${\displaystyle \left(\left\lfloor {\sqrt {4kn}}\right\rfloor +d\right)^{2}-4kn}$ ???????? ?????? ????????? ? ????? ${\displaystyle 256=16^{2}}$ . ????????????? ${\displaystyle A=130}$ ? ${\displaystyle B=16}$ . ????? ${\displaystyle d^{*}=(A-B;\;n)=19}$ , ????????????? ??????????? ${\displaystyle 1<d^{*}<n}$ ? ???????? ????????? ????? ${\displaystyle n}$ . ? ?????, ?? ????????? ????? ${\displaystyle 1387}$ ?? ??? ?????????: ${\displaystyle 73}$ ? ${\displaystyle 19}$ .

??????????

??????????

1. ????????? ?. ?. . — ?. : ????? , 2003. — 328 ?. — ISBN 5-94057-103-4 . ?? 27 ?????? 2007 ?? Wayback Machine
2. ??????? ??????????. . — ????? , 2011. — 190 ?.
3. Richard Crandall, Carl Pomerance. . — 2nd. — Springer, 2011. — 597 ?. — ISBN 0-387-25282-7 .

??? ????????? ???? ?????? ?????????? : ????? ? ???????? ? ???? ?????? ?????? ?? ??????????? ???????????? ????????? , ?????????????? ?????????? . ????? ??????????? ???????? ????????? ?? ?? ??????. ??????? ??????, ???? ????????? ??? ??????????.