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
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