Укажіть ідею ( p –1)- алгоритму Полларда факторизації
числа n = pq :

Question

Укажіть ідею ( p –1)- алгоритму  Полларда факторизації
числа  n  =  pq :

Answer

Вибрати випадкове число а,
НСД( а  , п ) = 1,
знайти число  v , що
ділиться на  ord p a , де  р  —
простий дільник числа  п, 
обчислити  r =НСД( а  v   –1,
n) та вибрати нове значення  а , якщо  r 
= 1, або  r  =  n .

Answer

Вибрати випадкове число  а , НСД( а  , п ) = 1,
знайти число  v , для якого   а  v    = 1 ( mod   n ),
обчислити  r =НСД( а  v   –1,  n ) та вибрати нове з значення  а , якщо  r  = 1, або  r  =  n .

Answer

Вибрати випадкове число а, НСД( а  , п ) = 1, намагатися знайти число
 v , для якого   а  v    ≠ 1(mod n), але  а  v    = 1 (mod р), де  р  — простий дільник числа  п , обчислити  r =НСД( а v –1,
n) та вибрати нове значення  а , якщо  r 
= 1, або  r  =  n .

Crowdly

Укажіть ідею ( p –1)- алгоритму Полларда факторизації числа n = pq :

Want instant access to all verified answers on elearning.kubg.edu.ua?