Ask Your Question

Tonelli-Shank values are incorrect when trying to get back to c value for Rabin

asked 2020-10-28 18:27:13 -0600

anything gravatar image

updated 2020-10-31 02:29:25 -0600

FrédéricC gravatar image

I'm working (banging head against wall) on a Rabin encryption as part of a challenge. I thought I was making progress as several algorithms had given em the same values for the mod sqrt but it seems that they are incorrect as I cannot get back to c from them but I don't understand why.

If someone can explain why they might be wrong or where I am going wrong that would be fantastic, thank you.

My values are:

n = 64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271842214498048655106618080254509684622363068406743573918979874641476333101257493419006081088753833559346504226066744706781644205324359031963711461737816475092631177676839385116576945754784715871099567521310291121

p = q = 8043878802952623586394638108236704902850439411184561583961128617599719871469109041598304494567727280429349828456316270041563810531926784203271836896365511

roots = 


However when getting back to c the assertion fails, there is a link here: - I cannot post link but the query param for sage cell is ?q=lnopxn

any help would be fantastic, I'm an incompetent fool at the best of times but I feel I should be closer to this and I am and simply cannot understand why the roots are considered wrong when several different algorithms have given the same results.

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted

answered 2020-10-31 06:09:40 -0600

rburing gravatar image

It seems you have found two solutions $r_1,r_2$ to the equation $r^2 = c \pmod p$, instead of modulo $n=p^2$.

These can be lifted to solutions of $r^2 = c \pmod n$ as explained in Tonelli's 1891 note:

sage: x1 = r1.powermod(p, n) * c.powermod((n - 2*p + 1)/2, n) % n
sage: x1
sage: (x1^2 - c) % n
sage: x2 = (-x1) % n
sage: x2
sage: (x2^2 - c) % n
edit flag offensive delete link more

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


Asked: 2020-10-28 18:27:13 -0600

Seen: 46 times

Last updated: Oct 31