Вычисления в конечных полях

Пример 1.11. Пусть II - 60. Оно раскладывается на множи­ тели 2, 2, 3 и 5 или т = 2''-3-5. Тогда по представленной формуле получим Ф (60) = (2' - 2') (з - 3") (5 - 5") =: 2 • 2 • 4 = 16. Таким образом, функцию Эйлера можно вычислить по сле­ дующим формулам; а) б) ф('«) = т - если in - простое число; если т - составное и т = р"' • pV' /?,, i-\,k ~ простые числа; "А -I )• ••••РА ^ч (. 1 ^ / __1_^ т . А . 1 1 1 • \ если т - составное и /« = р, • р, •... • . Описание алгоритма вычисления функции Эйлера На вход: число т G N. На выходе; 'значение (pint). 1. Пусть задан массив М, простых чисел т / элементов, где наибольшее из простых чисел не превосходит . Массив чисел можно получить, например, с помощью алгоритма модифициро­ ванного «решета» Эратосфена. 2. Зададим / = 1 (индекс текущего простого числа в массиве М,) и /' = 1 (текущий найденный сомножитель числа т), т' = т (запом­ ним т для промежуточных вычислений), 3. pi = О и а, = 0. 4. Если т' mod М,,[/] = О, то нашли сомножитель числа irr. - сохраняем pi = М,,[/] и а,- = а,- + 1, - т' = ni'I (под знаком «/» понимается це;ючисленнос деление), - перейти к началу этого пункта. 29