Zadanie jest poprzedzone przykładem, który powinien ułatwić rozwiązanie postawionego
problemu. Zgodnie z opisem w pierwszym kroku przyjmujemy, że wynik jest równy
x. W
kolejnych krokach podnosimy ten wynik do kwadratu, a w przypadku gdy kolejny bit rozwinięcia jest równy 1, wykonujemy dodatkowe mnożenie uzyskanego wyniku przez
x. Rozwinięcie binarne liczby z zadania jest równe ݇
k = 38 = (100110)
2. Kolejno obliczane potęgi
przedstawione zostały w tabelce. Zauważmy, że w przypadku gdy bit rozwinięcia jest równy
1, otrzymujemy dwie kolejne potęgi.
i
|
ki — kolejny bit rozwinięcia
|
obliczona potęga
|
5
|
1
|
X
|
4
|
0
|
x2
|
3
|
0
|
x4
|
2
|
1
|
x8, x9
|
1
|
1
|
x18, x19
|
0
|
0
|
x38
|