Ask Your Question
1

Computing square root in IntegerModRing(2^n)

asked 2020-04-20 21:45:17 +0100

apopoq gravatar image

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2020-04-21 09:40:39 +0100

vdelecroix gravatar image

updated 2020-04-21 09:43:59 +0100

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
edit flag offensive delete link more

Comments

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]
apopoq gravatar imageapopoq ( 2020-04-21 10:49:37 +0100 )edit

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.

vdelecroix gravatar imagevdelecroix ( 2020-04-21 12:29:15 +0100 )edit

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!

apopoq gravatar imageapopoq ( 2020-04-21 13:04:38 +0100 )edit

ok, i did it then...

dan_fulea gravatar imagedan_fulea ( 2020-04-21 16:03:38 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2020-04-20 21:45:17 +0100

Seen: 306 times

Last updated: Apr 21 '20