consider the following algorithm for completing the square root of an n-bit integer square root(x): for i=1,2....,[x/2]
Posted: Thu Jul 14, 2022 2:18 pm
consider the following algorithm for completing the square rootof an n-bit integer
square root(x): for i=1,2....,[x/2] do
if isquare == x then
output i
end if
end for
claim : the above algorithm runs in polynomial time.
square root(x): for i=1,2....,[x/2] do
if isquare == x then
output i
end if
end for
claim : the above algorithm runs in polynomial time.