Розклад числа на прості множники, Детальна інформація

3 -1 -625 -54 156 (1, 0, 0, 0, 0, 0)

4 2 320 26 * 5 159 (0, 0, 0, 1, 0, 0)

5 -2 -936 -23 * 32 * 13 155 (1, 1, 0, 0, 1, 0)

6 4 960 26 * 3 * 5 161 (0, 0, 1 ,1, 0, 0)

7 -6 -2160 -24 * 33 * 5 151 (1, 0, 1, 1, 0, 0)



4. Виберемо T = {1, 2, 5}, оскільки v1 + v2 + v5 = 0.

5. Обчислимо x = (a1a2a5) (mod n) = 936 = 26 * 34 * 132.

6. l1 = 1, l2 = 3, l3 = 2, l4 = 0, l5 = 1, l6 = 0.

7. y = -23 * 32 * 13 (mod n) = 24025.

8. Оскільки 936 \xF0BA\xF020–24025 (mod n), необхідно шукати іншу множину T.

9. Виберемо T = {3, 6, 7}, оскільки v3 + v6 + v7 = 0.

10. Обчислимо x = (a3a6a7) mod n = 23405 = 210 * 34 * 56.

11. l1 = 1, l2 = 5, l3 = 2, l4 = 3, l5 = 0, l6 = 0.

12. y = -25 * 32 * 53 (mod n) = 13922.

13. 23405 \xF0B9 \xF0B113922 (mod n).

d = НСД(x – y, n) = НСД(9483, 24961) = 109 – дільник.

Відповідь: 109 – дільник 24961.

7

10

19

4

1