ΠΠΠΠΠ Π£Π‘Π‘ΠΠΠ ΠΠΠ‘Π£ΠΠΠ Π‘Π’ΠΠΠΠΠ«Π Π£ΠΠΠΠΠ Π‘ΠΠ’ΠΠ’ ΠΠΠ€ΠΠ ΠΠΠ’ΠΠΠ Π Π ΠΠΠΠΠΠΠΠΠ’Π ΠΠΠΠΠ
ΠΠ°ΡΠ΅Π΄ΡΠ° ΠΈΠ½ΡΠΎΡΠΌΠ°ΡΠΈΠΊΠΈ
ΠΠΎΡΡΠ½ΠΈΡΠ΅Π»ΡΠ½Π°Ρ Π·Π°ΠΏΠΈΡΠΊΠ° ΠΊ ΠΊΡΡΡΠΎΠ²ΠΎΠΌΡ ΠΏΡΠΎΠ΅ΠΊΡΡ
ΠΏΠΎ ΠΊΡΡΡΡ
«ΠΡΡ
ΠΈΡΠ΅ΠΊΡΡΡΠ° Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΡ
ΡΠΈΡΡΠ΅ΠΌ»
Π½Π° ΡΠ΅ΠΌΡ
«ΠΠ»Π°Π½ΠΈΡΠΎΠ²Π°Π½ΠΈΠ΅ ΡΠ°Π±ΠΎΡ Π² Π²ΡΡΠΈΡΠ»ΠΈΡΠ΅Π»ΡΠ½ΡΡ
ΡΠΈΡΡΠ΅ΠΌΠ°Ρ
ΠΏΠΎ ΠΊΡΠΈΡΠ΅ΡΠΈΡ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡΠ½ΠΎΠ³ΠΎ ΡΡΠΌΠΌΠ°ΡΠ½ΠΎΠ³ΠΎ Π²ΡΠ΅ΠΌΠ΅Π½ΠΈ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΡ ΡΠ°Π±ΠΎΡ»
ΠΠΠΠ‘Π, 2001
ΠΠΎΡΡΠ°Π½ΠΎΠ²ΠΊΠ° Π·Π°Π΄Π°ΡΠΈ
Π€Π°ΠΊΡΠΎΡΠΈΠ·ΠΎΠ²Π°ΡΡ ΡΠ΅Π»ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ N Ρ ΠΏΠΎΠΌΠΎΡΡΡ ΡΠΎ-ΠΌΠ΅ΡΠΎΠ΄Π° ΠΠΎΠ»Π»Π°ΡΠ΄Π°.
ΠΡΡ
ΠΎΠ΄Π½ΡΠ΅ Π΄Π°Π½Π½ΡΠ΅:
Π¦Π΅Π»ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ N.
ΠΡΠ°ΡΠΊΠΎΠ΅ ΠΎΠΏΠΈΡΠ°Π½ΠΈΠ΅ ΡΠΎ-ΠΌΠ΅ΡΠΎΠ΄Π° ΠΠΎΠ»Π»Π°ΡΠ΄Π°
Π ΠΎ-ΠΌΠ΅ΡΠΎΠ΄ ΠΠΎΠ»Π»Π°ΡΠ΄Π° Π΄Π»Ρ ΡΠ°ΠΊΡΠΎΡΠΈΠ·Π°ΡΠΈΠΈ Π·Π°ΠΊΠ»ΡΡΠ°Π΅ΡΡΡ Π² ΡΠ»Π΅Π΄ΡΡΡΠ΅ΠΌ:
Π‘ΠΎΡΡΠ°Π²Π»ΡΠ΅ΡΡΡ ΠΏΠΎΡΠ»Π΅Π΄ΠΎΠ²Π°ΡΠ΅Π»ΡΠ½ΠΎΡΡΡ {x}, xi+1=f (xi), f (x)=x2+1
ΠΡΡΠΈΡΠ»ΡΡΡΡΡ ΡΠ°Π·Π½ΠΎΡΡΠΈ yi= x2i— xi
ΠΡΡΠΈΡΠ»ΡΠ΅ΡΡΡ Π½Π°ΠΈΠ±ΠΎΠ»ΡΡΠΈΠΉ ΠΎΠ±ΡΠΈΠΉ Π΄Π΅Π»ΠΈΡΠ΅Π»Ρ ΡΠΈΡΠ΅Π» yi ΠΈ N. ΠΡΠ»ΠΈ ΠΎΠ½ Π±ΠΎΠ»ΡΡΠ΅ 1, ΠΏΠΎΠ»ΡΡΠ΅Π½Π½ΡΠΉ ΠΠΠ (yi, N) ΡΠ²Π»ΡΠ΅ΡΡΡ Π΄Π΅Π»ΠΈΡΠ΅Π»Π΅ΠΌ ΡΠΈΡΠ»Π° N. ΠΡΠ»ΠΈ Π½Π΅Ρ — ΠΏΡΠΎΠ΄ΠΎΠ»ΠΆΠ°Π΅ΠΌ Π²ΡΠΏΠΎΠ»Π½Π΅Π½ΠΈΠ΅ Π°Π»Π³ΠΎΡΠΈΡΠΌΠ° ΡΠ½Π°ΡΠ°Π»Π°.
ΠΠ»Π³ΠΎΡΠΈΡΠΌ ΡΠ°Π±ΠΎΡΡ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
— ΠΠ²ΠΎΠ΄ ΡΠΈΡΠ»Π° N.
— ΠΠΎΠΊΠ° N Π½Π΅ ΡΠ°Π²Π½ΠΎ 1:
1. ΠΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ xi
2. ΠΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ x2i
ΠΠ°Ρ
ΠΎΠΆΠ΄Π΅Π½ΠΈΠ΅ ΡΠ°Π·Π½ΠΎΡΡΠΈ yi= x2i— xi
3. ΠΡΡΠΈΡΠ»Π΅Π½ΠΈΠ΅ ΠΠΠ (yi, N)
4. ΠΡΠΎΠ²Π΅ΡΠΊΠ° ΠΠΠ (yi, N) Π½Π° ΡΠ°Π²Π΅Π½ΡΡΠ²ΠΎ 1. ΠΡΠ»ΠΈ ΡΡΠΎ ΡΡΠ»ΠΎΠ²ΠΈΠ΅ Π²ΡΠΏΠΎΠ»Π½ΡΠ΅ΡΡΡ, ΡΠΎ ΠΠΠ — ΠΎΠ΄ΠΈΠ½ ΠΈΠ· Π΄Π΅Π»ΠΈΡΠ΅Π»Π΅ΠΉ ΡΠΈΡΠ»Π° N. ΠΠ΅Π»ΠΈΠΌ N Π½Π° ΠΠΠ ΠΈ ΠΏΠ΅ΡΠ΅Ρ
ΠΎΠ΄ΠΈΠΌ ΠΊ Π½Π°ΡΠ°Π»Ρ ΡΠΈΠΊΠ»Π°.
ΠΡΡ
ΠΎΠ΄ ΠΈΠ· ΡΠΈΠΊΠ»Π° — ΡΠ°Π²Π΅Π½ΡΡΠ²ΠΎ ΡΠΈΡΠ»Π° N Π΅Π΄ΠΈΠ½ΠΈΡΠ΅.
ΠΠΈΡΡΠΈΠ½Π³ ΠΏΡΠΎΠ³ΡΠ°ΠΌΠΌΡ
#include «stdio.h»
#include «conio.h»
#include «iostream.h»
unsigned long NOD (unsigned long a, unsigned long b)
{
while ((a > 0) && (b > 0))
if (a > b) a %= b;
else b %= a;
if (a == 0) return b;
return a;
}
void main ()
{
unsigned long N, y, x, x1, i, j, d;
clrscr ();
printf («ΠΠ²Π΅Π΄ΠΈΡΠ΅ N: «);
scanf («%ld», &N);
i = 1;
x = 0;
do {
x = (x*x + 1) % N;
x1 = x;
for (j = 0; j < i*2-i; j++)
x1 = (x1*x1 + 1) % N;
i++;
y = x1 — x;
d = NOD (y, N);
if (d ≠ 1)
{
cout<<" ΠΠ΅Π»ΠΈΡΠ΅Π»Ρ: «<<» «;
cout<<" ΠΠΎΠ»-Π²ΠΎ ΡΠ°Π³ΠΎΠ²: «<
N/=d;
i = 1;
x = 0;
}
}
while (N ≠ 1);
getch ();
}