ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 31 Oct 2020 12:09:40 +0100Tonelli-Shank values are incorrect when trying to get back to c value for Rabinhttps://ask.sagemath.org/question/54067/tonelli-shank-values-are-incorrect-when-trying-to-get-back-to-c-value-for-rabin/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 =
2187931274452861858404184425736861076518005991476611501855956036160679792394841793895180158176546375577356726244165298846056538405976359097397665134536364
5855947528499761727990453682499843826332433419707950082105172581439040079074267247703124336391180904851993102212150971195507272125950425105874171761829147
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.Thu, 29 Oct 2020 00:27:13 +0100https://ask.sagemath.org/question/54067/tonelli-shank-values-are-incorrect-when-trying-to-get-back-to-c-value-for-rabin/Answer by rburing for <p>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.</p>
<p>If someone can explain why they might be wrong or where I am going wrong that would be fantastic, thank you.</p>
<p>My values are: </p>
<pre><code>n = 64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271842214498048655106618080254509684622363068406743573918979874641476333101257493419006081088753833559346504226066744706781644205324359031963711461737816475092631177676839385116576945754784715871099567521310291121
p = q = 8043878802952623586394638108236704902850439411184561583961128617599719871469109041598304494567727280429349828456316270041563810531926784203271836896365511
roots =
2187931274452861858404184425736861076518005991476611501855956036160679792394841793895180158176546375577356726244165298846056538405976359097397665134536364
5855947528499761727990453682499843826332433419707950082105172581439040079074267247703124336391180904851993102212150971195507272125950425105874171761829147
</code></pre>
<p>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</p>
<p>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.</p>
https://ask.sagemath.org/question/54067/tonelli-shank-values-are-incorrect-when-trying-to-get-back-to-c-value-for-rabin/?answer=54093#post-id-54093It 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](https://mathoverflow.net/a/223806/61197):
sage: x1 = r1.powermod(p, n) * c.powermod((n - 2*p + 1)/2, n) % n
sage: x1
64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271753034649923142113830515792268064444518487016929096020442400942507965121543243161654445051643484581747767916266843209412116392813513581705574559159767553746511654597410103495145251789022071249050813249711591476
sage: (x1^2 - c) % n
0
sage: x2 = (-x1) % n
sage: x2
89179848125512992787564462241620177844581389814477898537473698968367979714250257351636037110348977598736309799901497369527812510845450258136902578048921346119523079429281621431693965762644622048754271598699645
sage: (x2^2 - c) % n
0Sat, 31 Oct 2020 12:09:40 +0100https://ask.sagemath.org/question/54067/tonelli-shank-values-are-incorrect-when-trying-to-get-back-to-c-value-for-rabin/?answer=54093#post-id-54093