Revision history [back]

Tonelli-Shank vales 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.

 2 None FrédéricC 4473 ●3 ●37 ●94

Tonelli-Shank vales 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.

 3 None FrédéricC 4473 ●3 ●37 ●94

Tonelli-Shank vales 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 64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271842214498048655106618080254509684622363068406743573918979874641476333101257493419006081088753833559346504226066744706781644205324359031963711461737816475092631177676839385116576945754784715871099567521310291121

p = q = 8043878802952623586394638108236704902850439411184561583961128617599719871469109041598304494567727280429349828456316270041563810531926784203271836896365511 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.