66685 Str140

274 OdpnwJodri do ćwibzeń

4. Dla każdego b, liczba bf - cf n jest resztą o najmniejszej wartości bezwzględnej z dzielenia bf przez n. Jeśli liczba p jest dzielnikiem tej bezwzględnej reszty, to bf = cfn (mod p), a to oznacza, że n jest resztą kwadratową modulo p.

■ W poniższych tablicach i przebiega początkowe wartości takie, że bezwzględne reszty liczb bo, .... bf dają rozkład n na czynniki. W czterech przypadkach (punkty (g), (i), (j), (k)) istnieje wcześniejsza wartość i taka, że dla pewnego podzbioru tych reszt odpowiednie wektory e, dają w sumie wektor zerowy; jednakże w tych przypadkach mamy b = ±c (mod ń).

(e) /	0	1	2	3	4	5	6
	111	2	1	2	2	7	1
	111	223	334	891	2116	3300	5416
bf mod n	-82	117	-71	89	-27	166	-39

(a) f	0	1 2 3
	97	1 1 17
bt	97	98 195 3413
bf mod n	-100	95 -11 44
B= {-1,2,5, 11}; b = NWD(b +c,n) = 257.	97 • 195 •	3413; c = 2^2 • 5 - 11;
(b) i	0	1 2 3
ił	116	2 4 1
bt	116	233 1048 1281
bf mod n	-105	45 -137 80
B={2,3, 5}; b = 233 • 1281; c = 2		l^2 • 3 • 5; AWZ>(6 + c, ń)
(c) I	0	1 2
o,	93	1 2
bt	93	94 281
bf mod n	-128	59 -32
B={—1, 2); b== 93 • 281;	c = 2^6; KI + § ») = 67.
(d) 1	0	1 2
	120	8 3
bt	120	961 3003
bf mod n	-29	65 -116
B= {—1,2,29}; 6 = 120 •	3003;c =	= 2 -29; NWD{b + c, n)

{-1,3,13}; b	= 223	2116 *	5416; c =	= 3^3 113;	; NWD{b + c, n)
i	0	1	2	3	4	5
^ai	120	1	1	8	2	2
bt	120	121	241	2049	4339	10727
bf mod n	-127	114	-27	98	-71	162

{-1,2, 3, 71 b "4 2049 • 10727; c = 2 • 3² • 7; NWD(b + c,ń) = 199.

B =

(O

B

fMpowiola do McieA 2/75

	i	0	1	2	3	4	5
(g)	Ol h,	100	1	1	1	1	2
		100	101	201	302	503	1308
	^ui bf mod n —	123	78	-91	97	-66	Tl
7, 11.13}; 6			= 101	•201 •	503 • 1308; c =		2* 3 *7 • 11	• 13;
(h)	0 i	2	3	4	5	6	7 8	9
/	lii i	1	2	1	4	1	6 2	1
	111 H2	223	558	781	3682	4463	5562 3138	8700
mod>	n -128 95	-67	139	-40	163	-31	79 -115	80
B =	. { — 1 * 2, 5); b	= 111 •	781 • 8700; c		= 2^7 - 5	i; NWD(b + c, n) = :		59.
(0	i ^0	1	2	3	4	5	6 7	8
	4 ^96 Ł 96	1	2	2	5	1	1 1	1
		97	290	677	3675	4352	8027 3026	1700
bf mod n —137		56	-77	32	-107	79	-88 89	-77

_B ^ {-1, 2, 7, 11}; b = 290 • 1700; c = 7 • 11; NWD(b + c, n) = 47.

u i di h.	0 1	2	3	4	5	6	7	8	9
	159 1	2	1	1	2	4	1	5	1
	159 160	479	639	1118	2875	12618	15493 :	13550	3532
i? mod n	-230 89	-158	145	-115	61	-227	50	-167	145
B={	-1.2, 5, 23. 29}; 6		= 639-	3532;	c — 5	• 29; NWD{b -		ł* c, n)	= 97.
(k) i	0	1	2	3	4	5	6	7	8
a.	133	1	2	4	2	3	1	2	1
bs	133	134	401	1738	3877	13369	17246	12115	11488
bf mod n —184		83	-56	107	-64	161	-77	149	-88

£={_!, 2, 7, 11, 23}; 6 = 401 - 3877 - 17246 • 11488; c = 2⁶-7 1l NWD(Jb + c, Ti) = 61.

5.5

2. Krok. 6 pochłania najwięcej czasu. Ten czas jest ograniczony przez

O

<p

A

P

logplog

i

O (A log n log P log log P).