galois.isqrt

class galois.isqrt(n)

Computes the integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\).

Note

This function is included for Python versions before 3.8. For Python 3.8 and later, this function calls math.isqrt() from the standard library.

Parameters

n (int) – A non-negative integer.

Returns

The integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\).

Return type

int

Examples

# Use a large Mersenne prime
In [552]: p = galois.mersenne_primes(2000)[-1]; p
Out[552]: 10407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087

In [553]: sqrt_p = galois.isqrt(p); sqrt_p
Out[553]: 3226132699481594337650229932669505772017441235628244885631123722785761803162998767122846394796285964908262519578341713326387400858087872534573955058079614218029097609909460991319304989482693499

In [554]: sqrt_p**2 <= p
Out[554]: True

In [555]: (sqrt_p + 1)**2 <= p
Out[555]: False