# Computing square root in IntegerModRing(2^n)

Hi, I'm trying to compute one square root in an IntegerModRing(2^n), but sage appears to fail to do so, am I doing something wrong?

PoC:

sage: n = 216
sage: FF = IntegerModRing(2^n)
sage: FF(1 + 2^(n - 1)).sqrt()


Thanks!

edit retag close merge delete

Sort by » oldest newest most voted

A reasonable algorithm does not have been implemented for that ring. This is a shame as it does work in p-adics.

sage: R = Zp(2, prec=300)
sage: R
2-adic Ring with capped relative precision 300
sage: R(1 + 2^(216 - 1))
1 + 2^215 + O(2^300)
sage: R(1 + 2^(216 - 1)).sqrt()
1 + 2^214 + O(2^299)


I guess this is what you should be using if you are interested in IntegerModRing(p^k).

For IntegerModRing Sage uses a generic algorithm that only works with small numbers

sage: sage: n = 20
sage: FF = IntegerModRing(2^n)
sage: FF(1 + 2^(n - 1)).sqrt()
262143

more

thanks for the helpful quick reply. However, if the square root exists, shouldn't it be possible to compute it (exactly) still? In mathematica I can easily do so

a = Mod[1 + 2^(n - 1), 2^n];
root = PowerMod[a, 1/2, 2^n]


Sure. Use p-adics with precision large enough and truncate. This is a prefectly valid algorithm.

sage: U = IntegerModRing(2^216)
sage: r_padics = R(1 + 2^(216 - 1)).sqrt()
sage: r_mod
26328072917139296674479506920917608079723773850137277813577744385
sage: r_mod**2 == 1 + 2^(216-1)
True


Using PowerMod is just a user convenience which is (sadly) not available in Sage.

great! thanks not only for the reply but also for the explanation. I've accepted the answer, unfortunately cannot upvote it as well (not enough points). stay safe!