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!
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
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 = U(r_padics)
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.
Asked: 2020-04-20 21:45:17 +0100
Seen: 290 times
Last updated: Apr 21 '20
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
