5027720049

Lista 7 - Faktoryzacja

1.    Rozłóż 525647 na czynniki wiedząc, że 525647 = 744² — 167².

2.    Rozłóż na czynniki za pomocą algorytmu Fermata: a) 8858; b) 53357; c) 34571.

Uwaga: Można wykorzystywać kalkulator z tablicowaniem funkcji, ale nie możesz stosować próbnego dzielenia.

3.    Korzystając z równości 30² = 49 mod 851 rozłóż liczbę 851 na czynniki.

4.    Obliczając x² mod 1121 rozłóż 1121 na czynniki.

5.    Znajdź nietrywialny dzielnik liczby 3157 korzystając z kongruencji 18² = 59² mod 3157.

6.    Czy z danych 41² = 2⁴ • 3, 43² = 2³ • 3³, 45² = 2³ • 7² mod 1633 można wywnioskować rozkład 1633 na czynniki?

7.    Znajdź nietrywialny dzielnik N za pomocą algorytmu Dixona wykorzystując podane informacje:

a)    N = 61063,

1882² = 2 • 3³ • 5 mod 61063,    1898² = 60750 mod 61063.

b)    N = 52097,

399² = 2² • 3 • 5 mod 52907,763² = 2⁶ • 3 mod 52907,

773² = 2⁶ • 3⁵ mod 52907,    976² = 2 • 5³ mod 52907.

8.    Rozłóż za pomocą p-Pollarda: a) 221. b) 3959.

9.    Metodą p— 1 Pollarda znajdź nietrywialny dzielnik liczby: a) 77; b) 247; c) 7991.

10. *. Wyjaśnij, dlaczego w algorytmie p-Pollarda można zakładać, że odpowiednia para ma postać x<ii — £j.