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()
262143thanks 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 = U(r_padics)
sage: r_mod
26328072917139296674479506920917608079723773850137277813577744385
sage: r_mod**2 == 1 + 2^(216-1)
TrueUsing 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!
ok, i did it then...
Asked: 4 years ago
Seen: 342 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.
